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

Xem PDF
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


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

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

    Hãy xác định số lượng màu phân biệt trong cây con của mỗi đỉnh.

    Input

    • Dòng đầu tiên gồm số nguyên \(n\): số lượng đỉnh. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
    • Dòng tiếp theo gồm \(n\) số nguyên \(c_1,c_2,c_3,\dots,c_n\): màu của từng đỉnh.
    • \(n-1\) dòng sau đó biểu diễn các cạnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh nối giữa \(a\) và \(b\).

    Output

    • In ra \(n\) số nguyên: số lượng màu phân biệt trong cây con của các đỉnh \(1,2,3,\dots,n\).

    Constraints

    • \(1\leq n\leq 2 \times 10^5\).
    • \(1\leq a,b\leq n\).
    • \(1\leq c_i\leq 10^9\).

    Example

    Test

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