#include <bits/stdc++.h> using namespace std;
const int N = 2e5 + 5;
int n;
vector<int> g[N];
int sz[N], big[N], col[N], L[N], R[N], Node[N], totdfn; int ans[N], cnt[N], totColor;
void add(int u) { if (cnt[col[u]] == 0) ++totColor; cnt[col[u]]++; }
void del(int u) { cnt[col[u]]--; if (cnt[col[u]] == 0) --totColor; }
int getAns() { return totColor; }
void dfs0(int u, int p) { L[u] = ++totdfn; Node[totdfn] = u; sz[u] = 1; for (int v : g[u]) if (v != p) { dfs0(v, u); sz[u] += sz[v]; if (!big[u] || sz[big[u]] < sz[v]) big[u] = v; } R[u] = totdfn; }
void dfs1(int u, int p, bool keep) { for (int v : g[u]) if (v != p && v != big[u]) { dfs1(v, u, false); } if (big[u]) { dfs1(big[u], u, true); } for (int v : g[u]) if (v != p && v != big[u]) { for (int i = L[v]; i <= R[v]; i++) { add(Node[i]); } } add(u); ans[u] = getAns(); if (keep == false) { for (int i = L[u]; i <= R[u]; i++) { del(Node[i]); } } }
int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &col[i]); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs0(1, 0); dfs1(1, 0, false); for (int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]); return 0; }
|