E. Lomsat gelral
注意答案会爆int
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define LL long long
LL w[N];//w
int n,q;
vector<int> g[N];
vector<int>qr[N];
LL ans[N];
map<int,int>cnt[N];//第一维深度,第二维点权,第三维记录是否存在
int son[N],sz[N];//重儿子
int L[N],R[N],dfn,id[N],dep[N];
void dfs1(int u,int fa){
son[u]=1;
L[u]=++dfn;
id[dfn]=u;
for(auto v:g[u]){
if(v==fa) continue;
dfs1(v,u);
son[u]+=son[v];
if(son[v]>son[sz[u]]) sz[u]=v;
}
R[u]=dfn;
}
LL color[N],bigcol,sum;
void add(int col){
color[col]++;
if(color[col]==bigcol) sum+=col;
if(color[col]>bigcol) sum=col,bigcol=color[col];
}
void del(int col){
color[col]--;
}
void dfs2(int u,int fa,bool op){
for(int v:g[u]){
if(v==fa||v==sz[u]) continue;
dfs2(v,u,false);
}
if(sz[u]){
dfs2(sz[u],u,true);
}
for(int v:g[u]){
if(v==fa||v==sz[u]) continue;
for(int i=L[v];i<=R[v];i++){
add(w[id[i]]);
}
}
add(w[u]);
ans[u]=sum;
if(!op){//清空轻子树的贡献
for(int i=L[u];i<=R[u];i++){
del(w[id[i]]);
}
sum=bigcol=0;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(1,0);
dfs2(1,0,false);
for(int i=1;i<=n;i++){
cout<<ans[i]<<' ';
}
return 0;
}