题目链接

$\sout{虽然确实用dfn序计算贡献比递归调用好写也不饶，但谁让我是犟种呢}$

题目大意就是说每个点$i$有个观察员，会在$w_i$时刻观察,有$m$条路径，人沿路径跑，只有在$w_i$那一时刻人刚好到那里才会让答案$+1$,问每个点的答案

思路:
也是学别人知道可以用$DSUonTree$做的,考虑对于一个点$x$，哪些情况会对答案有贡献，必要条件显然得是，某一条路径的起点或者终点在以$x$为根的子树里面，然后还有刚好在$w_x$时刻跑到$x$的限制.

我们分两种情况考虑:
$1.$起点在以$x$为根的子树里面
$2.$终点在以$x$为根的子树里面

对于情况一，可以看成是与$x$深度差为$w_x$的点
对于情况二，显然要满足$$路径长度-深度差=w_x$$
写成方程类似于$len-(de{p}_y-de{p}_x)=w_x$
其中y是终点,$len$是路径长度

移项一下可以得到$$len-de{p}_y=de{p}_x+w_x$$
左式和右式都只与自身有关.小trick来了,可以开两个桶解决，每次计算询问对应桶的值即可

一些细节:
路径会被计算两遍,如果是以x为起点和终点的$lca$的话,要去重，记录一下以x为$lca$的路径即可

最重要的是，以$x$为$lca$的路径对上面的节点是没有贡献的，要删除它们

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;const int maxn = 3e5+10;
const int base = 3e5+1;//偏移量，防止索引是负的
int n,m;
int w[maxn],ans[maxn],s[maxn],t[maxn],len[maxn];//len是路径长度
int f[maxn][25],sz[maxn],son[maxn],HH,l[maxn],dep[maxn];
int cnt0[maxn<<1],cnt1[maxn<<1];//桶，如果开map就可以不用偏移量了
vector<int>mark[maxn];//mark[i],以i为lca的路径
vector<int>g[maxn],ed[maxn],st[maxn];//树,以i为起点的路径st[i]，以i为终点的路径ed[i]void dfs(int x,int fa){sz[x]=1;f[x][0]=fa;dep[x] = dep[fa]+1;for(int i = 1;i<25;++i) f[x][i] = f[f[x][i-1]][i-1];for(auto y:g[x]){if(y==fa) continue;dfs(y,x);sz[x]+=sz[y];if(sz[y]>sz[son[x]]) son[x]=y;}
}int lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i = 24;i>=0;--i){if(dep[f[x][i]]>=dep[y]) x = f[x][i];}if(x==y) return x;for(int i = 24;i>=0;--i){if(f[x][i]!=f[y][i]){x = f[x][i];y = f[y][i];}}return f[x][0];
}void calc(int x,int fa,bool op,int root){if(op){for(auto p:st[x]){if(dep[l[p]]<=dep[root]) ++cnt0[dep[x]];}for(auto p:ed[x]){if(dep[l[p]]<=dep[root]) ++cnt1[len[p]-dep[x]+base];}}else{for(auto p:st[x]){if(dep[l[p]]<=dep[root]) --cnt0[dep[x]];}for(auto p:ed[x]){if(dep[l[p]]<=dep[root]) --cnt1[len[p]-dep[x]+base];}}for(auto y:g[x]){if(y==fa||y==HH) continue;calc(y,x,op,root);}
}void del(int x, bool flag) {for(auto p : mark[x]) {if(dep[s[p]] == dep[x] + w[x]) ans[x] --;//把重复计算的删掉if(flag) cnt0[dep[s[p]]] --, cnt1[len[p] - dep[t[p]] + base] --;//只有当x是重儿子时才删,因为若x是轻儿子在下面就会被清空了}
}void dsu(int x,int fa,bool op){for(auto y:g[x]){if(y==fa||y==son[x]) continue;dsu(y,x,0);}if(son[x]) dsu(son[x],x,1),HH=son[x];calc(x,fa,1,x);HH=0;ans[x] += cnt0[dep[x] + w[x]] + cnt1[w[x] - dep[x] + base];del(x,op);//把lca为x的路径贡献删掉，因为它不会对上面有贡献if(!op) calc(x,fa,0,x);
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i = 1;i<n;++i){int x,y;cin>>x>>y;g[x].emplace_back(y);g[y].emplace_back(x);}for(int i = 1;i<=n;++i) cin>>w[i];dfs(1,0);for(int i = 1;i<=m;++i){cin>>s[i]>>t[i];l[i] = lca(s[i],t[i]);//l[i]是lcalen[i] = dep[s[i]]+dep[t[i]]-2*dep[l[i]];mark[l[i]].emplace_back(i);ed[t[i]].emplace_back(i);st[s[i]].emplace_back(i);}dsu(1,0,0);for(int i = 1;i<=n;++i) cout<<ans[i]<<" ";cout<<"\n";return 0;
}