前言
沒做出來，看了很多篇題解后AC了，感覺大部分題解講得不清楚。
題目
思路
結果有兩種求法
- 模擬跑步過程，統計每個節點能觀察到的人數
- 考慮每條路徑會對哪些節點作出貢獻（當前路徑的玩家能被觀察到）
嘗試
第一種求法必須遍歷當前路徑的所有節點，不能優化，因為不能跳過任何節點，最壞時間復雜度O(nm)，超時，換思路。
正解思路
不再遍歷統計，換第二種求法。
路徑 si → ti 若能對節點 u 有貢獻，節點u一定是路徑L上的節點。
分情況討論
- 節點u在路徑 si → lca(si, ti) 上，設depth[i] = 節點i的深度（根節點為1），此時depth[si] = depth[u] + w[u]。
- 節點u在路徑 lca(si, ti)?→ ti 上，設dis(x, y) = x到y之間的距離，此時 dis(si, ti) = w[u] + (depth[ti] - depth[u])，移項得 dis(si, ti) - depth[ti] = w[u] - depth[u]，移項后等式左邊是已知量。
根據等式，且n < 10^6，用桶快速得出節點觀察到的人數，設 cntStart[depth[u] + w[u]] = 滿足節點 u 的 si（即depth[si]?= depth[u] + w[u]），起點為 si 的路徑個數；cntLast[w[u] - depth[u]] = 滿足節點 u 的 ti，（即dis(si, ti) - depth[ti] = w[u] - depth[u]），終點為ti的路徑個數。
設result[u] = 在節點u能觀察到的人數（相當于路徑數）。
除了節點 u = lca(si, ti) 的情況，節點u要么在路徑 si → lca(si, ti) 上，此時 result[u] +=?起點為 si 的路徑個數，要么在路徑 lca(si, ti)?→ ti 上，此時 result[u] += 終點為ti的路徑個數，路徑個數正確統計。
當節點 u = lca(si, ti)，若 si 和 ti 會對節點u產生貢獻，此時 result[u] +=?起點為 si 的路徑個數 +?終點為ti的路徑個數，si → ti 的路徑會被計算兩次（si 計算一次，ti 計算一次），需要result[u] = result[u] - 1。
當路徑?si → ti 的 si 滿足?depth[si] = depth[lca(si, ti)] + w[lca(si, ti)]，ti也會滿足dis(si, ti) - depth[ti] = w[lca(si, ti)] - depth[lca(si, ti)]。
證明
depth[lca(si, ti)] + w[lca(si, ti)] = w[lca(si, ti)] - depth[lca(si, ti)] + 2 ×?depth[lca(si, ti)]，
那么有
dis(si, ti) - depth[ti] +?2 ×?depth[lca(si, ti)]?= w[lca(si, ti)] - depth[lca(si, ti)] +?2 ×?depth[lca(si, ti)]，化簡得
depth[si] = depth[lca(si, ti)] + w[lca(si, ti)] 。
證畢
所以只要判斷到 depth[si] = depth[lca(si, ti)] + w[lca(si, ti)] ，就result[lca(si, ti)] = result[lca(si, ti)] - 1。
實現
發現無論什么情況，si、ti 都在以節點u為根的子樹上，所以 dfs 遍歷，回溯的時候統計。
tot1 = 以節點u為根的子樹之外的起點 si 滿足 depth[si] = depth[u] + w[u] 的路徑個數，tot2 =?以節點u為根的子樹之外的終點 ti?滿足 dis(si, ti) - depth[ti] = w[u] - depth[u] 的路徑個數，計算tot1，tot2是為了去掉節點u不再上面的路徑數。根據 tot1 和 tot2 的定義，要在下一層遞歸前求解。
先統計節點u為起點和為終點時有貢獻的路徑數，可能滿足?depth[si] = depth[u] + w[u] 的 si 為 u，滿足?dis(si, ti) - depth[ti] = w[u] - depth[u] 的 ti 為 u。
最后減去 lca(si, ti) = u 的路徑數，這些路徑之后不會再被計入。
LCA用倍增加速求解。
細節見代碼。
代碼
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 299998 + 5;
const LL Maxm = 299998 + 5;
const LL Maxk = 20;
const LL Size = 300000;struct node {LL s, t, e;
} pla[Maxm];vector<LL> tree[Maxn];
vector<LL> tId[Maxn];
vector<LL> LId[Maxn];
LL vct_w[Maxn], depth[Maxn], father[Maxn][Maxk];
LL cnt_s[Maxn], cntStart[Maxn * 2], cntLast[Maxn * 2], result[Maxn];void init(LL u, LL fa) {depth[u] = depth[fa] + 1;father[u][0] = fa;for (LL i = 1; depth[u] > (1 << i); ++i) {father[u][i] = father[father[u][i - 1]][i - 1];}for (auto v : tree[u]) {if (v != fa) init(v, u);}return;
}LL LCA(LL u, LL v) {if (depth[u] < depth[v]) swap(u, v);for (LL i = Maxk - 1; i >= 0; --i) {if (depth[father[u][i]] >= depth[v]) u = father[u][i];}if (u == v) return u;for (LL i = Maxk - 1; i >= 0; --i) {if (father[u][i] != father[v][i]) {u = father[u][i];v = father[v][i];}}return father[u][0];
}void dfs(LL u, LL fa) {LL tot1 = cntStart[depth[u] + vct_w[u]], tot2 = cntLast[vct_w[u] - depth[u] + Size];for (auto v : tree[u]) {if (v != fa) dfs(v, u);}cntStart[depth[u]] += cnt_s[u];for (auto id : tId[u]) {++cntLast[pla[id].e - depth[pla[id].t] + Size];}result[u] += (cntStart[depth[u] + vct_w[u]] - tot1) + (cntLast[vct_w[u] - depth[u] + Size] - tot2);for (auto id : LId[u]) {--cntStart[depth[pla[id].s]];--cntLast[pla[id].e - depth[pla[id].t] + Size];}return;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, u, v;cin >> n >> m;for (LL i = 1; i < n; ++i) {cin >> u >> v;tree[u].emplace_back(v);tree[v].emplace_back(u);}for (LL i = 1; i <= n; ++i) cin >> vct_w[i];init(1, 0);LL lcaId = 0;for (LL i = 1; i <= m; ++i) {cin >> pla[i].s >> pla[i].t;lcaId = LCA(pla[i].s, pla[i].t);pla[i].e = depth[pla[i].s] + depth[pla[i].t] - depth[lcaId] * 2;++cnt_s[pla[i].s];tId[pla[i].t].emplace_back(i);LId[lcaId].emplace_back(i);if (depth[pla[i].s] == depth[lcaId] + vct_w[lcaId]) --result[lcaId];}dfs(1, 0);for (LL i = 1; i <= n; ++i) cout << result[i] << ' ';return 0;
}
注意
- cntStart要開到2 * Maxn
- 明確每個數組的下標和元素是什么，搞錯很難調
- 思路是一條條的路徑，被卡住就換條路徑。
)
