天天放毒...
首先介绍一个树上差分。
每次进入的时候记录贡献，跟出来的时候的差值就是子树贡献。
然后就可以做了。
发现考虑每个人的贡献有困难。
于是考虑每个观察员的答案。
把路径拆成两条，以lca分开。x -> z -> y，完全分成A，B两部分。
那么A：d[x] = w[z] + d[z];B：len - d[y] + N = w[z] - d[z] + N;
这里+ N是为了防止负数。
然后发现右边只跟z有关，这里的z可以是路径上任一点。
那么对于每个人，把需要树上差分统计的左边数值用vector记录。
然后跑一遍统计即可。
注意：如果lca能观测到这条路径，那么--，因为测了A，B两次。
看代码。
#include <cstdio>
#include <vector> const int N = ; inline void read(int &x) {
x = ;
char c = getchar();
while(c < '' || c > '') {
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
} struct Edge {
int v, nex;
}edge[N << ]; int top; int n, m, e[N], w[N], binA[N << ], binB[N << ], cancel[N], d[N], fa[N][], lm, ans[N];
std::vector<int> vA[N], vB[N], vA_[N], vB_[N]; inline void add(int x, int y) {
edge[++top].v = y;
edge[top].nex = e[x];
e[x] = top;
return;
} void DFS1(int x, int f) {
fa[x][] = f;
d[x] = d[f] + ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y != f) {
DFS1(y, x);
}
}
return;
} inline void getlca() {
DFS1(, );
while(( << lm) < n) {
lm++;
}
for(int i = ; i <= lm; i++) {
for(int x = ; x <= n; x++) {
fa[x][i] = fa[fa[x][i - ]][i - ];
}
}
return;
} inline int lca(int x, int y) {
int t = lm;
while(d[x] > d[y]) {
std::swap(x, y);
}
while(t > - && d[y] > d[x]) {
if(d[fa[y][t]] >= d[x]) {
y = fa[y][t];
}
t--;
}
if(x == y) {
return x;
}
t = lm;
while(t > - && fa[x][] != fa[y][]) {
if(fa[x][t] != fa[y][t]) {
x = fa[x][t];
y = fa[y][t];
}
t--;
}
return fa[x][];
} void DFS(int x) {
int A = binA[w[x] + d[x]];
int B = binB[w[x] - d[x] + N];
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y != fa[x][]) {
DFS(y);
}
}
for(int i = ; i < vA[x].size(); i++) {
binA[vA[x][i]]++;
}
for(int i = ; i < vB[x].size(); i++) {
binB[vB[x][i]]++;
}
ans[x] += binA[w[x] + d[x]] - A;
ans[x] += binB[w[x] - d[x] + N] - B;
for(int i = ; i < vA_[x].size(); i++) {
binA[vA_[x][i]]--;
}
for(int i = ; i < vB_[x].size(); i++) {
binB[vB_[x][i]]--;
}
return;
} int main() {
read(n);
read(m);
int x, y, z;
for(int i = ; i < n; i++) {
read(x);
read(y);
add(x, y);
add(y, x);
}
for(int i = ; i <= n; i++) {
read(w[i]);
}
getlca();
for(int i = ; i <= m; i++) {
read(x);
read(y);
z = lca(x, y);
vA[x].push_back(d[x]); //d[x] = w[z] + d[z];
vA_[z].push_back(d[x]); //
int len = d[x] + d[y] - * d[z];
vB[y].push_back(len - d[y] + N); //len - d[y] + N = w[z] - d[z] + N;
vB_[z].push_back(len - d[y] + N);
if(d[x] == w[z] + d[z]) {
cancel[z]++;
}
} DFS(); for(int i = ; i <= n; i++) {
printf("%d ", ans[i] - cancel[i]);
}
/*puts("");
for(int i = 1; i < N * 2; i++) {
if(binB[i]) {
printf("binB[%d] = %d\n", i, binB[i]);
}
if(binA[i]) {
printf("binA[%d] = %d\n", i, binA[i]);
}
}
printf("over");*/ return ;
}
AC代码
zbtrs大佬用主席树A了，还说显然是主席树，太强了%%%