You are given a rooted tree with root in vertex 1. Each vertex is coloured in some colour.

Let's call colour c dominating in the subtree of vertex v if there are no other colours that appear in the subtree of vertex v more times than colour c. So it's possible that two or more colours will be dominating in the subtree of some vertex.

The subtree of vertex v is the vertex v and all other vertices that contains vertex v in each path to the root.

For each vertex v find the sum of all dominating colours in the subtree of vertex v.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of vertices in the tree.

The second line contains n integers c_{i} (1 ≤ c_{i} ≤ n), c_{i} — the colour of the i-th vertex.

Each of the next n - 1 lines contains two integers x_{j}, y_{j} (1 ≤ x_{j}, y_{j} ≤ n) — the edge of the tree. The first vertex is the root of the tree.


-----Output-----

Print n integers — the sums of dominating colours for each vertex.


-----Examples-----
Input
4
1 2 3 4
1 2
2 3
2 4

Output
10 9 3 4

Input
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

Output
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3

Difficulty: interview

Starter code:

Solutions:
from collections import defaultdict


class SumDefaultdict(defaultdict):

    def __init__(self, *args, **kwargs) -> None:
        super().__init__(int, *args, **kwargs)
        self.mx = max(self.values())
        self.mx_sum = sum(c for c, v in list(self.items()) if v == self.mx)

    def sumadd(self, map):
        for bb, val in list(map.items()):
            if val > 0:
                self[bb] += val
                if self[bb] > self.mx:
                    self.mx = self[bb]
                    self.mx_sum = bb
                elif self[bb] == self.mx:
                    self.mx_sum += bb

def go():
    n = int(input())
    c = list(map(int, input().split()))

    edges = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = [int(x) - 1 for x in input().split()]
        edges[a].append(b)
        edges[b].append(a)

    depth = [0] + [None] * (n - 1)
    parent = [None] * n
    que = [0]
    index = 0
    while index < len(que):
        curr = que[index]
        for b in edges[curr]:
            if depth[b] is None:
                depth[b] = depth[curr] + 1
                parent[b] = curr
                que.append(b)
        index += 1

    order = sorted(((depth[i], i) for i in range(n)), reverse=True)

    cols = [SumDefaultdict({c[i]: 1}) for i in range(n)]
    answer = [0] * n
    for d, i in order:
        children = sorted([cols[b] for b in edges[i] if depth[b] > d], key=len, reverse=True)
        if children:
            for j in range(1, len(children)):
                children[0].sumadd(children[j])
            children[0].sumadd({c[i]: 1})
            cols[i] = children[0]
        # max_val = max(cols[i].values())
        answer[i] = cols[i].mx_sum

    print(' '.join(map(str, answer)))


go()


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N = int(input())
    color = list(map(int, input().split()))
    color.insert(0, 0)
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        adj[a].append(b)
        adj[b].append(a)

    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()

    cnt = [{color[i]: 1} for i in range(N+1)]
    cnt_size = [1] * (N+1)
    dom_num = [1] * (N+1)
    ans = [color[i] for i in range(N+1)]
    for v in seq:
        big = cnt[v]
        size_big = cnt_size[v]
        for u in child[v]:
            small = cnt[u]
            size_small = cnt_size[u]
            if size_big < size_small:
                small, big = big, small
                dom_num[v] = dom_num[u]
                ans[v] = ans[u]
            size_big += size_small
            for c in small:
                if c not in big:
                    big[c] = small[c]
                else:
                    big[c] += small[c]
                cnt_size[v] += small[c]
                if big[c] > dom_num[v]:
                    dom_num[v] = big[c]
                    ans[v] = c
                elif big[c] == dom_num[v]:
                    ans[v] += c
        cnt_size[v] = size_big
        cnt[v] = big
    print(*ans[1:])
    #print(child)
    #print(cnt)
    #print(cnt_size)


def __starting_point():
    main()

__starting_point()

import sys
from collections import Counter

n = int(input())
color = list(map(int, input().split()))
adj = [[] for _ in range(n)]

for _ in range(n-1):
    u, v = list(map(int, sys.stdin.readline().split()))
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

count = [Counter() for _ in range(n)]
max_cnt = [0]*n
dp = [0]*n

stack = [0]
par = [-1]*n
order = []
while stack:
    v = stack.pop()
    order.append(v)
    for d in adj[v]:
        if d != par[v]:
            stack.append(d)
            par[d] = v

for v in reversed(order):
    child = [i for i in adj[v] if i != par[v]]
    child.sort(key=lambda v: -len(count[v]))

    if child:
        dp[v] = dp[child[0]]
        max_cnt[v] = max_cnt[child[0]]
        count[v] = count[child[0]]
        for d in child[1:]:
            for k, val in list(count[d].items()):
                count[v][k] += val
                if count[v][k] > max_cnt[v]:
                    dp[v] = k
                    max_cnt[v] = count[v][k]
                elif count[v][k] == max_cnt[v]:
                    dp[v] += k

    count[v][color[v]] += 1
    if count[v][color[v]] > max_cnt[v]:
        dp[v] = color[v]
        max_cnt[v] = count[v][color[v]]
    elif count[v][color[v]] == max_cnt[v]:
        dp[v] += color[v]

    if par[v] != -1:
        stack.append(par[v])

print(*dp)