题目概述
题目链接：https://www.luogu.com.cn/problem/P1600。
给你一棵树，每个节点上有一个观察时间，现在有 \(m\) 个选手，选手会以每秒一个节点的速度，从 \(s_i\) 到 \(t_i\)。
求对于每个节点的观察时间能观察到多少个选手。
分析
经典题目记录一下。
显然，从 \(s_i\) 到 \(t_i\)，可以拆成 \(s_i\rightarrow lca\) 以及 \(lca\rightarrow t_i\)。
于是我们分两类进行讨论。
左半部分（\(s_i\rightarrow lca\)）
那么第 \(i\) 个选手能在节点 \(u\) 被观察到当且仅当：\(dep_{s_i}-dep_{u}=w_u\)。
把相同下标的放一起有：\(dep_{s_i}=w_u+dep_u\)。
也就是说在这条路径上面每个点需要查询自己能不能满足 \(dep_u+w_u=dep_{s_i}\)，相当于我可以放 \(dep_{s_i}\) 到这个点上作为我要求的答案，这种方法在 dsu on tree 很常见。
右半部分（\(t_i\rightarrow lca\)）
在节点 \(u\) 能够被观察到当且仅当：\(dep_{s_i}+dep_u-2\times dep_{lca}=w_u\)。
移项可得：\(w_u-dep_u=dep_{s_i}-2\times dep_{lca}\)。
结合
用两个桶存即可，只需要遍历子树，所以说直接差分。
代码
时间复杂度 \(\mathcal{O}(n+m)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 300005
#define PII pair<int,int>
using namespace std;
const int D = 3e5;
int fa[N][30],dep[N];
vector<int> g[N];
vector<PII> add[N],del[N];
int cnt[2][N << 1];
void dfs0(int cur,int father) {fa[cur][0] = father;dep[cur] = dep[father] + 1;for (auto i : g[cur])if (i != father) dfs0(i,cur);
}
int LCA(int x,int y) {if (x == y) return x;if (dep[x] < dep[y]) x ^= y ^= x ^= y;for (int j = 25;j >= 0;j --)if (dep[fa[x][j]] >= dep[y]) x = fa[x][j];if (x == y) return x;for (int j = 25;j >= 0;j --)if (fa[x][j] != fa[y][j]) x = fa[x][j],y = fa[y][j];return fa[x][0];
}
int n,m,w[N],ans[N];
void dfs(int cur,int fa) {int pre1 = cnt[0][w[cur] + dep[cur] + D],pre2 = cnt[1] [w[cur] - dep[cur] + D];for (auto i : add[cur]) cnt[i.first][i.second + D] ++;for (auto i : del[cur]) cnt[i.first][i.second + D] --;for (auto i : g[cur])if (i != fa) dfs(i,cur);ans[cur] = cnt[0][w[cur] + dep[cur] + D] - pre1 + cnt[1][w[cur] - dep[cur] + D] - pre2;
}
signed main(){cin >> n >> m;for (int i = 1;i < n;i ++) {int u,v;scanf("%lld%lld",&u,&v);g[u].push_back(v);g[v].push_back(u);}for (int i = 1;i <= n;i ++) scanf("%lld",&w[i]);dfs0(1,0);for (int j = 1;j <= 25;j ++)for (int i = 1;i <= n;i ++)fa[i][j] = fa[fa[i][j - 1]][j - 1];for (int i = 1;i <= m;i ++) {int st,ed;scanf("%lld%lld",&st,&ed);int t = LCA(st,ed);add[st].push_back({0,dep[st]}),del[fa[t][0]].push_back({0,dep[st]});add[ed].push_back({1,dep[st] - 2 * dep[t]}),del[t].push_back({1,dep[st] - 2 * dep[t]});}dfs(1,0);for (int i = 1;i <= n;i ++) cout << ans[i] << ' ';return 0;
}