Cau mày (cây màu)

Xem dạng PDF
Gửi bài giải
Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
bedao
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một cây gồm ~n~ đỉnh có gốc tại đỉnh ~1~. Đỉnh thứ ~i~ (~1 \leq i \leq n~) được gán màu sắc là ~c_i~.

Với mỗi đỉnh ~i~, xác định số màu sắc phân biệt có trong cây con gốc ~i~.

Input

  • Dòng đầu chứa số nguyên dương ~n~ (~1 \leq n \leq 2 \times 10^5~).

  • Dòng thứ hai chứa ~n~ số nguyên dương cách nhau bởi dấu cách biểu diễn mảng ~c~, với ~c_i~ là màu sắc của đỉnh thứ ~i~ (~1 \leq c_i \leq 10^9~).

  • ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a, b~ biểu diễn một cạnh hai chiều giữa đỉnh ~a~ và ~b~ (~1 \leq a,b \leq n~).

Output

Gồm một dòng duy nhất chứa ~n~ số nguyên cách nhau bởi dấu cách, số thứ ~i~ là số màu sắc phân biệt trong tất cả các đỉnh thuộc cây con gốc ~i~.

Scoring

Subtask Điểm Giới hạn
1 40 ~n \leq 5000~
2 60 ~n \leq 2 \times 10^5~

Sample Input 1

5
2 3 2 2 1
1 2
1 3
3 4
3 5

Sample Output 1

3 1 2 1 1

Sample Input 2

4
1 1 3 1000
1 2
2 3
2 4

Sample Output 2

3 3 1 1

Notes

  • Trong test đầu tiên, cây con của đỉnh ~1~ bao gồm tất cả các đỉnh trong cây, mang ~3~ giá trị màu sắc khác nhau. Cây con của đỉnh ~3~ bao gồm ba đỉnh là ~3, 4, 5~ lần lượt mang các màu ~2, 2, 1~, có tất cả ~2~ màu sắc phân biệt là màu ~1~ và ~2~.

  • Trong test thứ hai, cây con của đỉnh ~1~ và đỉnh ~2~ đều có ~3~ màu sắc phân biệt là màu ~1, 3, 1000~.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -3
    phuongly160109  đã bình luận lúc 23, Tháng 4, 2025, 0:48

    include <bits/stdc++.h>

    using namespace std;

    int n; vector<int> color; vector tree; vector color_sets;

    void dfs(int u, int parent) { color_sets[u].insert(color[u]); for (int v : tree[u]) { if (v == parent) continue; dfs(v, u);

        if (color_sets[u].size() < color_sets[v].size())
        swap(color_sets[u], color_sets[v]);
    for (int c : color_sets[v])
        color_sets[u].insert(c);
}

    }

    int main() { cin >> n; color.resize(n + 1); tree.resize(n + 1); color_sets.resize(n + 1);

    for (int i = 1; i <= n; ++i)
    cin >> color[i];

for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    tree[u].push_back(v);
    tree[v].push_back(u);
}

dfs(1, 0);

for (int i = 1; i <= n; ++i)
    cout << color_sets[i].size() << " ";
cout << "\n";

return 0;

    }


  • -35
    k116tinvuongngotan  đã bình luận lúc 3, Tháng 5, 2024, 8:36

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.