题意简化

一棵树上有 $m$ 个玩家从起点 $s_i$ 跑到终点 $t_i$，每个节点 $j$ 的观察员在 $w_j$ 秒出现，求每个观察员能看到的玩家数量。

基本思路：LCA+树上差分

我们将第 $i$ 条路径 $s_i \rightarrow t_i$ 分解为 $s_i \rightarrow \text{LCA}(s_i, t_i)$ 和 $\text{LCA}(s_i, t_i) \rightarrow t_i$，便于求解。

求解路径 1

对于 $s_i \rightarrow \text{LCA}(s_i, t_i)$ 的路径，玩家 $i$ 在节点 $u$ 能被观察到当且仅当 $dep_{s_i} - dep_u = w_u$。

移项得 $dep_{s_i} = w_u + dep_u$，相当于路径上每个节点加一个 $dep_{s_i}$ 的值，统计每一个节点 $u$ 上 $w_u + dep_u$ 的数量。

记 $cnt_{0, w_u + dep_u}$ 为这个值的数量，我们在端点 $s_i$ 和 $\text{LCA}(s_i, t_i)$ 处树上差分一个 $dep_{s_i}$ 的值，dfs 遍历整棵树，每访问到一个节点 $u$，先记录先前的 $cnt_{0, w_u + dep_u}$ 的值，再统计 $u$ 端点处对答案的贡献，统计后的 $cnt_{0, w_u + dep_u}$ 减去先前的值就是节点 $u$ 的答案。

求解路径 2

对于 $\text{LCA}(s_i, t_i) \rightarrow t_i$ 的路径，玩家 $i$ 在节点 $u$ 能被观察到当且仅当 $dep_{s_i} + dep_u - 2 \times dep_{\text{LCA}(s_i, t_i)} = w_u$。

移项得 $dep_{s_i} - 2 \times dep_{\text{LCA}(s_i, t_i)} = w_u - dep_u$，相当于路径上每一个节点加一个 $dep_{s_i} - 2 \times dep_{\text{LCA}(s_i, t_i)}$ 的值，统计每一个节点 $u$ 上 $w_u - dep_u$ 的数量。

记 $cnt_{1, w_u - dep_u}$ 为这个值的数量，我们在端点 $s_i$ 和 $\text{LCA}(s_i, t_i)$ 处树上差分一个 $dep_{s_i} - 2 \times dep_{\text{LCA}(s_i, t_i)}$ 的值，dfs 遍历整棵树，每访问到一个节点 $u$，先记录先前的 $cnt_{1, w_u - dep_u}$ 的值，再统计 $u$ 端点处对答案的贡献，统计后的 $cnt_{1, w_u - dep_u}$ 减去先前的值就是节点 $u$ 的答案。

AC Code

/*
起点 s 终点 t
对于左路径上的点 x
dep[s]-dep[x]==w[x] => dep[s]==w[x]+dep[x]
对于右路径上的点 y
dep[s]+dep[y]-2*dep[lca(s,y)]==w[y] => dep[s]-2*dep[lca(s,y)]==w[y]-dep[y]
*/
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define pii pair <int, int>
#define mkpr make_pair
#define fi first
#define se second
using namespace std;
const int N = 3e5 + 5, D = 3e5;
int n, m, w[N], d[N], f[N][25], c[2][N<<1], ans[N], dep[N];
vector <int> g[N];
vector <pii> add[N], del[N];
struct path {int u, v;} p[N];
void Dfs(int u, int p) {
	f[u][0] = p;
	dep[u] = dep[p] + 1;
	for (int v : g[u]) {
		if (v == p) continue ;
		Dfs(v, u);
	}
}
void InitLCA() {
	for (int j = 1; j <= 21; j++) {
		for (int i = 1; i <= n; i++) {
			f[i][j] = f[f[i][j-1]][j-1];
		}
	}
}
int LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = 21; i >= 0; i--) if (dep[f[u][i]] >= dep[v]) u = f[u][i];
	if (u == v) return u;
	for (int i = 21; i >= 0; i--) if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
	return f[u][0];
}
void Dfs2(int u) {
	int pre1 = c[0][w[u]+dep[u]+D], pre2 = c[1][w[u]-dep[u]+D]; // 计算先前答案
	for (pii cur : add[u]) ++c[cur.fi][cur.se+D];
	for (pii cur : del[u]) --c[cur.fi][cur.se+D];
	for (int v : g[u]) {
		if (v == f[u][0]) continue ;
		Dfs2(v);
	}
	ans[u] = c[0][w[u]+dep[u]+D] - pre1 + c[1][w[u]-dep[u]+D] - pre2;
}
void Solve() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		g[u].pb(v), g[v].pb(u);
	}
	for (int i = 1; i <= n; i++) cin >> w[i];
	Dfs(1, 0); InitLCA();
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		int lc = LCA(u, v);
		add[u].pb(mkpr(0, dep[u])), del[f[lc][0]].pb(mkpr(0, dep[u]));
		add[v].pb(mkpr(1, dep[u]-2*dep[lc])), del[lc].pb(mkpr(1, dep[u]-2*dep[lc]));
	}
	Dfs2(1);
	for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	Solve();
	return 0;
}

C69 线段树合并+树上差分 P1600 [NOIP2016 提高组] 天天爱跑步

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
vector<int>G[N];
int n,D,f[N][20],dep[N];
void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	f[x][0]=fa;for(int i=1;i<=D;i++) f[x][i]=f[f[x][i-1]][i-1];
	for(auto y:G[x])if(y!=fa)dfs(y,x);
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=D;i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=D;i>=0;i--)if( f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
int w[N],ans[N];
vector<pair<int,int>>g1[N],g2[N];
int c1[N<<1],c2[N<<1];
void dfs2(int x,int fa)
{
	int t1=c1[dep[x]+w[x]],t2=c2[w[x]-dep[x]+n];

	for(auto y:G[x])if(y!=fa)dfs2(y,x);

	for(auto i:g1[x]) c1[i.first]+=i.second;
	for(auto i:g2[x]) c2[i.first]+=i.second;

	ans[x]+= c1[dep[x]+w[x]]-t1 + c2[w[x]-dep[x]+n]-t2;
}
int main()
{
	int m;scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
	dep[0]=0;D=log2(n);dfs(1,0);
	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
	memset(g1,0,sizeof(g1));memset(g2,0,sizeof(g2));
	memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2));
    /*
    设si和ti的最近公共祖先为p
    1、当x在si和p之间时，有 dep[si]-dep[x]=w[x] -> dep[si]=dep[x]+w[x]，即只要贡献 c1[dep[si]] ，然后用 c1[dep[x]+w[x]]检测即可。
    2、当x在p和ti之间时，有 dep[si]-dep[p]+dep[x]-dep[p]=w[x] -> dep[si] - 2*dep[p] =w[x]-dep[x]，即只要贡献 c2[dep[si]-2*dep[p]+n] ，然后用 c2[dep[x]+w[x]+n]检测即可。
    */
	for(int i=1,si,ti;i<=m;i++)
	{
		scanf("%d%d",&si,&ti);
		int p=lca(si,ti),fp=f[p][0];
		g1[si].push_back({dep[si],1});
		g1[p].push_back({dep[si],-1});
		g2[ti].push_back({dep[si]-2*dep[p]+n,1});
		g2[fp].push_back({dep[si]-2*dep[p]+n,-1});
	}
	memset(ans,0,sizeof(ans));
	dfs2(1,0);
	for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf("\n");
	return 0;
}