洛谷1600 天天爱跑步 (树上差分)

题目链接：https://www.luogu.com.cn/problem/P1600

参考题解:https://www.cnblogs.com/lfyzoi/p/10221884.html

转换思路，枚举每个观察员，统计有哪些运动员会给观察员做贡献。因为给观察员做贡献的运动员都在观察员的子树内，所以 (dfs) 统计即可。对于一条运动员路径，可以拆成从出发结点 (u) 到 (lca) 的路径和从 (lca) 的终点 (v) 的路径。

其中处在上行路径上的观察员 (P)，如果能观察到这个运动员，那么要满足

[dep[P]+w[P] = dep[u] ]

下行路径上观察员要观察到该运动员要满足

[w[P]-dep[P]=dis(u,v)-dep[v] ]

开一个桶，每个观察员分别对应一个桶中元素。在 (dfs) 枚举观察员时，同时统计当前节点作为运动员会对哪些观察员产生贡献，在桶中对应元素加上即可。统计完当前观察员，还要减去多余的贡献。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii; 

const int maxn = 300010;

int n, m;
int w[maxn];
int ath[maxn]; // i 出发的路径数量 
int st[maxn], ed[maxn], di[maxn];

vector<int> lu[maxn]; // 以 i 为 lca 的链
vector<int> fr[maxn]; // 以 i 为终点的链 

int h[maxn], cnt = 0;
struct E{
	int to, next;
}e[maxn << 1];
void add(int u, int v){
	e[++cnt].to = v;
	e[cnt].next = h[u];
	h[u] = cnt;
}

int fa[maxn][28], dep[maxn];
void dfs(int u, int par){
	fa[u][0] = par;
	dep[u] = dep[par] + 1;
	
	for(int i = 1 ; i <= 25 ; ++i){
		fa[u][i] = fa[fa[u][i-1]][i-1];
	}
	
	for(int i = h[u] ; i != -1 ; i = e[i].next){
		int v = e[i].to;
		if(v == par) continue;
		dfs(v, u);
	}
}

int LCA(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = 25 ; i >= 0 ; --i){
		if(dep[fa[u][i]] >= dep[v]){
			u = fa[u][i];
		}
	}
	if(u == v) return u;
	for(int i = 25 ; i >= 0 ; --i){
		if(fa[u][i] != fa[v][i]){
			u = fa[u][i], v = fa[v][i];
		}
	}
	return fa[u][0];
}

int ans[maxn];
int buc1[maxn << 1], buc2[maxn + maxn + 10000]; // buc2 偏移 

void solve(int u, int par){
	int tmp1 = buc1[dep[u] + w[u]], tmp2 = buc2[w[u] - dep[u] + maxn];
	for(int i = h[u] ; i != -1 ; i = e[i].next){
		int v = e[i].to;
		if(v == par) continue;
		solve(v, u);
	}
	
	buc1[dep[u]] += ath[u]; // 以 u 为起点的路径做的贡献
	for(int i = 0 ; i < fr[u].size() ; ++i){ // 以 u 为终点的路径做的贡献 
		buc2[di[fr[u][i]] - dep[ed[fr[u][i]]] + maxn]++;
	}
	
	ans[u] += buc1[dep[u] + w[u]] - tmp1 + buc2[w[u] - dep[u] + maxn] - tmp2; // 统计答案
	
	// 删除以 u 为 lca 的路径的答案
	for(int i = 0 ; i < lu[u].size() ; ++i){
		int num = lu[u][i];
		buc1[dep[st[num]]]--;
		buc2[di[num] - dep[ed[num]] + maxn]--;
	} 
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	memset(h, -1, sizeof(h));
	
	n = read(), m = read();
	
	int u, v;
	for(int i = 1 ; i <= n - 1 ; ++i){
		u = read(), v = read();
		add(u, v); add(v, u);
	}
	
	dfs(1, 0);	
		
	for(int i = 1 ; i <= n ; ++i) w[i] = read();

	for(int i = 1 ; i <= m ; ++i) {
		st[i] = read(), ed[i] = read();
		
		++ath[st[i]];
		fr[ed[i]].push_back(i); 
		int lca = LCA(st[i], ed[i]);
		lu[lca].push_back(i);
		di[i] = dep[st[i]] + dep[ed[i]] - 2 * dep[lca];	
		if(dep[lca] + w[lca] == dep[st[i]]) ans[lca]--; // 没有折线的路径会重复统计 
	}
	
	solve(1, 0);
	
	for(int i = 1 ; i <= n ; ++i) printf("%d ", ans[i]); printf("
");
	
	return 0;
}