Số màu phân biệt trong cây con

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một cây gồm $n$ đỉnh, gốc tại đỉnh 1. Mỗi đỉnh có một màu sắc.

Với mỗi đỉnh, hãy tính số lượng màu sắc phân biệt trong cây con gốc tại đỉnh đó.

Dòng đầu chứa số nguyên $n$ .

Dòng thứ hai chứa $n$ số nguyên $c_{1}, c_{2}, \dots, c_{n}$ — màu sắc của từng đỉnh.

$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một cạnh của cây.

In ra $n$ số nguyên, số thứ $i$ là số màu phân biệt trong cây con gốc tại đỉnh $i$ .

Input	Output	Giải thích
5 2 3 2 2 1 1 2 1 3 3 4 3 5	3 1 2 1 1	Cây con đỉnh 1 gồm tất cả: màu {1,2,3} → 3. Đỉnh 3 gồm {2,2,1} → 2 màu. Đỉnh 2,4,5 chỉ có 1 màu.
4 1 2 1 3 1 2 1 3 1 4	3 1 1 1	Cây con đỉnh 1 chứa màu 1,2,3 → 3 màu phân biệt.

Bình luận

Không có bình luận tại thời điểm này.