Tóm tắt đề bài: cho đồ thị dạng cây với đỉnh ~1~ là gốc, mỗi đỉnh được tô một màu nhất định. Với mỗi cây con gốc ~u~, bạn cần tính tổng các màu phổ biến ở tất cả các đỉnh của cây con này (kể cả gốc).

Subtask ~1~ ~(n \le 500)~:

• Dùng kỹ thuật dfs để tính từng cây con.
• Ở mỗi cây cha, sau khi duyệt xong các cây con, ta cập nhật tất cả các màu và tìm màu phổ biến và tính đáp án cho cây cha.
• Đpt: ~O(n^2)~.

Subtask ~2~ ~(n \le 10^5)~:

• Vì mỗi cây cha cần tính toán dựa vào kết quả của các cây con, ta sử dụng ctdl map kèm kỹ thuật gộp map để tối ưu độ phức tạp.
• Nhận thấy rằng khi ta gộp phần tử từ map có ít phần tử sang map có nhiều phần tử hơn, thì mỗi phần tử chỉ được di chuyển tối đa ~\log n~ lần, có thể thỏa mãn giới hạn của subtask này.
• Đpt: ~O(n \log ^2 n)~

Code tham khảo

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 1e5 + 5;
int n;
int c[N], res[N], mx[N];
vector<int> g[N];

void dfs(int u, int p, map<int, int>& large) {
    res[u] = c[u];
    mx[u] = 1;
    large[c[u]]++;

    for (auto v : g[u]) if (v != p) {
        map<int, int> small;
        dfs(v, u, small);

        if (small.size() > large.size()) {
            swap(large, small);
            res[u] = res[v];
            mx[u] = mx[v];
        }

        for (auto p : small) {
            large[p.first] += p.second;

            int val = large[p.first];
            if (val > mx[u]) {
                mx[u] = val;
                res[u] = p.first;
            }
            else if (val == mx[u]) res[u] += p.first;
        }
    }
}

int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    map<int, int> mp;
    dfs(1, 0, mp);
    for (int i = 1; i <= n; i++) cout << res[i] << " ";
    return 0;
}