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: HARD
Tags: Tree algorithms

Data structures

Graph traversal

Spanning trees
Skill types: Data structures

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 self.items() if v == self.mx))

	def sumadd(self, map):
		for (bb, val) in 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) = map(lambda x: int(x) - 1, 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]
		answer[i] = cols[i].mx_sum
	print(' '.join(map(str, answer)))
go()


from collections import defaultdict as df
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
timer = 0

@bootstrap
def dfs(v, p):
	global timer
	tin[v] = timer
	ver[timer] = v
	timer += 1
	for child in tree[v]:
		if child != p:
			yield dfs(child, v)
			size[v] += size[child]
	size[v] += 1
	tout[v] = timer
	timer += 1
	yield 0

def operation(mx, v, x):
	ans[cnt[color[v]]] -= color[v]
	cnt[color[v]] += x
	ans[cnt[color[v]]] += color[v]
	mx = max(mx, cnt[color[v]])
	return mx

@bootstrap
def dfs1(v, pa, keep):
	mx = 0
	mx_child = -1
	big_child = -1
	for child in tree[v]:
		if child != pa and size[child] > mx_child:
			mx_child = size[child]
			big_child = child
	for child in tree[v]:
		if child != pa and child != big_child:
			yield dfs1(child, v, 0)
	if big_child != -1:
		temp = (yield dfs1(big_child, v, 1))
		mx = max(temp, mx)
	for child in tree[v]:
		if child != pa and child != big_child:
			for p in range(tin[child], tout[child]):
				mx = operation(mx, ver[p], 1)
	mx = operation(mx, v, 1)
	res[v - 1] = ans[mx]
	if not keep:
		for p in range(tin[v], tout[v]):
			mx = operation(mx, ver[p], -1)
	yield mx
n = int(input().strip())
color = [0] + list(map(int, input().split()))
tree = df(list)
for i in range(1, n):
	(u, v) = map(int, input().split())
	tree[u].append(v)
	tree[v].append(u)
cnt = [0 for i in range(n + 1)]
size = [0 for i in range(n + 1)]
ver = [0 for i in range(n + 1 << 1)]
tin = [0 for i in range(n + 1)]
tout = [0 for i in range(n + 1)]
ans = [0 for i in range(n + 1)]
res = [0 for i in range(n)]
dfs(1, 1)
dfs1(1, 1, 1)
print(' '.join((str(i) for i in res)))


import sys
input = sys.stdin.buffer.readline

class SegmentTree:

	def __init__(self, n, op, e):
		self.n = n
		self.op = op
		self.e = e
		self.size = 2 ** (n - 1).bit_length()
		self.node = [self.e] * (2 * self.size)

	def __getitem__(self, i):
		return self.node[i + self.size]

	def __setitem__(self, i, val):
		i += self.size
		self.node[i] = val
		while i > 1:
			i >>= 1
			self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

	def build(self, array):
		for (i, val) in enumerate(array, self.size):
			self.node[i] = val
		for i in range(self.size - 1, 0, -1):
			self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

	def all_fold(self):
		return self.node[1]

	def fold(self, l, r):
		(l, r) = (l + self.size, r + self.size)
		(vl, vr) = (self.e, self.e)
		while l < r:
			if l & 1:
				vl = self.op(vl, self.node[l])
				l += 1
			if r & 1:
				r -= 1
				vr = self.op(self.node[r], vr)
			(l, r) = (l >> 1, r >> 1)
		return self.op(vl, vr)

def topological_sorted(tree, root=None):
	n = len(tree)
	par = [-1] * n
	tp_order = []
	for v in range(n):
		if par[v] != -1 or (root is not None and v != root):
			continue
		stack = [v]
		while stack:
			v = stack.pop()
			tp_order.append(v)
			for nxt_v in tree[v]:
				if nxt_v == par[v]:
					continue
				par[nxt_v] = v
				stack.append(nxt_v)
	return (tp_order, par)

def dsu_on_tree(tree, root):
	n = len(tree)
	(tp_order, par) = topological_sorted(tree, root)
	di_tree = [[] for i in range(n)]
	for v in range(n):
		for nxt_v in tree[v]:
			if nxt_v == par[v]:
				continue
			di_tree[v].append(nxt_v)
	sub_size = [1] * n
	for v in tp_order[::-1]:
		for nxt_v in di_tree[v]:
			sub_size[v] += sub_size[nxt_v]
	di_tree = [sorted(tr, key=lambda v: sub_size[v]) for tr in di_tree]
	keeps = [0] * n
	for v in range(n):
		di_tree[v] = di_tree[v][:-1][::-1] + di_tree[v][-1:]
		for chi_v in di_tree[v][:-1]:
			keeps[chi_v] = 1
	(tp_order, _) = topological_sorted(di_tree, root)

	def add(sub_root, val):
		stack = [sub_root]
		while stack:
			v = stack.pop()
			vals = st[colors[v]]
			st[colors[v]] = (vals[0] + val, vals[1])
			for chi_v in di_tree[v]:
				stack.append(chi_v)
	for v in tp_order[::-1]:
		for chi_v in di_tree[v]:
			if keeps[chi_v] == 1:
				add(chi_v, 1)
		vals = st[colors[v]]
		st[colors[v]] = (vals[0] + 1, vals[1])
		ans[v] = st.all_fold()[1]
		if keeps[v] == 1:
			add(v, -1)
n = int(input())
colors = list(map(int, input().split()))
edges = [list(map(int, input().split())) for i in range(n - 1)]
tree = [[] for i in range(n)]
for (u, v) in edges:
	u -= 1
	v -= 1
	tree[u].append(v)
	tree[v].append(u)

def op(x, y):
	if x[0] == y[0]:
		return (x[0], x[1] + y[1])
	elif x[0] > y[0]:
		return x
	elif x[0] < y[0]:
		return y
e = (0, 0)
st = SegmentTree(10 ** 5 + 10, op, e)
st.build([(0, i) for i in range(10 ** 5 + 10)])
ans = [0] * n
dsu_on_tree(tree, 0)
print(*ans)


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) = 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 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)


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) = 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:])
main()


import os
import sys
from io import BytesIO, IOBase
_str = str
BUFSIZE = 8192

def str(x=b''):
	return x if type(x) is bytes else _str(x).encode()

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

def tree_bfs(tree, flat=True, start=0) -> list:
	stack = [start]
	result = []
	while stack:
		new_stack = []
		if flat:
			result.extend(stack)
		else:
			result.append(stack)
		for node in stack:
			new_stack.extend(tree[node])
		stack = new_stack
	return result

def to_tree(graph, root=0):
	stack = [[root]]
	while stack:
		if not stack[-1]:
			del stack[-1]
			continue
		parent = stack[-1].pop()
		for child in graph[parent]:
			graph[child].discard(parent)
		stack.append(list(graph[parent]))

def tree_postorder(tree, flat=True, root=0):
	return tree_bfs(tree, flat, root)[::-1]
from collections import defaultdict

class Counter:

	def __init__(self, c):
		self.ans = c
		self.c_t = defaultdict(lambda : 0)
		self.mx = self.c_t[c] = 1
		self.t_c = defaultdict(set)
		self.t_c[1] = {c}

	def merge(self, other):
		for (c, t) in other.c_t.items():
			self.add(c, t)

	def add(self, c, t):
		old_t = self.c_t[c]
		self.c_t[c] = new_t = old_t + t
		self.t_c[old_t].discard(c)
		self.t_c[new_t].add(c)
		if new_t == self.mx:
			self.ans += c
		elif new_t > self.mx:
			self.mx = new_t
			self.ans = c

	def __len__(self):
		return len(self.c_t)

	def __repr__(self):
		return _str(self.ans)

def solve():
	n = itg()
	ans = list(map(Counter, mpint()))
	tree = [set() for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = mpint()
		a -= 1
		b -= 1
		tree[a].add(b)
		tree[b].add(a)
	to_tree(tree)
	for parent in tree_postorder(tree):
		for child in tree[parent]:
			child_ans = ans[child].ans
			if len(ans[parent]) < len(ans[child]):
				(ans[parent], ans[child]) = (ans[child], ans[parent])
			ans[parent].merge(ans[child])
			ans[child] = child_ans
	return ans

def main():
	print(*solve())
DEBUG = 0
URL = 'https://codeforces.com/contest/600/problem/E'
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
elif DEBUG == 2:
	main()
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	main()