You are given an unrooted tree of $n$ nodes numbered from $\mbox{1}$ to $n$. Each node $\boldsymbol{i}$ has a color, $c_i$. 

Let $d(i,j)$ be the number of different colors in the path between node $\boldsymbol{i}$ and node $j$. For each node $\boldsymbol{i}$, calculate the value of $\textit{sum}_i$, defined as follows:

$sum_{i}=\sum_{j=1}^{n}d(i,j)$

Your task is to print the value of $\textit{sum}_i$ for each node $1\leq i\leq n$.

Input Format

The first line contains a single integer, $n$, denoting the number of nodes. 

The second line contains $n$ space-separated integers, $c_1,c_2,\ldots,c_n$, where each $c_i$ describes the color of node $\boldsymbol{i}$. 

Each of the $n-1$ subsequent lines contains $2$ space-separated integers, $\boldsymbol{a}$ and $\boldsymbol{b}$, defining an undirected edge between nodes $\boldsymbol{a}$ and $\boldsymbol{b}$.

Constraints

$1\leq n\leq10^5$
$1\leq c_i\leq10^5$

Output Format

Print $n$ lines, where the $i^{\mbox{th}}$ line contains a single integer denoting $\textit{sum}_i$.

Sample Input
5
1 2 3 2 3
1 2
2 3
2 4
1 5

Sample Output
10
9
11
9
12

Explanation

The Sample Input defines the following tree:

Each $\textit{sum}_i$ is calculated as follows:

$sum_1=d(1,1)+d(1,2)+d(1,3)+d(1,4)+d(1,5)=1+2+3+2+2=10$
$sum_2=d(2,1)+d(2,2)+d(2,3)+d(2,4)+d(2,5)=2+1+2+1+3=9$
$sum_3=d(3,1)+d(3,2)+d(3,3)+d(3,4)+d(3,5)=3+2+1+2+3=11$
$sum_4=d(4,1)+d(4,2)+d(4,3)+d(4,4)+d(4,5)=2+1+2+1+3=9$
$sum_5=d(5,1)+d(5,2)+d(5,3)+d(5,4)+d(5,5)=2+3+3+3+1=12$

Source: hackerrank | Difficulty: HARD
Tags: Data structures


Solutions:
import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


def unique_color_sum(root, edges, colors, size):
	node_colors = [set() for _ in range(size)]
	node_colors[root].add(colors[root])
	visited = set()
	visited.add(root)
	queue = [root]
	while queue:
		node = queue.pop(0)
		for x in edges[node]:
			if x not in visited:
				node_colors[x].update(node_colors[node])
				node_colors[x].add(colors[x])
				queue.append(x)
				visited.add(x)
	color_sum = 0
	for s in node_colors:
		color_sum += len(s)
	return color_sum
n = int(input())
colors = list(map(int, input().split()))
tree_graph = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	tree_graph[a].append(b)
	tree_graph[b].append(a)
for node in range(n):
	print(unique_color_sum(node, tree_graph, colors, n))


class Node:

	def __init__(self, id, color):
		self.id = id
		self.color = color
		self.connections = []

	def addEdge(self, node):
		self.connections.append(node)
n = int(input())
colors = input().split(' ')
nodes = []
for i in range(n):
	node = Node(i, colors[i])
	nodes.append(node)
for i in range(n - 1):
	conn = [int(x) - 1 for x in input().split(' ')]
	nodes[conn[0]].addEdge(nodes[conn[1]])
	nodes[conn[1]].addEdge(nodes[conn[0]])

def findSum(prevNode, node, currSum, colors):
	sum = currSum
	newColors = colors.copy()
	if not node.color in newColors:
		sum += 1
		newColors[node.color] = 1
	newSum = sum
	for newNode in node.connections:
		if newNode != prevNode:
			newSum += findSum(node, newNode, sum, newColors)
	return newSum
for i in range(n):
	print(findSum(nodes[i], nodes[i], 0, {}))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import os
import sys
import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


n = int(input())
color = list(map(int, input().split()))
data = {i: (color[i - 1], []) for i in range(1, n + 1)}
for _ in range(n - 1):
	(a, b) = list(map(int, input().split()))
	data[a][1].append(b)
	data[b][1].append(a)
grid = [[0 for i in range(n)] for j in range(n)]
for i in range(1, n + 1):
	count = 0
	visited = [False for _ in range(n + 1)]
	if not 0 in grid[i - 1]:
		print(sum(grid[i - 1]))
		continue

	def findDeference(data, start):
		queue = [(start, [])]
		while queue:
			selectedcity = tuple(queue.pop(0))
			selectedcity[1].append(data[selectedcity[0]][0])
			grid[start - 1][selectedcity[0] - 1] = len(set(selectedcity[1]))
			grid[selectedcity[0] - 1][start - 1] = len(set(selectedcity[1]))
			visited[selectedcity[0]] = True
			for city in data[selectedcity[0]][1]:
				if visited[city]:
					continue
				else:
					queue.append((city, selectedcity[1].copy()))
	findDeference(data, i)
	print(sum(grid[i - 1]))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))


import collections
n = int(input())
node_colors = input().split()
edges = {i: [] for i in range(n)}
for _ in range(n - 1):
	(one, two) = [int(i) - 1 for i in input().split()]
	edges[one].append(two)
	edges[two].append(one)

def bfs_sum(i):
	value = 0
	seen = {i}
	q = collections.deque([(i, {node_colors[i]})])
	while q:
		(t, colors) = q.popleft()
		value += len(colors)
		for edge in edges[t]:
			if edge not in seen:
				seen.add(edge)
				q.append((edge, colors | {node_colors[edge]}))
	return value
for i in range(n):
	print(bfs_sum(i))