Untitled
unknown
c_cpp
a year ago
1.1 kB
3
Indexable
#include <bits/stdc++.h> #define eps 1e-16 #define M_PI 3.141592653589793 #define bs 1000000007 #define bsize 512 const int N = 200005; using namespace std; int n; int c[N]; map<int, int> S[N]; int w[N]; int used[N]; int mx[N]; long long cnt[N]; vector<int> g[N]; long long ans[N]; void run_merge(int a,int b) { if (S[w[a]].size()<S[w[b]].size()) swap(w[a],w[b]); int id=w[a]; map<int, int>::iterator it; for (it=S[w[b]].begin();it!=S[w[b]].end();it++) { int val=(*it).first; int amount=(*it).second; S[id][val]+=amount; if (S[id][val]>mx[id]) { mx[id]=S[id][val]; cnt[id]=0; } if (S[id][val]==mx[id]) cnt[id]+=val; } } void dfs(int v) { used[v]=1; for (int i=0;i<g[v].size();i++) { int to=g[v][i]; if (used[to]) continue; dfs(to); run_merge(v,to); } ans[v]=cnt[w[v]]; } int main(){ cin>>n; for (int i=1;i<=n;i++) { cin>>c[i]; S[i][c[i]]=1; w[i]=i; mx[i]=1; cnt[i]=c[i]; } for (int i=1;i<n;i++) { int a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } dfs(1); for (int i=1;i<=n;i++) { if (i>1) cout<<" "; cout<<ans[i]; } cout<<endl; return 0; }
Editor is loading...
Leave a Comment