CSES - Distinct Colors | Màu khác nhau

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , haidanghutcansa , An09855
Dạng bài
Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một cây có gốc bao gồm \(n\) nút. Các nút được đánh số \(1, 2, \ldots, n\) và nút \(1\) là gốc của cây. Mỗi nút có một màu.

Nhiệm vụ của bạn là với mỗi nút, xác định số lượng màu phân biệt trong cây con của nó.

Input

  • Dòng đầu vào đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 2 \times 10^{5})\) - số lượng nút. Các nút được đánh số \(1, 2, \ldots, n\).
  • Dòng tiếp theo bao gồm \(n\) số nguyên \(c_{1}, c_{2}, \ldots, c_{n}\) \((1 \leq c_{i} \leq 10^{9})\) - màu sắc của mỗi nút.
  • Sau đó, có \(n − 1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) - có một cạnh nối hai nút \(a\) và \(b\).

Output

  • \(n\) số nguyên: với mỗi nút \(1, 2, \ldots, n\), in ra số lượng màu khác nhau.

Example

Test 1

Input 
5
2 3 2 2 1
1 2
1 3
3 4
3 5
Output 
3 1 2 1 1

Bình luận


  • -9
    N7hoatt    5:10 p.m. 29 Tháng 8, 2023 ← đã chỉnh sửa

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.