Задано корневое дерево с корнем в вершине 1. Каждая вершина покрашена в некоторый цвет.
Будем говорить, что цвет c доминирует в поддереве вершины v, если нет другого цвета, который встречается в поддереве вершины v большее количество раз, чем цвет c. Таким образом, возможно два или более цвета одновременно доминируют в одном поддереве.
Поддерево вершины v — это сама вершина v и все такие вершины, путь от которых до корня обязательно проходит через вершину v.
Вам нужно для каждой вершины v определить сумму доминирующих цветов в поддереве вершины v.
В первой строке находится целое число n (1 ≤ n ≤ 105) — количество вершин в дереве.
В второй строке находятся n целых чисел ci (1 ≤ ci ≤ n), ci — цвет i-й вершины.
В каждой из следующей n - 1 строке находится пара целых чисел xj, yj (1 ≤ xj, yj ≤ n) — ребро дерева. Корнем дерева является вершина номер 1.
Выведите 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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач