¶凉笙 @ 2021-06-11 17:29:07
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
}
return fl?-x:x;
}
const int maxn = 3e5 + 10;
int head[maxn],cnt=0;
struct edge{
int to,nxt;
}e[maxn<<1];
inline void link(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
#include <vector>
#define maxlog 23
int n,m;
vector <int> add1[maxn],add2[maxn],del1[maxn],del2[maxn];
int de[maxn],f[maxn][23];
void dfs(int u,int fa){
de[u]=de[fa]+1;f[u][0]=fa;
for(int i=1;i<maxlog;i++)f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
}
}
int getlca(int x,int y){
if(de[x]<de[y])swap(x,y);
for(int i=maxlog-1;i>=0;i--){
if(de[f[x][i]]>=de[y])x=f[x][i];
}
if(x==y)return x;
for(int i=maxlog-1;i>=0;i--)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
int w[maxn],t1[maxn],t2[maxn],ans[maxn];//从下往上 and 从上往下
void solve(int u,int fa){
int v1=t1[w[u]+de[u]],v2=t2[w[u]-de[u]+n];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
solve(v,u);
}
for(vector<int>::iterator it=add1[u].begin();it!=add1[u].end();it++)t1[*it]++;
for(vector<int>::iterator it=del1[u].begin();it!=del1[u].end();it++)t1[*it]--;
for(vector<int>::iterator it=add2[u].begin();it!=add2[u].end();it++)t2[*it]++;
for(vector<int>::iterator it=del2[u].begin();it!=del2[u].end();it++)t2[*it]--;
ans[u]+=t1[w[u]+de[u]]-v1+t2[w[u]-de[u]+n]-v2;
}
#define read() read<int>()
#define Debug(x) cerr<<(x)<<endl
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
n=read();m=read();
for(int i=1;i<n;i++){
int u=read(),v=read();link(u,v),link(v,u);
}
for(int i=1;i<=n;i++)w[i]=read();
de[0]=0;
dfs(1,0);
for(int i=1;i<=m;i++){
int s=read(),t=read();
int LCA=getlca(s,t);
//Debug(LCA);//
add1[s].push_back(de[s]);
add2[t].push_back(de[s]-2*de[LCA]+n);//细节+n
del1[LCA].push_back(de[s]);
del2[f[LCA][0]].push_back(de[s]-2*de[LCA]+n);
}
solve(1,0);
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
puts("");
return 0;
}
by zhuoz @ 2021-06-11 18:03:02
@¶凉笙 你跟我微信头像一样耶!!!