题目传送门
前置知识：树上差分
各位大佬们肯定知道在数组上差分是什么吧：差分数组中的值是原数组中这个位置与它左边（或右边，写法无所谓）位置的差。这个方法可以把“区间加”转化为“左端点加，右端点减”。
然后对于一个位置，它的值就是差分数组中的前缀和。
例如：一个数组 [1,0,2,5,3]。
它的差分数组就是 [1,−1,2,3,−2] 。
在区间 [2,4] 上 +1 ，就等价于在差分数组中下标为 2 的地方 +1 ，下标为 5 的地方 −1 。差分数组变为 [1,0,2,3,−3]。
此时求原数组下标为 4 的地方就是求差分数组的下标范围 [1,4] 的和，为 6 。
类似地，我们可以把差分这个算法转化到树上。
设差分数组为 b ，对于树上的一个路径加 1 ，例如 u→v 这条路径上面所有点的权值 +1 ，我们可以把它转化成 b[u] 加 1 ，b[v] 加 1 ，b[lca(u,v)] 减 1 ， b[fa[lca(u,v)]] 减 1 。最后对于一个点上的权值，我们求这个点的差分数组的子树和就可以了。
正文
《算法竞赛进阶指南》大法好！
首先对于每个玩家的跑步路线，我们把它拆成两段： Si→lca(Si,Ti) 和 lca(Si,Ti)→Ti（不包括 lca(Si,Ti) ）。
然后分开考虑：
- 若一个观察员 x 处在 Si 到 lca(Si,Ti) 的路径上，当且仅当 deep[Si]−deep[x]=w[x] 时，这个观察员可以观察到这个玩家 i 。其中 deep 数组表示节点的深度。
- 若一个观察员 x 处在 lca(Si,Ti) 到 Ti 的路径上，当且仅当 deep[Si]+deep[x]−2×deep[lca(Si,Ti)]=w[x] 时，这个观察员可以观察到这个玩家 i 。
对于情况一，把关于 x 的项都移到等式右边，得到 deep[Si]=deep[x]+w[x] 时，这个玩家可以被位于点 x 的观察员观察到。
那么这种情况就转化为：每一个玩家在 Si 到 lca(Si,Ti) 的路径上放一个类型为 deep[Si] 的物品。最后求任意 x 处的类型为 deep[x]+w[x] 的物品有多少个。
看到这里，就知道可以用树上差分了！
“路径 u→v 上放类型为 k 的物品”可以转化为：在 u 处产生一个物品 k ， v 处也产生一个物品 k ，在 fa[lca(u,v)] 处减去两个物品 k 。然后对于一个点上拥有的物品，我们求这个点的子树中所有的物品即可。
情况二类似，请读者自行推导（或者看《算法竞赛进阶指南》中的结果，只要你有）。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define grep(u) for(int ptr=last[u];ptr;ptr=pre[ptr])
using namespace std;
const int N=6e5+5,LOGMAX=20;
int n,m,s[N],t[N],w[N];
int target[2*N],pre[2*N],last[N],tot=0;
void add(int u,int v) {
target[++tot]=v;
pre[tot]=last[u];
last[u]=tot;
}
int deep[N],bel[N][LOGMAX];
void dfs(int u,int fa) {
deep[u]=deep[fa]+1;
bel[u][0]=fa;
rep(i,1,LOGMAX-1) {
bel[u][i]=bel[bel[u][i-1]][i-1];
}
grep(u) if(target[ptr]!=fa) dfs(target[ptr],u);
}
vector<int> bok1[N],bok2[N];
int query(int u,int v) {
if(deep[u]<deep[v]) swap(u,v);
per(i,LOGMAX-1,0)
if(deep[bel[u][i]]>=deep[v]) u=bel[u][i];
if(u==v) return u;
per(i,LOGMAX-1,0)
if(bel[u][i]!=bel[v][i]) u=bel[u][i],v=bel[v][i];
return bel[u][0];
}
int c[N*2],sum[N];
void dfs1(int u,int fa) {
int now=c[w[u]+deep[u]];
for(vector<int>::iterator ii=bok1[u].begin();ii!=bok1[u].end();++ii) ++c[*ii];
for(vector<int>::iterator ii=bok2[u].begin();ii!=bok2[u].end();++ii) --c[*ii];
grep(u) if(target[ptr]!=fa) dfs1(target[ptr],u);
int ans=c[w[u]+deep[u]]-now;
sum[u]+=ans;
}
void dfs2(int u,int fa) {
int now=c[w[u]-deep[u]];
for(vector<int>::iterator ii=bok1[u].begin();ii!=bok1[u].end();++ii) ++c[*ii];
for(vector<int>::iterator ii=bok2[u].begin();ii!=bok2[u].end();++ii) --c[*ii];
grep(u) if(target[ptr]!=fa) dfs2(target[ptr],u);
int ans=c[w[u]-deep[u]]-now;
sum[u]+=ans;
}
int main(){
scanf("%d%d",&n,&m);
rep(i,1,n-1) {
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1,0);
rep(i,1,n) scanf("%d",&w[i]);
rep(i,1,m) {
scanf("%d%d",&s[i],&t[i]);
int lca=query(s[i],t[i]);
bok1[s[i]].push_back(deep[s[i]]);
bok2[bel[lca][0]].push_back(deep[s[i]]);
}
dfs1(1,0);
memset(c,0,sizeof(c));
rep(i,1,n) bok1[i].clear(),bok2[i].clear();
rep(i,1,m) {
int lca=query(s[i],t[i]);
bok1[t[i]].push_back(deep[s[i]]-2*deep[lca]);
bok2[lca].push_back(deep[s[i]]-2*deep[lca]);
}
dfs2(1,0);
rep(i,1,n) printf("%d ",sum[i]);
return 0;
}
|