Orz
by SKTelecomT1_Faker @ 2020-02-17 21:00:45
@[IAMAKER](/user/189012) ZRR loves U (She told me herself)
by YellowBean_Elsa @ 2020-02-17 21:02:48
@[YellowBean](/user/104292) That's irreevant to me.
by SKTelecomT1_Faker @ 2020-02-17 21:04:01
@[IAMAKER](/user/189012) correction: irrelevant
by YellowBean_Elsa @ 2020-02-17 21:05:16
@[YellowBean](/user/104292)
你开桶怎么算
我觉得最优应该是线段树合并
by Smile_Cindy @ 2020-02-17 21:05:17
@[Alpha](/user/87058) 开桶不是两遍 $O(N)$ 的dfs就水过去了吗
by YellowBean_Elsa @ 2020-02-17 21:06:19
@[YellowBean](/user/104292) My hand slipped
by SKTelecomT1_Faker @ 2020-02-17 21:06:48
@[Alpha](/user/87058) 树上差分
by mrsrz @ 2020-02-17 21:07:03
我写的，这是 $O((N+M)logN)$ 但主要是把时间浪费在 LCA 和 map 上了（应该用 Tarjan 求 LCA，map 换成 vector）
```cpp
//coder: Feliks a Hacker of IOI == GM-YB an AKer of IMO
#include<bits/stdc++.h>
using namespace std;
const int N=320005;
int n,m;
inline int read(){
int x=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x;
}int v[N<<1],nex[N<<1],first[N],tot;
queue<int> q;
int d[N],fa[21][N],T;
inline void adde(int x,int y){
v[++tot]=y;
nex[tot]=first[x];
first[x]=tot;
}namespace LCA{
inline void bfs(){
q.push(1);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=first[x];i;i=nex[i]){
int y=v[i];if(d[y])continue;
d[y]=d[x]+1;q.push(y);fa[0][y]=x;
for(int j=1;j<=T;j++)
fa[j][y]=fa[j-1][fa[j-1][y]];
}
}
}inline int lca(int x,int y){
if(x==y)return x;
if(d[x]<d[y])swap(x,y);
//d[x] > d[y]
for(int i=T;i>=0;i--)
if(d[fa[i][x]]>=d[y])x=fa[i][x];
if(x==y)return x;
for(int i=T;i>=0;i--)
if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
}using namespace LCA;
int w[N],cn[N],s[N],t[N],cm[N],ap[N<<1];
map<int,int> cf[N];
int ans[N];
void dfs(int x,int f){
int cnt=ap[cn[x]];
for(map<int,int>::iterator it=cf[x].begin();it!=cf[x].end();it++)
ap[(*it).first]+=(*it).second;
for(int i=first[x];i;i=nex[i]){
int y=v[i];if(y==f)continue;
dfs(y,x);
}ans[x]+=ap[cn[x]]-cnt;
}
int main(){
n=read(),m=read();
T=(int)(log(n)/log(2.0))+1;
for(int i=1;i<n;i++){
int x=read(),y=read();
adde(x,y),adde(y,x);
}d[1]=1;bfs();
for(int i=1;i<=n;i++)w[i]=read(),cn[i]=d[i]+w[i];
for(int i=1;i<=m;i++){
s[i]=read(),t[i]=read();
int p=lca(s[i],t[i]);
cf[s[i]][d[s[i]]]++;
cf[fa[0][p]][d[s[i]]]--;
}dfs(1,0);
for(int i=1;i<=n;i++)cn[i]=w[i]-d[i]+n,cf[i].clear();
for(int i=1;i<=m;i++){
int p=lca(s[i],t[i]),x=d[s[i]]-(d[p]<<1)+n;
cf[t[i]][x]++;
cf[p][x]--;
}dfs(1,0);
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}
```
by YellowBean_Elsa @ 2020-02-17 21:08:18
准确来说，还是要带 $\log$，因为几乎没有人并查集写的是真的反阿克曼函数，都是写的一个log的并查集
by 皎月半洒花 @ 2020-02-17 21:11:04