Elearning CodePath – CTP Online Judge

Màu khác nhau trên cây con

DISTINCT_COLORS

🟢 Easy #Tree #DSU

### 📝 Bài toán
Cho một cây có n nút, gốc là nút 1. Mỗi nút i được tô một màu c_i. Với mỗi nút trong cây, hãy xác định số lượng màu sắc khác nhau xuất hiện trong cây con của nó.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file DISTINCT_COLORS.INP:
- Dòng đầu tiên chứa số nguyên n (1 <= n <= 2 * 10^5) là số lượng nút.
- Dòng thứ hai chứa n số nguyên c_1, c_2, ..., c_n (1 <= c_i <= 10^9) đại diện cho màu của mỗi nút.
- n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên a và b (1 <= a, b <= n) mô tả một cạnh nối giữa hai nút a và b.

### 📤 Định dạng Đầu ra
Ghi ra file DISTINCT_COLORS.OUT n số nguyên cách nhau bởi dấu cách, số thứ i đại diện cho số lượng màu khác nhau trong cây con của nút i (theo thứ tự nút từ 1 đến n).

### ✨ Ví dụ
| Input | Output |
| :--- | :--- |
| 5 | 3 1 2 1 1 |
| 2 3 2 2 1 | |
| 1 2 | |
| 1 3 | |
| 3 4 | |
| 3 5 | |

### 🏷 Subtasks
- Subtask 1 (30%): n <= 5000.
- Subtask 2 (70%): n <= 2 * 10^5.

✅ Đã AC: 3 / 5 submissions