1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
|
#define ll long long using namespace std;
const int maxn = 1e5+7;
int n, col[maxn], st[maxn], ed[maxn], son[maxn], sz[maxn],cntt; vector<int>g[maxn]; ll sum, ans[maxn], maxx , Son, cnt[maxn];
void (int x,int fa){ st[x]=++cntt; sz[x]=1; int mx=-1; for(int i=0;i<int(g[x].size());i++){ int v=g[x][i]; if(v==fa) continue; dfsxu(v, x); sz[x]+=sz[v]; if(sz[v] > mx){ mx=sz[v]; son[x]=v; } } ed[x]=cntt; }
void solve(int x,int fa,int val) { cnt[col[x]]+=val; if(cnt[col[x]] > maxx) { maxx=cnt[col[x]]; sum = col[x]; } else if(cnt[col[x]] == maxx){ sum += col[x]; } for(int i=0;i<int(g[x].size());i++) { int v=g[x][i]; if(v==fa || v==Son) continue; solve(v, x , val); } }
void dfs(int x,int fa, bool keep) { int mx=0; for(int i=0;i<int(g[x].size());i++) { int v=g[x][i]; if(v==fa||v==son[x]) continue; dfs(v, x, 0); } if(son[x]) dfs(son[x], x, 1), Son=son[x]; solve(x, fa, 1); Son=0; ans[x]=sum; if(!keep) solve(x,fa,-1), sum=maxx=0; }
int main() { int u, v; scanf("%d", &n); for(int i=1;i<=n;i++) scanf("%d", &col[i]); for(int i=1;i<=n-1;i++) { scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfsxu(1, 0); dfs(1,0,0); for(int i=1;i<=n;i++) printf("%lld%c", ans[i], i==n?'n':' '); return 0; }
|
近期评论