魔鬼题面
题解：
LCA + 树上差分。对于一次询问u到v，我们可以拆成两段，一段为u到LCA，一段为LCA到v。
先考虑u到LCA，即从下到上的情况。对于在i点的观察员，只有深度在Depth[i] + W[i]的点才可能对i点有贡献，这个贡献在LCA点结束。那么利用差分思想，我们在Depth[i] + W[i]的点打上标记，在LCA处减去标记，则u到LCA这一段就有了1的贡献。当我们DFS到一个节点x时，需要求的答案是x子树中节点的贡献，即回溯完成后标记数组的变化量，我们在递归前保存一下初始值，去子树逛一圈后得到新的值，用新的值减去旧的就是变化量了。
那么LCA到v的情况与上述情况相反，即从上往下，但思想是一样的，因为Depth[i] - W[i]可能为负数，我们需要加上一个相同的偏移量防止程序运行错误。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<climits>
#include<cmath>
#define MAXA 1000005
using namespace std;
int Head[MAXA],cnt;
struct Rx_Graph {
int next,to;
}Edge[MAXA];
struct Rx {
int Type,Val,Flag;
};
vector<Rx> Gx[MAXA];
Rx Make(int a,int b,int c) {
Rx Ret;
Ret.Type = a;
Ret.Val = b;
Ret.Flag = c;
return Ret;
}
void Add(int u,int v) {
Edge[++cnt].next = Head[u];
Edge[cnt].to = v;
Head[u] = cnt;
}
int Depth[MAXA],f[MAXA][20],Py = 30000;
int LCA(int x,int y) {
if(Depth[y] > Depth[x])
swap(x,y);
for(int i=18;i>=0;i--)
if(Depth[f[x][i]] >= Depth[y])
x = f[x][i];
if(x == y) return x;
for(int i=18;i>=0;i--)
if(f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
return f[x][0];
}
void Init(int x,int Last) {
for(int i=Head[x];i;i=Edge[i].next) {
int y = Edge[i].to;
if(y == Last) continue;
Depth[y] = Depth[x] + 1;
f[y][0] = x;
Init(y,x);
}
}
void Chafen(int u,int v) {
int Lca = LCA(u,v),Len = Depth[u] + Depth[v] - Depth[Lca] * 2;
Gx[u].push_back(Make(1,Depth[u],1));
Gx[v].push_back(Make(2,Depth[v] - Len + Py,1));
Gx[Lca].push_back(Make(1,Depth[u],-1));
Gx[f[Lca][0]].push_back((Make(2,Depth[v] - Len + Py,-1)));
}
int n,m,u,v,CheckTime[MAXA],Start,Target,Cnt1[MAXA],Cnt2[MAXA],Ans[MAXA];
void DFS(int x,int Last) {
int Now = Cnt1[CheckTime[x] + Depth[x]] + Cnt2[Depth[x] - CheckTime[x] + Py];
for(int i=0;i<Gx[x].size();i++) {
if(Gx[x][i].Type == 1)
Cnt1[Gx[x][i].Val] += Gx[x][i].Flag;
else Cnt2[Gx[x][i].Val] += Gx[x][i].Flag;
}
for(int i=Head[x];i;i=Edge[i].next) {
int y = Edge[i].to;
if(y == Last) continue;
DFS(y,x);
}
Ans[x] = Cnt1[CheckTime[x] + Depth[x]] + Cnt2[Depth[x] - CheckTime[x] + Py] - Now;
}
int main() {
scanf("%d %d",&n,&m);
for(int i=1;i<n;i++) {
scanf("%d %d",&u,&v);
Add(u,v);
Add(v,u);
}
for(int i=1;i<=n;i++)
scanf("%d",&CheckTime[i]);
Depth[1] = 1;
Init(1,0);
for(int j=1;j<=18;j++)
for(int i=1;i<=n;i++)
f[i][j] = f[f[i][j-1]][j-1];
for(int i=1;i<=m;i++) {
scanf("%d %d",&Start,&Target);
Chafen(Start,Target);
}
DFS(1,0);
for(int i=1;i<=n;i++)
printf("%d ",Ans[i]);
}
