trang chủ / đề bài / distcolor

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

Đề bài

Mô tả

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ữ liệu vào

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

Dòng thứ hai chứa n số nguyên c1,c2,…,cn — 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.

Dữ liệu ra

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.

Ràng buộc

  • 1≤n≤2·105
  • 1≤ci≤109
  • 1≤a,b≤n

Ví dụ

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0