Ý tưởng: Sử dụng Euler tour (đường đi Euler) để trải phẳng cây.

Vì tính chất của Euler tour, cây con của một đỉnh sẽ là một mảng con liên tiếp nằm trên mảng Euler tour. Nhắc lại, cây con gốc ~i~ sẽ được biểu diễn bởi mảng con bắt đầu tại vị trí ~in[i]~ và kết thúc tại vị trí ~out[i]~.

Tổng cộng, ta sẽ có ~n~ cặp (~in[i], out[i]~) khác nhau. Bài toán trở thành: cho một mảng ~A~ gồm ~n~ phần tử (~1 \leq A_i \leq 10^9~) và ~n~ truy vấn có dạng ~(l, r)~, với mỗi truy vấn đếm số lượng giá trị phân biệt trong đoạn ~A[l...r]~. ~\Rightarrow~ Ta có thể sử dụng thuật toán Mo hoặc Segment Tree để giải quyết bài toán đã được biến đổi trên.

Vì màu sắc của các đỉnh có thể vượt quá giới hạn của mảng một chiều thông thường và bài toán chỉ quan tâm đến số giá trị khác nhau, lưu ý việc nén các giá trị màu sắc để phù hợp với giới hạn mảng.

Code mẫu dưới đây sử dụng thuật toán Mo để giải quyết bài toán con:

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5, B = 450;
int n;
vector<int> adj[N + 5];
int c[N + 5];
int a[N + 5], in[N + 5], out[N + 5], timer = 0;
int cnt[N + 5];
pair<int, int> q[N + 5];
int ans[N + 5];

void dfs(int par, int u) {
  in[u] = ++timer;
  a[timer] = u;

  for (int v : adj[u]) {
    if (v == par) continue;
    dfs(u, v);
  }

  out[u] = timer;
}

bool cmp(pair<int, int> u, pair<int, int> v) {
  if (u.first / B == v.first / B) return u.second < v.second;
  return u.first < v.first;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  vector<int> v;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
    v.push_back(c[i]);
  }

  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());

  for (int i = 1; i <= n; i++)
    c[i] = lower_bound(v.begin(), v.end(), c[i]) - v.begin() + 1;

  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  dfs(0, 1);
  for (int i = 1; i <= n; i++) q[i] = {in[i], out[i]};
  sort(q + 1, q + 1 + n, cmp);

  int res = 0, l = 1, r = 0;
  for (int i = 1; i <= n; i++) {
    int u = q[i].first, v = q[i].second;
    while (r < v) {
      r++;
      int color = c[a[r]];
      if (cnt[color] == 0) res++;
      cnt[color]++;
    }

    while (l > u) {
      l--;
      int color = c[a[l]];
      if (cnt[color] == 0) res++;
      cnt[color]++;
    }

    while (r > v) {
      int color = c[a[r]];
      cnt[color]--;
      if (cnt[color] == 0) res--;
      r--;
    }

    while (l < u) {
      int color = c[a[l]];
      cnt[color]--;
      if (cnt[color] == 0) res--;
      l++;
    }

    ans[a[u]] = res;  // a[u] la node nhan doan con a[u...v] la subtree
  }

  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}

#include <bits/stdc++.h>
#define task "a"
#define etr
#define pii pair<int,int>
#define pli pair<long long,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define bg begin
#define pb push_back
#define pf push_front
#define ll long long
#define ld long double
#define pob pop_back
#define pof pop_front
#define lwb lower_bound
#define upb upper_bound
using namespace std;

void freop()
{
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
}

int n;
vector<int> adj[200005];
set<int> tree[200005];
int res[200005];

void dfs(int par, int u)
{
    for (int v : adj[u])
    {
        if (v==par) continue;
        dfs(u,v);
        if (tree[v].size() > tree[u].size()) swap(tree[u], tree[v]);
        for (int x : tree[v]) tree[u].insert(x);
    }

    res[u] = tree[u].size();
}

void process()
{
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        int a;
        cin >> a;
        tree[i].insert(a);
    }

    for (int i=1; i<n; i++)
    {
        int a,b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    dfs(0,1);
    for (int i=1; i<=n; i++) cout << res[i] << ' ';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t=1; //cin >> t;
    while (t--) process();

    return 0;
}