Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
E. Ломсат гелрал
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд $1$ орой нь үндэс байх үндэстэй мод өгөгдсөн. Орой бүр ямар нэг өнгөөр будагдсан.
Хэрвээ $v$ оройн дэд модонд $c$ өнгөнөөс олон харагдах өөр ямар нэгэн өнгө байхгүй бол $v$ оройн дэд модонд $c$ өнгө давамгайлж байна гэе. Зарим оройн дэд модонд хоёр болон түүнээс их өнгө давамгайлж байж болно.
$v$ оройн дэд мод нь $v$ орой ба үндэст хүрэх зам нь $v$ оройг агуулах бусад бүх оройг хэлнэ.
$v$ орой бүрийн хувьд $v$ оройн дэд модонд байгаа бүх давамгайлагч өнгөнүүдийн нийлбэрийг ол.
Оролт
Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 10^{5}$) байх ба модны оройнуудын тоо юм.
Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $c_{i}$ ($1 ≤ c_{i} ≤ n$) байх ба $c_{i}$ нь $i$-р оройн өнгө.
Дараагийн $n - 1$ мөр бүрт хоёр бүхэл тоон утга $x_{j}, y_{j}$ ($1 ≤ x_{j}, y_{j} ≤ n$) байх ба модны ирмэг юм. Эхний орой нь модны үндэс байна.
Гаралт
Орой бүрийн хувьд давамгайлж буй өнгөнүүдийн нийлбэрийг буюу $n$ ширхэг бүхэл тоон утгыг хэвлэ.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
4 1 2 3 4 1 2 2 3 2 4
Гаралт
10 9 3 4
Оролт
15 1 2 3 1 2 3 3 1 1 3 2 2 1 2 3 1 2 1 3 1 4 1 14 1 15 2 5 2 6 2 7 3 8 3 9 3 10 4 11 4 12 4 13
Гаралт
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3