AtCoder Beginner Contest 163 - path pass i

We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i.
Additionally, each vertex is painted in a color, and the color of Vertex i is c_i. Here, the color of each vertex is represented by an integer between 1 and N (inclusive). The same integer corresponds to the same color; different integers correspond to different colors.
For each k=1, 2, ..., N, solve the following problem:
 - Find the number of simple paths that visit a vertex painted in the color k one or more times.
Note: The simple paths from Vertex u to v and from v to u are not distinguished.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - 1 \leq c_i \leq N
 - 1 \leq a_i,b_i \leq N
 - The given graph is a tree.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
c_1 c_2 ... c_N
a_1 b_1
:
a_{N-1} b_{N-1}

-----Output-----
Print the answers for k = 1, 2, ..., N in order, each in its own line.

-----Sample Input-----
3
1 2 1
1 2
2 3

-----Sample Output-----
5
4
0

Let P_{i,j} denote the simple path connecting Vertex i and j.
There are 5 simple paths that visit a vertex painted in the color 1 one or more times:
P_{1,1}\,,\,P_{1,2}\,,\,P_{1,3}\,,\,P_{2,3}\,,\,P_{3,3} 
There are 4 simple paths that visit a vertex painted in the color 2 one or more times:
P_{1,2}\,,\,P_{1,3}\,,\,P_{2,2}\,,\,P_{2,3} 
There are no simple paths that visit a vertex painted in the color 3 one or more times.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
mod = 1000000007
eps = 10 ** (-9)

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

	def calc(n):
		return n * (n + 1) // 2
	N = int(input())
	C = list(map(int, input().split()))
	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()
	size = [1] * (N + 1)
	for v in seq:
		for u in child[v]:
			size[v] += size[u]
	ans = [calc(N)] * (N + 1)
	par_C = [[] for _ in range(N + 1)]
	sub = [0] * (N + 1)
	sub_0 = [0] * (N + 1)
	st = deque()
	st.append(1)
	while st:
		v = st.pop()
		if v > 0:
			st.append(-v)
			for u in child[v]:
				st.append(u)
			c = C[v - 1]
			if par_C[c]:
				sub[par_C[c][-1]] += size[v]
			else:
				sub_0[c] += size[v]
			par_C[c].append(v)
		else:
			v = -v
			c = C[v - 1]
			assert par_C[c][-1] == v
			par_C[c].pop()
			p = par[v]
			if p:
				cp = C[p - 1]
				ans[cp] -= calc(size[v] - sub[p])
				sub[p] = 0
	for c in range(1, N + 1):
		ans[c] -= calc(N - sub_0[c])
		print(ans[c])
main()


import sys
sys.setrecursionlimit(10 ** 6)
stdin = sys.stdin
ns = lambda : stdin.readline().rstrip()
ni = lambda : int(stdin.readline().rstrip())
nm = lambda : map(int, stdin.readline().split())
nl = lambda : list(map(int, stdin.readline().split()))
n = ni()
color = nl()
g = [list() for _ in range(n)]
for _ in range(n - 1):
	(a, b) = nm()
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
size = [1] * n
par = [-1] * n
h = [list() for _ in range(n + 1)]
idx = [0] * n

def dfs(v, p):
	h[color[v]].append(v)
	for x in g[v]:
		if x == p:
			continue
		par[x] = v
		size[v] += dfs(x, v)
		h[color[v]].append(v)
	h[color[v]].append(v)
	return size[v]
dfs(0, -1)
for v in range(n):
	if idx[v] < len(g[v]) and g[v][idx[v]] == par[v]:
		idx[v] += 1
acc = [0] * (n + 10)
ans = [n * (n + 1) // 2] * (n + 1)
for col in range(1, n + 1):
	acc[-1] = 0
	p = [-1]
	for v in h[col]:
		if p[-1] == v:
			p.pop()
			if idx[v] >= len(g[v]):
				acc[p[-1]] += size[v]
				continue
			q = size[g[v][idx[v]]] - acc[v]
			idx[v] += 1
			if idx[v] < len(g[v]) and g[v][idx[v]] == par[v]:
				idx[v] += 1
			ans[col] -= q * (q + 1) // 2
			acc[v] = 0
			p.append(v)
		else:
			p.append(v)
	q = n - acc[-1]
	ans[col] -= q * (q + 1) // 2
print(*ans[1:], sep='\n')


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n = int(input())
C = list(map(int, input().split()))
path = [set() for _ in range(n)]
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	path[a].add(b)
	path[b].add(a)
ans = [n * (n + 1) // 2] * n
cparent = [[] for _ in range(n)]
root_size = [n] * n
reached = [False] * n
size = [0] * n

def dfs(p):
	c = C[p] - 1
	cparent[c].append(p)
	s = 1
	for nxt in path[p]:
		if reached[nxt]:
			continue
		reached[nxt] = True
		size[p] = 0
		ret = dfs(nxt)
		s += ret
		size[p] += ret
		ans[c] -= size[p] * (size[p] + 1) // 2
	cparent[c].pop()
	if cparent[c]:
		size[cparent[c][-1]] -= s
	else:
		root_size[c] -= s
	return s
reached = [False] * n
reached[0] = True
dfs(0)
for i in range(n):
	print(ans[i] - root_size[i] * (root_size[i] + 1) // 2)


from collections import defaultdict
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
N = int(readline())
C = tuple(map(lambda x: int(x) - 1, readline().split()))
temp = map(int, read().split())
temp = zip(temp, temp)
adj = [list() for _ in range(N)]
for (a, b) in temp:
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
parent = [None] * N
parent[0] = -1
stack = [0]
order = []
while stack:
	p = stack.pop()
	order.append(p)
	for c in adj[p]:
		if parent[c] is None:
			parent[c] = p
			stack.append(c)

def merge(a, b):
	if len(a) > len(b):
		(a, b) = (b, a)
	for (k, v) in a.items():
		b[k] += v
	return b
dp = [defaultdict(int) for _ in range(N)]
subtreesize = [0] * N
cnt = [N * (N + 1) // 2] * N
for c in reversed(order):
	p = parent[c]
	if p >= 0:
		dp[c][C[c]] = subtreesize[c] + 1
		x = subtreesize[c] - dp[c][C[p]] + 1
		cnt[C[p]] -= x * (x + 1) // 2
		subtreesize[p] += subtreesize[c] + 1
		dp[p] = merge(dp[c], dp[p])
		dp[c] = None
dp[0][C[0]] = subtreesize[0] + 1
for c in range(N):
	x = subtreesize[0] - dp[0][c] + 1
	cnt[c] -= x * (x + 1) // 2
print(*cnt, sep='\n')


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
n = int(input())
c = list(map(lambda x: int(x) - 1, input().split()))
graph = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
ans = [n * (n + 1) // 2] * n
n_subtree = [1] * n
cnt = [0] * n
n_visited = 0

def dfs(v, v_p):
	nonlocal n_visited
	cnt_v_before = cnt[c[v]]
	for v_next in graph[v]:
		if v_next == v_p:
			continue
		m_prev = n_visited - cnt[c[v]]
		dfs(v_next, v)
		n_subtree[v] += n_subtree[v_next]
		m_next = n_visited - cnt[c[v]]
		m = m_next - m_prev
		ans[c[v]] -= m * (m + 1) // 2
	cnt[c[v]] = cnt_v_before + n_subtree[v]
	n_visited += 1
dfs(0, -1)
for i in range(n):
	m = n - cnt[i]
	ans[i] -= m * (m + 1) // 2
print(*ans, sep='\n')


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()

class SegmentTree(object):

	def __init__(self, A, dot, unit):
		n = 1 << (len(A) - 1).bit_length()
		tree = [unit] * (2 * n)
		for (i, v) in enumerate(A):
			tree[i + n] = v
		for i in range(n - 1, 0, -1):
			tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
		self._n = n
		self._tree = tree
		self._dot = dot
		self._unit = unit

	def __getitem__(self, i):
		return self._tree[i + self._n]

	def update(self, i, v):
		i += self._n
		self._tree[i] = v
		while i != 1:
			i >>= 1
			self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

	def add(self, i, v):
		self.update(i, self[i] + v)

	def sum(self, l, r):
		l += self._n
		r += self._n
		l_val = r_val = self._unit
		while l < r:
			if l & 1:
				l_val = self._dot(l_val, self._tree[l])
				l += 1
			if r & 1:
				r -= 1
				r_val = self._dot(self._tree[r], r_val)
			l >>= 1
			r >>= 1
		return self._dot(l_val, r_val)
from operator import add

def resolve():
	n = int(input())
	color = [[] for _ in range(n)]
	for (v, c) in enumerate(map(int, input().split())):
		color[c - 1].append(v)
	E = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		E[u].append(v)
		E[v].append(u)
	start = [-1] * n
	end = [-1] * n
	count = 0
	stack = [(~0, -1), (0, -1)]
	while stack:
		(v, p) = stack.pop()
		if v >= 0:
			start[v] = count
			count += 1
			for nv in E[v]:
				if nv == p:
					continue
				stack.append((~nv, v))
				stack.append((nv, v))
		else:
			end[~v] = count
	f = lambda x: x * (x + 1) // 2
	ans = [f(n)] * n
	tree = SegmentTree([1] * n, add, 0)
	history = []
	for c in range(n):
		for v in sorted(color[c], key=lambda x: start[x], reverse=1):
			count = 1
			for nv in E[v]:
				if start[v] > start[nv]:
					continue
				s = tree.sum(start[nv], end[nv])
				ans[c] -= f(s)
				count += s
			tree.add(start[v], -count)
			history.append((start[v], count))
		ans[c] -= f(tree.sum(0, n))
		while history:
			tree.add(*history.pop())
	print(*ans, sep='\n')
resolve()


import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import cmp_to_key, lru_cache, reduce
from operator import add, sub
from itertools import count
sys.setrecursionlimit(10 ** 6 + 1)
input = sys.stdin.buffer.readline
MOD = 10 ** 9 + 7

def solve(g, clr, n):

	def dfs(v, par):
		nonlocal total
		sub[v] = 1
		bfr = cnt[clr[v]]
		for u in g[v]:
			if u == par:
				continue
			pre = total - cnt[clr[v]]
			sub[v] += dfs(u, v)
			nxt = total - cnt[clr[v]]
			ans[clr[v]] -= (nxt - pre) * (nxt - pre - 1) // 2
		cnt[clr[v]] = bfr + sub[v]
		total += 1
		return sub[v]
	ans = [(n - 1) * n // 2] * (n + 1)
	cnt = [0] * (n + 1)
	sub = [0] * (n + 1)
	total = 0
	dfs(1, -1)
	for i in range(1, n + 1):
		(pre, nxt) = (0, n - cnt[i])
		ans[i] -= (nxt - pre) * (nxt - pre - 1) // 2
	for c in clr:
		ans[c] += 1
	print(*ans[1:], sep='\n')
n = int(input())
colors = [0] + [int(s) for s in input().split()]
g = defaultdict(set)
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	g[a].add(b)
	g[b].add(a)
solve(g, colors, n)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def solve():
	N = int(input())
	Cs = [A - 1 for A in map(int, input().split())]
	adjL = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		adjL[a].append(b)
		adjL[b].append(a)
	sizeSubtrees = [1] * N
	numVs = [0] * N
	anss = [0] * N

	def dfs(vNow, vPar, clrPar):
		clrNow = Cs[vNow]
		numVNow = numVs[clrNow]
		numVPar = numVs[clrPar]
		for v2 in adjL[vNow]:
			if v2 == vPar:
				continue
			dfs(v2, vNow, clrNow)
			sizeSubtrees[vNow] += sizeSubtrees[v2]
		numVs[clrNow] = numVNow + sizeSubtrees[vNow]
		if clrPar != -1:
			k = sizeSubtrees[vNow] - (numVs[clrPar] - numVPar)
			anss[clrPar] += k * (k + 1) // 2
	dfs(0, -1, -1)
	for clr in range(N):
		if clr == Cs[0]:
			continue
		k = N - numVs[clr]
		anss[clr] += k * (k + 1) // 2
	numAll = N * (N + 1) // 2
	anss = [numAll - ans for ans in anss]
	print('\n'.join(map(str, anss)))
solve()


import sys
input = sys.stdin.readline
N = int(input())
C = [0] + list(map(int, input().split()))
E = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	E[a].append(b)
	E[b].append(a)
from collections import deque
QUE = deque([1])
QUE2 = deque()
EULER = [0]
USED = [0] * (N + 1)
Parent = [-1] * (N + 1)
TOP_SORT = [1]
Children = [[] for i in range(N + 1)]
while QUE:
	x = QUE.pop()
	EULER.append(x)
	if USED[x] == 1:
		continue
	for to in E[x]:
		if USED[to] == 0:
			QUE2.append(to)
			Parent[to] = x
			Children[x].append(to)
			TOP_SORT.append(to)
		else:
			QUE.append(to)
	QUE.extend(QUE2)
	QUE2 = deque()
	USED[x] = 1
CE = [[] for i in range(N + 1)]
CTOP_SORT = [[] for i in range(N + 1)]
for x in TOP_SORT:
	CTOP_SORT[C[x]].append(x)
EFIRST = [-1] * (N + 1)
ELAST = [-1] * (N + 1)
for i in range(len(EULER)):
	if EFIRST[EULER[i]] == -1:
		EFIRST[EULER[i]] = i
	ELAST[EULER[i]] = i
	CE[C[EULER[i]]].append(i)
Size = [1] * (N + 1)
for i in TOP_SORT[1:][::-1]:
	Size[Parent[i]] += Size[i]
Size[0] = N + 1
LEN = len(EULER)
BIT = [0] * (LEN + 1)

def update(v, w):
	while v <= LEN:
		BIT[v] += w
		v += v & -v

def getvalue(v):
	ANS = 0
	while v != 0:
		ANS += BIT[v]
		v -= v & -v
	return ANS
for i in range(1, N + 1):
	update(EFIRST[i], 1)
for color in range(1, N + 1):
	if CE[color] == []:
		print(0)
		continue
	EULER2 = CE[color]
	TOP_SORT2 = CTOP_SORT[color]
	HISTORY = []
	ANS = 0
	for x in TOP_SORT2[::-1]:
		for to in Children[x]:
			sc = getvalue(ELAST[to]) - getvalue(EFIRST[to] - 1)
			update(EFIRST[x], -sc)
			HISTORY.append((EFIRST[x], sc))
			ANS += sc * (sc + 1) // 2
		update(EFIRST[x], -1)
		HISTORY.append((EFIRST[x], 1))
	sc = getvalue(len(EULER))
	ANS += sc * (sc + 1) // 2
	print(N * (N + 1) // 2 - ANS)
	for (x, y) in HISTORY:
		update(x, y)


import sys
from operator import add
readline = sys.stdin.readline

def euler_tour(root, Edge):
	N = len(Edge)
	stack = [root]
	used = [False] * N
	tour = []
	down = []
	dist = [0] * N
	ta = tour.append
	sa = stack.append
	St = [None] * N
	En = [None] * N
	cnt = -1
	while stack:
		cnt += 1
		vn = stack.pop()
		ta(vn)
		if St[vn] is None:
			St[vn] = cnt
		En[vn] = cnt
		if used[vn]:
			continue
		for vf in Edge[vn]:
			if used[vf]:
				sa(vf)
			else:
				dist[vf] = 1 + dist[vn]
				down.append(vf)
		stack.extend(down)
		down = []
		used[vn] = True
	return (St, En, tour, dist)

def parorder(Edge, p):
	N = len(Edge)
	par = [0] * N
	par[p] = -1
	stack = [p]
	order = []
	visited = set([p])
	ast = stack.append
	apo = order.append
	while stack:
		vn = stack.pop()
		apo(vn)
		for vf in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			ast(vf)
	return (par, order)

def getcld(p):
	res = [[] for _ in range(len(p))]
	for (i, v) in enumerate(p):
		if v == -1:
			continue
		res[v].append(i)
	return res

class Segtree:

	def __init__(self, A, intv, initialize=True, segf=max):
		self.N = len(A)
		self.N0 = 2 ** (self.N - 1).bit_length()
		self.intv = intv
		self.segf = segf
		if initialize:
			self.data = [intv] * self.N0 + A + [intv] * (self.N0 - self.N)
			for i in range(self.N0 - 1, 0, -1):
				self.data[i] = self.segf(self.data[2 * i], self.data[2 * i + 1])
		else:
			self.data = [intv] * (2 * self.N0)

	def __repr__(self):
		return str(' '.join(map(str, self.data[self.N0:self.N0 + self.N])))

	def update(self, k, x):
		k += self.N0
		self.data[k] = x
		while k > 0:
			k = k >> 1
			self.data[k] = self.segf(self.data[2 * k], self.data[2 * k + 1])

	def query(self, l, r):
		(L, R) = (l + self.N0, r + self.N0)
		s = self.intv
		while L < R:
			if R & 1:
				R -= 1
				s = self.segf(s, self.data[R])
			if L & 1:
				s = self.segf(s, self.data[L])
				L += 1
			L >>= 1
			R >>= 1
		return s

	def binsearch(self, l, r, check, reverse=False):
		(L, R) = (l + self.N0, r + self.N0)
		(SL, SR) = ([], [])
		while L < R:
			if R & 1:
				R -= 1
				SR.append(R)
			if L & 1:
				SL.append(L)
				L += 1
			L >>= 1
			R >>= 1
		if reverse:
			for idx in SR + SL[::-1]:
				if check(self.data[idx]):
					break
			else:
				return -1
			while idx < self.N0:
				if check(self.data[2 * idx + 1]):
					idx = 2 * idx + 1
				else:
					idx = 2 * idx
			return idx - self.N0
		else:
			for idx in SL + SR[::-1]:
				if check(self.data[idx]):
					break
			else:
				return -1
			while idx < self.N0:
				if check(self.data[2 * idx]):
					idx = 2 * idx
				else:
					idx = 2 * idx + 1
			return idx - self.N0
N = int(readline())
Col = list(map(lambda x: int(x) - 1, readline().split()))
Colidx = [[] for _ in range(N)]
for i in range(N):
	Colidx[Col[i]].append(i)
Edge = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, readline().split())
	a -= 1
	b -= 1
	Edge[a].append(b)
	Edge[b].append(a)
root = 0
for root in range(N):
	if len(Edge[root]) == 1:
		break
(P, L) = parorder(Edge, root)
C = getcld(P)
(St, En, tour, dist) = euler_tour(root, Edge)
L = len(tour)
table = [0] * L
Ans = [0] * N
for i in range(N):
	table[En[i]] = 1
T = Segtree(table, 0, initialize=True, segf=add)
for c in range(N):
	Ci = Colidx[c]
	if Ci:
		Ci.sort(key=lambda x: dist[x], reverse=True)
		res = 0
		for v in Ci:
			sv = 0
			for cv in C[v]:
				k = T.query(St[cv], En[cv] + 1)
				sv += k
				res += k * (k + 1) // 2
			T.update(En[v], -sv)
		k = T.query(St[root], En[root] + 1)
		res += k * (k + 1) // 2
		for v in Ci:
			T.update(En[v], 1)
		Ans[c] = N * (N + 1) // 2 - res
print('\n'.join(map(str, Ans)))


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
C = [int(x) - 1 for x in input().split()]
E = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)

def dfs(u, p=-1):
	color = C[u]
	VC[color].append(u)
	s = 1
	for v in E[u]:
		if v == p:
			continue
		child[u] = 0
		ret = dfs(v, u)
		s += ret
		child[u] += ret
		ans[color] -= child[u] * (child[u] + 1) // 2
	VC[color].pop()
	if VC[color]:
		child[VC[color][-1]] -= s
	else:
		root_size[color] -= s
	return s
child = [0] * N
root_size = [N] * N
VC = [[] for _ in range(N)]
ans = [N * (N + 1) // 2] * N
dfs(0)
for i in range(N):
	print(ans[i] - root_size[i] * (root_size[i] + 1) // 2)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
N = int(input())
c = [int(i) - 1 for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	vec[a - 1].append(b - 1)
	vec[b - 1].append(a - 1)
ret = [N * (N - 1) // 2 + N] * N
par = [[N + i] for i in range(N)]
vec2 = [[] for _ in range(N * 2)]
have = [0] * (N * 2)
way = [0] * (N * 2)
fr = [0] * (N + 2)
for i in range(N, 2 * N):
	have[i] = N + 1
mem = defaultdict(int)

def dfs(cur, pre):
	s = 1
	ancestor = par[c[cur]][-1]
	vec2[ancestor].append(cur)
	if pre != -1:
		fr[cur] = way[ancestor]
	par[c[cur]].append(cur)
	for nex in vec[cur]:
		if nex == pre:
			continue
		way[cur] = nex
		s += dfs(nex, cur)
		mem[cur, nex] = have[nex]
	par[c[cur]].pop()
	have[cur] = s
	return s
dfs(0, -1)
for i in range(N, 2 * N):
	mem[i, 0] = N
for i in range(N):
	q = [(N + i, -1)]
	while q:
		(cur, pre) = q.pop()
		for nex in vec2[cur]:
			mem[cur, fr[nex]] -= have[nex]
			q.append((nex, cur))
for (k, v) in mem.items():
	if v <= 0:
		continue
	if k[0] >= N:
		ret[k[0] % N] -= v * (v - 1) // 2 + v
	else:
		ret[c[k[0]]] -= v * (v - 1) // 2 + v
for i in range(N):
	print(ret[i])


import sys
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict
INF = float('inf')
MOD = 10 ** 9 + 7

class Graph(object):

	def __init__(self, N):
		self.N = N
		self.E = defaultdict(list)

	def add_edge(self, f, t, w=1):
		self.E[f].append((t, w))
		self.E[t].append((f, w))
N = int(input())
c = [x - 1 for x in map(int, input().split())]
A = [None] * (N - 1)
B = [None] * (N - 1)
for i in range(N - 1):
	(A[i], B[i]) = map(int, input().split())
g = Graph(N)
for (a, b) in zip(A, B):
	g.add_edge(a - 1, b - 1)
ans = [0] * N

def f(curr, par=-1):
	ret = defaultdict(int)
	size = 1
	for (dest, w) in g.E[curr]:
		if dest == par:
			continue
		(sz, child) = f(dest, curr)
		size += sz
		n = sz - child[c[curr]]
		ans[c[curr]] += n * (n + 1) // 2
		if len(ret) < len(child):
			(child, ret) = (ret, child)
		for key in child:
			ret[key] += child[key]
	ret[c[curr]] = size
	return (size, ret)
(sz, ret) = f(0)
for color in range(N):
	if color != c[0]:
		n = sz - ret[color]
		ans[color] += n * (n + 1) // 2
tot = N * (N + 1) // 2
for a in ans:
	print(tot - a)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict
N = int(readline())
C = (0,) + tuple(map(int, readline().split()))
m = map(int, read().split())
AB = zip(m, m)
graph = [[] for _ in range(N + 1)]
for (a, b) in AB:
	graph[a].append(b)
	graph[b].append(a)
root = 1
parent = [0] * (N + 1)
depth = [0] * (N + 1)
order = []
stack = [root]
depth[root] = 1
while stack:
	x = stack.pop()
	order.append(x)
	for y in graph[x]:
		if y == parent[x]:
			continue
		parent[y] = x
		stack.append(y)
		depth[y] = depth[x] + 1

def merge(v, p):
	A = dp[v]
	B = dp[p]
	size_A = size[v]
	size_B = size[p]
	c = C[p]
	if len(A) < len(B):
		(A, B) = (B, A)
		(size_A, size_B) = (size_B, size_A)
	answer[c] += (size_A - A[c]) * (size_B - B[c])
	for (key, cnt) in B.items():
		answer[key] -= cnt * A[key]
		A[key] += cnt
	size[p] = size_A + size_B
	dp[p] = A
answer = [0] * (N + 1)
dp = [defaultdict(int) for _ in range(N + 1)]
size = [0] * (N + 1)
for v in order[::-1]:
	c = C[v]
	n = size[v] + 1 - dp[v][c]
	answer[c] -= size[v] * n
	size[v] += 1
	dp[v][c] = size[v]
	if v == root:
		break
	p = parent[v]
	merge(v, p)
A = dp[root]
c = size[root]
for v in range(1, N + 1):
	print(c * A[v] + answer[v])


import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
N = int(input())
C = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for i in range(N - 1)]
es = [[] for _ in range(N)]
for (a, b) in AB:
	(a, b) = (a - 1, b - 1)
	es[a].append(b)
	es[b].append(a)
cs = [[] for _ in range(N)]
for (i, c) in enumerate(C):
	cs[c - 1].append(i)
tin = [-1] * N
tout = [-1] * N
k = 0

def dfs(v, p=-1):
	global k
	tin[v] = k
	k += 1
	for to in es[v]:
		if to == p:
			continue
		dfs(to, v)
	tout[v] = k
dfs(0)

class BinaryIndexedTree:

	def __init__(self, size):
		self.N = size
		self.bit = [0] * (size + 1)

	def add(self, x, w):
		x += 1
		while x <= self.N:
			self.bit[x] += w
			x += x & -x

	def _sum(self, x):
		ret = 0
		while x > 0:
			ret += self.bit[x]
			x -= x & -x
		return ret

	def sum(self, l, r):
		return self._sum(r) - self._sum(l)

	def __str__(self):
		arr = [self.sum(i, i + 1) for i in range(self.N)]
		return str(arr)
bit = BinaryIndexedTree(N)
for i in range(N):
	bit.add(i, 1)
whole = N * (N + 1) // 2
anss = []
for i in range(N):
	ans = whole
	cs[i].sort(key=lambda x: -tin[x])
	history = []
	for v in cs[i]:
		cnt = 1
		for to in es[v]:
			if tin[to] < tin[v]:
				continue
			num = bit.sum(tin[to], tout[to])
			ans -= num * (num + 1) // 2
			cnt += num
		bit.add(tin[v], -cnt)
		history.append((tin[v], cnt))
	pn = bit.sum(0, N)
	ans -= pn * (pn + 1) // 2
	for (a, b) in history:
		bit.add(a, b)
	anss.append(ans)
print(*anss, sep='\n')


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(N, C, AB):

	def edges_to_array(A, B, N, M):
		head = [-1] * (N + 1)
		nxt = [0] * (M + M)
		to = [0] * (M + M)
		for i in range(M):
			a = A[i]
			b = B[i]
			nxt[i << 1] = head[a]
			to[i << 1] = b
			head[a] = i << 1
			nxt[i << 1 | 1] = head[b]
			to[i << 1 | 1] = a
			head[b] = i << 1 | 1
		return (head, nxt, to)

	def EulerTour(head, nxt, to, root=1):
		N = len(head) - 1
		parent = [0] * (N + 1)
		ind_L = [0] * (N + 1)
		ind_R = [0] * (N + 1)
		i = -1
		tour = []
		stack = [-root, root]
		stack[0] = -root
		stack[1] = root
		while stack:
			v = stack.pop()
			tour.append(v)
			i += 1
			if v > 0:
				ind_L[v] = i
				p = parent[v]
				k = head[v]
				while k != -1:
					w = to[k]
					if w == p:
						k = nxt[k]
						continue
					parent[w] = v
					stack.append(-w)
					stack.append(w)
					k = nxt[k]
			else:
				ind_R[-v] = i
		return (tour, ind_L, ind_R, parent)
	(head, nxt, to) = edges_to_array(AB[::2], AB[1::2], N, N - 1)
	(tour, ind_L, ind_R, parent) = EulerTour(head, nxt, to)
	removed = [0] * (N + 1)
	answer = [N * (N + 1) // 2] * (N + 1)
	memo = [0] * (N + 1)
	for v in tour:
		if v > 0:
			memo[v] = removed[C[parent[v]]]
		else:
			v = -v
			removed[C[v]] += 1
			p = parent[v]
			x = (ind_R[v] - ind_L[v]) // 2 + 1
			x -= removed[C[p]] - memo[v]
			answer[C[p]] -= x * (x + 1) // 2
			removed[C[p]] += x
	for (i, x) in enumerate(removed):
		x = N - x
		answer[i] -= x * (x + 1) // 2
	return answer
N = int(readline())
C = (0,) + tuple(map(int, readline().split()))
AB = tuple(map(int, read().split()))
answer = solve(N, C, AB)
print('\n'.join(map(str, answer[1:])))


import os
from collections import Counter, defaultdict
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
N = int(sys.stdin.buffer.readline())
C = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]
for (a, b) in AB:
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
color_counts = [defaultdict(int) for _ in range(N + 1)]
for c in range(1, N + 1):
	color_counts[c][0] = N
color_v_weights = [[] for _ in range(N + 1)]
color_v = [0 for _ in range(N + 1)]
color_v_next = [1 for _ in range(N + 1)]

def dfs(v, p):
	color = C[v]
	color_v_prev = color_v[color]
	children_cv = []
	ret = 1
	for u in graph[v]:
		if u == p:
			continue
		cv = color_v_next[color]
		children_cv.append(cv)
		color_v[color] = cv
		color_v_next[color] += 1
		cnt = dfs(u, v)
		ret += cnt
		color_counts[color][cv] += cnt
	color_v[color] = color_v_prev
	color_counts[color][color_v_prev] -= ret
	return ret
dfs(0, None)
counter = Counter(C)
for (color, cc) in enumerate(color_counts[1:], start=1):
	ans = N * (N - 1) // 2 + counter[color]
	for cnt in cc.values():
		ans -= cnt * (cnt - 1) // 2
	print(ans)


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)

def sum(n):
	return n * (n + 1) // 2

def dfs(v, p):
	ret = defaultdict(int)
	size = 1
	for vv in g[v]:
		if vv == p:
			continue
		(ss, d) = dfs(vv, v)
		size += ss
		ans[c[v]] += sum(ss - d[c[v]])
		if len(ret) < len(d):
			(ret, d) = (d, ret)
		for vvv in d:
			ret[vvv] += d[vvv]
	ret[c[v]] = size
	return (size, ret)
n = int(input())
c = list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
ans = [0] * (n + 1)
for _ in range(n - 1):
	(s, t) = list(map(int, input().split()))
	s -= 1
	t -= 1
	g[s].append(t)
	g[t].append(s)
(_, ret) = dfs(0, -1)
for i in range(1, n + 1):
	print(sum(n) - ans[i] - sum(n - ret[i]))


import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2 * n))
cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n - 1):
	(a, b) = [int(c) for c in input().split()]
	ns[a].add(b)
	ns[b].add(a)
ans = [0] * (n + 1)
minus = [0] * (n + 1)
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n + 1)}
nextu = {}

def dfs(u, prev, ans):
	global minus, st, minus0
	k = cs[u]
	st[k].append(u)
	ss = 1
	for v in ns[u]:
		if v == prev:
			continue
		nextu[u] = v
		s = dfs(v, u, ans)
		ss += s
		tmp = s - minus[v]
		ans[k] += int(tmp * (tmp - 1) / 2) + tmp
	st[k].pop()
	if st[k]:
		minus[nextu[st[k][-1]]] += ss
	else:
		minus0[k] += ss
	return ss
dfs(1, -1, ans)
for k in range(1, n + 1):
	tmp = n - minus0[k]
	ans[k] += int(tmp * (tmp - 1) / 2) + tmp
total = int(n * (n + 1) / 2)
for i in range(1, n + 1):
	print(total - ans[i])


import sys
n = int(input())
c = list(map(int, input().split()))
c = [x - 1 for x in c]
adj = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = tuple(map(int, input().split()))
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
size = [1 for i in range(n)]
stack = [[] for color in range(n)]
in_time = [-1 for i in range(n)]
out_time = [-1 for i in range(n)]
timer = 0
total = n * (n + 1) // 2
ans = [total for color in range(n)]

def dfs(parent, root):
	global timer
	in_time[root] = timer
	timer += 1
	for child in adj[root]:
		if parent == child:
			continue
		dfs(root, child)
		size[root] += size[child]
		cnt = size[child]
		while stack[c[root]]:
			x = stack[c[root]][-1]
			if in_time[x] > in_time[root] and out_time[x] != -1:
				cnt -= size[x]
				stack[c[root]].pop()
			else:
				break
		ans[c[root]] -= cnt * (cnt + 1) // 2
	out_time[root] = timer
	timer += 1
	stack[c[root]].append(root)
sys.setrecursionlimit(10 ** 6)
dfs(0, 0)
for color in range(n):
	cnt = n
	while len(stack[color]) > 0:
		x = stack[color][-1]
		cnt -= size[x]
		stack[color].pop()
	ans[color] -= cnt * (cnt + 1) // 2
	print(ans[color])


def f(l):
	r = sum(l) ** 2
	for x in l:
		r -= x ** 2
	r = r // 2
	r += sum(l) + 1
	return r
(N,) = map(int, input().split())
G = [set() for _ in range(N + 1)]
G2 = [set() for _ in range(N + 1)]
sz = [1 for _ in range(N + 1)]
X = [-1] + list(map(int, input().split()))
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].add(b)
	G[b].add(a)
stack = [1]
vs = set([1])
vs_dfs = []
while stack:
	v = stack.pop()
	vs_dfs.append(v)
	for u in G[v]:
		if u in vs:
			continue
		vs.add(u)
		G2[v].add(u)
		stack += [u]
G = None
for x in vs_dfs[::-1]:
	for u in G2[x]:
		sz[x] += sz[u]
stack = [1]
path = []
R = [0] * (N + 1)
kh = [[] for _ in range(N + 1)]
tt = [N - 1 for _ in range(N + 1)]
while stack:
	v = stack.pop()
	if v > 0:
		if path:
			parent = path[-1]
			kh[X[parent]].append(sz[v])
		path.append(v)
		tmp = []
		for u in G2[v]:
			tmp.append(sz[u])
			stack += [-v, u]
		if kh[X[v]]:
			tmp.append(kh[X[v]][-1] - 1 - sum(tmp))
			kh[X[v]][-1] -= sz[v]
		else:
			tmp.append(tt[X[v]] - sum(tmp))
			tt[X[v]] -= sz[v]
		R[X[v]] += f(tmp)
	else:
		c = path.pop()
		kh[X[-v]].pop()
for i in range(1, N + 1):
	print(R[i])


import collections
import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
colors = [int(x) - 1 for x in input().split()]
neighbors = collections.defaultdict(list)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	neighbors[a - 1].append(b - 1)
	neighbors[b - 1].append(a - 1)
subtree_sizes = [0] * N

def calc_sizes(node, parent):
	sz = 1
	for i in neighbors[node]:
		if i != parent:
			sz += calc_sizes(i, node)
	subtree_sizes[node] = sz
	return sz
calc_sizes(0, -1)
components = {c: {0: N} for c in range(N)}
components[colors[0]] = {}
color_stack = {c: [0] for c in range(N)}
color_stack[colors[0]] = []

def calc_components(node, parent):
	color_stack_pushed = False
	if parent >= 0 and colors[parent] != colors[node]:
		color_parent = color_stack[colors[node]][-1]
		components[colors[node]][color_parent] -= subtree_sizes[node]
		components[colors[parent]][node] = subtree_sizes[node]
		color_stack[colors[parent]].append(node)
		color_stack_pushed = True
	for i in neighbors[node]:
		if i != parent:
			calc_components(i, node)
	if color_stack_pushed:
		color_stack[colors[parent]].pop()
calc_components(0, -1)

def count_paths(n):
	return n * (n + 1) // 2
total_paths = count_paths(subtree_sizes[0])
for c in range(N):
	print(total_paths - sum((count_paths(size) for size in components[c].values())))


mod = 1000000007
eps = 10 ** (-9)

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

	def calc(n):
		return n * (n - 1) // 2 + n

	def merge(A, B):
		if len(A) > len(B):
			(A, B) = (B, A)
		for a in A:
			if a in B:
				B[a] += A[a]
			else:
				B[a] = A[a]
		return B
	N = int(input())
	C = list(map(int, input().split()))
	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()
	size = [1] * (N + 1)
	dic = [{} for _ in range(N + 1)]
	ans = [calc(N)] * (N + 1)
	for v in seq:
		for u in child[v]:
			size[v] += size[u]
		c = C[v - 1]
		for u in child[v]:
			if c in dic[u]:
				ans[c] -= calc(size[u] - dic[u][c])
			else:
				ans[c] -= calc(size[u])
			dic[v] = merge(dic[v], dic[u])
		dic[v][c] = size[v]
	for c in range(1, N + 1):
		if c in dic[1]:
			print(ans[c] - calc(N - dic[1][c]))
		else:
			print(ans[c] - calc(N))
main()


import bisect
import collections
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62

def lmi():
	return list(map(int, input().split()))

def llmi(n):
	return [lmi() for _ in range(n)]
N = int(input())
c_raw = lmi()
ab = llmi(N - 1)
adj = collections.defaultdict(list)
for (a, b) in ab:
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
total = N * (N + 1) // 2
visited = [False] * N
visited[0] = True
stacks = [[[0, 0]] for i in range(N)]
ans = [0] * N
curr = 1
color_stack = [[0, N] for _ in range(N)]

class Tree:

	def __init__(self, i, _c):
		self.i = i
		self.color = _c
		self.child_count = 0
		self.children = []

	def set_child_count(self, parent=-1):
		for node_index in adj[self.i]:
			if node_index == parent:
				continue
			self.children.append(node_index)
			trees[node_index].set_child_count(self.i)
			self.child_count += trees[node_index].child_count + 1

	def dfs(self):
		color_stack[self.color][-1] -= self.child_count + 1
		for node_index in self.children:
			color_stack[self.color].append(trees[node_index].child_count + 1)
			trees[node_index].dfs()
			ans[self.color] -= get_path_count(color_stack[self.color].pop())
trees = [Tree(i, c - 1) for (i, c) in enumerate(c_raw)]

def get_path_count(x):
	return x + x * (x - 1) // 2
ans = [get_path_count(N)] * N
trees[0].set_child_count()
trees[0].dfs()
for color in range(N):
	print(ans[color] - get_path_count(color_stack[color][-1]))


import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
C = [int(a) - 1 for a in input().split()]
X = [[] for i in range(N)]
head = [-1] * (N + 1)
to = [0] * (N - 1 << 1)
nxt = [0] * (N - 1 << 1)
for i in range(N - 1):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	nxt[i] = head[x]
	to[i] = y
	head[x] = i
	j = i + N - 1
	nxt[j] = head[y]
	to[j] = x
	head[y] = j

def EulerTour(n, i=0):
	f = lambda k: k * (k + 1) // 2
	USED = [0] * n
	ORG = [0] * n
	TMP = [0] * n
	ANS = [f(n)] * n
	P = [-1] * n
	ct = 0
	ET1 = [0] * n
	ET2 = [0] * n
	while i >= 0:
		e = head[i]
		if e < 0:
			ET2[i] = ct
			USED[C[i]] += 1 + TMP[i]
			if i:
				k = ET2[i] - ET1[i] + 1 - USED[C[P[i]]] + ORG[i]
				ANS[C[P[i]]] -= f(k)
				TMP[P[i]] += k
			i = P[i]
			continue
		j = to[e]
		if P[i] == j:
			head[i] = nxt[e]
			continue
		P[j] = i
		head[i] = nxt[e]
		i = j
		ORG[i] = USED[C[P[i]]]
		ct += 1
		ET1[i] = ct
	for i in range(n):
		ANS[i] -= f(n - USED[i])
	return ANS
print(*EulerTour(N, 0), sep='\n')


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
sys.setrecursionlimit(10 ** 6)

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

def resolve():
	N = ir()
	c = lr()
	ab = [[] for i in range(N)]
	for i in range(N - 1):
		(a, b) = lr()
		ab[a - 1].append(b - 1)
		ab[b - 1].append(a - 1)
	tot = N * (N + 1) // 2
	il = [0] * N
	ol = [0] * N
	cnt = [0]

	def dfs(u, p):
		cnt[0] += 1
		il[u] = cnt[0]
		for i in ab[u]:
			if i != p:
				dfs(i, u)
		ol[u] = cnt[0]
	dfs(0, -1)
	vs = [[] for i in range(N)]
	for i in range(N):
		vs[c[i] - 1].append(i)
	sl = Bit(N)
	for i in range(1, N + 1):
		sl.add(i, 1)
	for i in range(N):
		his = []
		ans = tot
		tvs = sorted(vs[i], key=lambda x: il[x])[::-1]
		for v in tvs:
			n = 1
			for j in ab[v]:
				if il[j] > il[v]:
					tmp = sl.sum(ol[j]) - sl.sum(il[j] - 1)
					ans -= tmp * (tmp + 1) // 2
					n += tmp
			sl.add(il[v], -n)
			his.append([il[v], n])
		tmp = sl.sum(ol[0]) - sl.sum(0)
		ans -= tmp * (tmp + 1) // 2
		for h in his:
			sl.add(h[0], h[1])
		print(ans)
resolve()


import sys
import itertools
sys.setrecursionlimit(3 * 10 ** 5)

class Node:

	def __init__(self, color):
		self.color = int(color) - 1
		self.children = []

	def add_child(self, node):
		self.children.append(node)

	@staticmethod
	def prepare_nodes(n):
		nodes = tuple(map(Node, input().split()))
		for _ in range(n - 1):
			(a, b) = [int(x) - 1 for x in input().split()]
			nodes[a].add_child(nodes[b])
			nodes[b].add_child(nodes[a])
		return nodes

def main():
	n = int(input())
	nodes = Node.prepare_nodes(n)
	dp = [0 for _ in range(n)]
	ans_list = [n * (n + 1) // 2 for _ in range(n)]

	def update_ans(s, color):
		ans_list[color] -= (s + dp[color]) * (s + dp[color] + 1) // 2

	def dfs(s, node, parent):
		color = node.color
		pre_s = s + dp[color]
		for child in node.children:
			if child == parent:
				continue
			dp[color] = -s
			s = dfs(s, child, node)
			update_ans(s, color)
		s += 1
		dp[color] = pre_s - s
		return s
	s = dfs(0, nodes[0], Node(-1))
	for i in range(n):
		update_ans(s, i)
		print(ans_list[i])
main()


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 6)
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
nn = lambda : list(stdin.readline().split())
ns = lambda : stdin.readline().rstrip()
n = ni()
c = [i - 1 for i in na()]
g = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = na()
	(a, b) = (a - 1, b - 1)
	g[a].append(b)
	g[b].append(a)

def EulerTour(n, X, i0):
	P = [-1] * n
	Q = [~i0, i0]
	ct = -1
	x = [0] * n
	y = [0] * n
	z = [0] * n
	ET = []
	ET1 = [0] * n
	ET2 = [0] * n
	DE = [0] * n
	de = -1
	ans = [n * (n + 1) // 2] * n
	while Q:
		i = Q.pop()
		if i < 0:
			i = ~i
			ET2[i] = ct
			de -= 1
			x[c[i]] += 1 + z[i]
			if i:
				p = P[i]
				k = ET2[i] - ET1[i] + 1 - x[c[p]] + y[i]
				ans[c[p]] -= k * (k + 1) // 2
				z[p] += k
			continue
		if i >= 0:
			ET.append(i)
			ct += 1
			if i:
				y[i] = x[c[P[i]]]
			if ET1[i] == 0:
				ET1[i] = ct
			de += 1
			DE[i] = de
		for a in X[i][::-1]:
			if a != P[i]:
				P[a] = i
				for k in range(len(X[a])):
					if X[a][k] == i:
						del X[a][k]
						break
				Q.append(~a)
				Q.append(a)
	for i in range(n):
		ans[i] -= (n - x[i]) * (n - x[i] + 1) // 2
	return ans
print(*EulerTour(n, g, 0), sep='\n')


N = int(input())
Cs = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
degs = [0] * N
clusters = [[] for _ in range(N)]

def go(curr, fro):
	col = Cs[curr] - 1
	deg = 1
	clust = {}
	for n in adj[curr]:
		if n == fro:
			continue
		(ch_deg, ch_clust) = (yield (n, curr))
		clusters[col].append(ch_deg - ch_clust.get(col, 0))
		if len(ch_clust) > len(clust):
			(clust, ch_clust) = (ch_clust, clust)
		for (k, v) in ch_clust.items():
			clust[k] = clust.get(k, 0) + v
		deg += ch_deg
	clust[col] = deg
	return (deg, clust)

def tramp(gen_fn, *args):
	stack = [gen_fn(*args)]
	val = None
	while stack:
		gen = stack[-1]
		try:
			params = gen.send(val)
		except StopIteration as e:
			stack.pop()
			val = e.value
		else:
			stack.append(go(*params))
			val = None
	return val
(_, root_clust) = tramp(go, 0, -1)
for i in range(N):
	clusters[i].append(N - root_clust.get(i, 0))
for clust in clusters:
	tot = (N * N + N) // 2
	for cnt in clust:
		tot -= (cnt * cnt + cnt) // 2
	print(tot)


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

class BIT:

	def __init__(self, n, x=1):
		self.n = n
		self.T = [0] * (n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.T[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		ret = 0
		while i > 0:
			ret += self.T[i]
			i -= i & -i
		return ret

	def sump(self, l, r):
		return self.sum(r - 1) - self.sum(l - 1)
N = int(input())
C = [[] for _ in [0] * N]
for (i, c) in enumerate(map(int, input().split())):
	C[c - 1].append(i)
G = [[] for _ in [0] * N]
for _ in [0] * (N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
pin = [-1] * N
pout = [-1] * N
k = 0

def dfs(v=0, p=-1):
	global k
	pin[v] = k
	k += 1
	for u in G[v]:
		if u == p:
			continue
		dfs(u, v)
	pout[v] = k

def f(x):
	return x * (x + 1) // 2
dfs()
b = BIT(N)
for i in range(N):
	b.add(i, 1)
total = f(N)
for c in C:
	c.sort(key=lambda x: pin[x], reverse=True)
	history = []
	ans = total
	for v in c:
		sub = 1
		for u in G[v]:
			if pin[u] < pin[v]:
				continue
			num = b.sump(pin[u], pout[u])
			ans -= f(num)
			sub += num
		b.add(pin[v], -sub)
		history.append((pin[v], sub))
	ans -= f(b.sump(0, N))
	for h in history:
		b.add(*h)
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
C = [int(a) - 1 for a in input().split()]
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)

def EulerTour(n, X, i0):
	f = lambda k: k * (k + 1) // 2
	USED = [0] * n
	ORG = [0] * n
	TMP = [0] * n
	P = [-1] * n
	Q = [~i0, i0]
	ct = -1
	ET1 = [0] * n
	ET2 = [0] * n
	ANS = [f(n)] * n
	while Q:
		i = Q.pop()
		if i < 0:
			i = ~i
			ET2[i] = ct
			USED[C[i]] += 1 + TMP[i]
			if i:
				p = P[i]
				k = ET2[i] - ET1[i] + 1 - USED[C[p]] + ORG[i]
				ANS[C[p]] -= f(k)
				TMP[p] += k
			continue
		if i >= 0:
			if i:
				ORG[i] = USED[C[P[i]]]
			ct += 1
			if ET1[i] == 0:
				ET1[i] = ct
		for a in X[i][::-1]:
			if a != P[i]:
				P[a] = i
				for k in range(len(X[a])):
					if X[a][k] == i:
						del X[a][k]
						break
				Q.append(~a)
				Q.append(a)
	for i in range(n):
		ANS[i] -= f(n - USED[i])
	return ANS
print(*EulerTour(N, X, 0), sep='\n')


import sys
sys.setrecursionlimit(10 ** 9)
mod = 1000000007
INF = 110110110
N = int(input())
c = list(map(int, input().split()))
for i in range(N):
	c[i] -= 1
E = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = list(map(int, input().split()))
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
child = [0] * N

def dfs(now, par):
	res = 1
	for to in E[now]:
		if to == par:
			continue
		res += dfs(to, now)
	child[now] = res
	return res
dfs(0, -1)
ans = [0] * N
ok = [N] * N

def solve(now, par):
	memo = ok[c[now]]
	up = ok[c[now]] - child[now]
	num = [up]
	for to in E[now]:
		if to == par:
			continue
		num.append(child[to])
	S = sum(num)
	ans[c[now]] += S + 1
	for n in num:
		S -= n
		ans[c[now]] += S * n
	for to in E[now]:
		if to == par:
			continue
		ok[c[now]] = child[to]
		solve(to, now)
	ok[c[now]] = memo - child[now]
solve(0, -1)
for i in range(N):
	print(ans[i])


import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf
import math
import bisect

class BIT:
	NORMAL = 0
	ROLLBACK = 1

	def __init__(self, size):
		self.size = size
		self.data = [0] * (size + 1)
		self.status = BIT.NORMAL
		self.history = []

	def add(self, pos, val):
		assert pos > 0, pos
		if self.status == BIT.NORMAL:
			self.history.append((pos, val))
		k = pos
		while k <= self.size:
			self.data[k] += val
			k += k & -k

	def sum(self, pos):
		s = 0
		k = pos
		while k > 0:
			s += self.data[k]
			k -= k & -k
		return s

	def sum_section(self, frm, to):
		to_val = self.sum(to)
		frm_val = self.sum(frm)
		return to_val - frm_val

	def save(self):
		self.history = []

	def rollback(self):
		self.status = BIT.ROLLBACK
		for (pos, val) in self.history:
			self.add(pos, -1 * val)
		self.history = []
		self.status = BIT.NORMAL

class Graph:

	def __init__(self, size):
		self.size = size
		self.vertices = [0] * size
		self.edges = [None] * size
		for i in range(size):
			self.edges[i] = []

	def add_edge(self, frm, to):
		self.edges[frm].append(to)
		self.edges[to].append(frm)

def make_mybit(size):
	bit = BIT(size)
	for i in range(size):
		bit.add(i + 1, 1)
	bit.save()
	return bit

def init_color_s(size):
	color_s = [None] * graph.size
	for i in range(graph.size):
		color_s[i] = []
	return color_s

def dfs(graph):
	parent_s = [0] * graph.size
	in_s = [0] * graph.size
	out_s = [0] * graph.size
	order = 0
	color_s = init_color_s(graph.size)

	def _dfs(v, prev):
		nonlocal order
		order += 1
		parent_s[v] = prev
		in_s[v] = order
		c = graph.vertices[v]
		color_s[c].append(v)
		for to in graph.edges[v]:
			if to == prev:
				continue
			_dfs(to, v)
		out_s[v] = order
	_dfs(0, -1)
	return (parent_s, in_s, out_s, color_s)

def calc(v):
	return v * (v + 1) // 2

def get_connected(bit, v, in_s, out_s):
	large_key = out_s[v]
	small_key = in_s[v] - 1
	return bit.sum_section(small_key, large_key)

def calc_for(bit, v, in_s, out_s):
	connected = get_connected(bit, v, in_s, out_s)
	return calc(connected)

def cut(bit, v, in_s, out_s):
	connected = get_connected(bit, v, in_s, out_s)
	bit.add(in_s[v], -1 * connected)

def solve(n, graph):
	bit = make_mybit(graph.size)
	(parent_s, in_s, out_s, color_s) = dfs(graph)
	for same_color_s in color_s:
		ans = calc(graph.size)
		bit.rollback()
		for v in same_color_s[::-1]:
			for to in graph.edges[v]:
				if to == parent_s[v]:
					continue
				ans -= calc_for(bit, to, in_s, out_s)
			cut(bit, v, in_s, out_s)
		ans -= calc_for(bit, 0, in_s, out_s)
		print(ans)
n = int(input())
graph = Graph(n)
vertices = list(map(int, input().split()))
for (i, c) in enumerate(vertices):
	vertices[i] = c - 1
graph.vertices = vertices
for _ in range(n - 1):
	(frm, to) = list(map(int, input().split()))
	frm -= 1
	to -= 1
	graph.add_edge(frm, to)
solve(n, graph)


import sys
sys.setrecursionlimit(10 ** 6)

def main():
	n = int(input())
	color = list(map(int, input().split()))
	nodes = [[] for i in range(n)]
	cut = [[0] for i in range(n + 1)]
	ans = [0] * (n + 1)
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		nodes[a - 1].append(b - 1)
		nodes[b - 1].append(a - 1)

	def num(p, parent):
		s = 0
		for child in nodes[p]:
			if child == parent:
				continue
			cut[color[p]].append(0)
			nc = num(child, p)
			group = nc - cut[color[p]].pop()
			ans[color[p]] += group * (group + 1) // 2
			s += nc
		s += 1
		cut[color[p]][-1] += s
		return s
	num(0, -1)
	for (a, c) in zip(ans[1:], cut[1:]):
		group = n - c[0]
		c = group * (group + 1) // 2
		print(n * (n + 1) // 2 - c - a)
main()


import sys
sys.setrecursionlimit(10 ** 6)

def input():
	return sys.stdin.readline()[:-1]
n = int(input())
c = list(map(int, input().split()))
ans = [n * (n + 1) // 2 for _ in range(n)]
for i in range(n):
	c[i] -= 1
adj = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
s = 0
dp = [0 for _ in range(n)]

def dfs(x, p):
	nonlocal s
	pres = s + dp[c[x]]
	for v in adj[x]:
		if v == p:
			continue
		dp[c[x]] = -s
		dfs(v, x)
		ans[c[x]] -= (s + dp[c[x]]) * (s + dp[c[x]] + 1) // 2
	s += 1
	dp[c[x]] = pres - s
	return
dfs(0, -1)
for i in range(n):
	ans[i] -= (s + dp[i]) * (s + dp[i] + 1) // 2
print(*ans, sep='\n')


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
c = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
s = [1]
order = []
vis = [0] * (N + 1)
ps = [0] * (N + 1)
while len(s):
	x = s.pop()
	vis[x] = 1
	order.append(x)
	for y in e[x]:
		if vis[y]:
			continue
		s.append(y)
		ps[y] = x
size = [1] * (N + 1)
res = [0] * (N + 1)
d = [dd(int) for _ in range(N + 1)]
for x in order[::-1]:
	for y in e[x]:
		if y == ps[x]:
			continue
		size[x] += size[y]
		res[c[x]] += (size[y] - d[y][c[x]]) * (size[y] - d[y][c[x]] + 1) // 2
		if len(d[x]) < len(d[y]):
			(d[x], d[y]) = (d[y], d[x])
		for z in d[y]:
			d[x][z] += d[y][z]
	d[x][c[x]] = size[x]
for i in range(1, N + 1):
	print(N * (N + 1) // 2 - res[i] - (N - d[1][i]) * (N - d[1][i] + 1) // 2)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def EulerTour(graph, root=1):
	N = len(graph) - 1
	parent = [0] * (N + 1)
	stack = [-root, root]
	tour = []
	ind_L = [0] * (N + 1)
	ind_R = [0] * (N + 1)
	i = -1
	while stack:
		v = stack.pop()
		tour.append(v)
		i += 1
		if v > 0:
			ind_L[v] = i
			p = parent[v]
			for w in graph[v]:
				if w == p:
					continue
				parent[w] = v
				stack.append(-w)
				stack.append(w)
		else:
			ind_R[-v] = i
	return (tour, ind_L, ind_R, parent)
N = int(readline())
graph = [[] for _ in range(N + 1)]
C = (0,) + tuple(map(int, readline().split()))
m = map(int, read().split())
for (a, b) in zip(m, m):
	graph[a].append(b)
	graph[b].append(a)
(tour, ind_L, ind_R, parent) = EulerTour(graph)
removed = [0] * (N + 1)
answer = [N * (N + 1) // 2] * (N + 1)
memo = [0] * (N + 1)
for v in tour:
	if v > 0:
		memo[v] = removed[C[parent[v]]]
	else:
		v = -v
		removed[C[v]] += 1
		c = C[parent[v]]
		x = (ind_R[v] - ind_L[v]) // 2 + 1
		x -= removed[c] - memo[v]
		answer[c] -= x * (x + 1) // 2
		removed[c] += x
for (i, x) in enumerate(removed):
	x = N - x
	answer[i] -= x * (x + 1) // 2
print('\n'.join(map(str, answer[1:])))


import sys
from collections import deque
input = sys.stdin.buffer.readline
sys.setrecursionlimit(2 * 10 ** 5)
N = int(input())
c = list(map(int, input().split()))
edge = [[] for i in range(N + 1)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)
deq = deque([1])
parent = [-1 for i in range(N + 1)]
parent[1] = 0
topo = []
while deq:
	v = deq.popleft()
	topo.append(v)
	for nv in edge[v]:
		if parent[nv] == -1:
			parent[nv] = v
			deq.append(nv)
topo = topo[::-1]
vertex = []
size = [1 for i in range(N + 1)]
size[0] = N

def euler_tour(v, pv):
	vertex.append(v)
	for nv in edge[v]:
		if nv != pv:
			euler_tour(nv, v)
			size[v] += size[nv]
	vertex.append(v)
euler_tour(1, 0)
color_tree_edge = [{c[i]: []} for i in range(N)]
color_tree_edge = [{c: [] for c in range(1, N + 1)}] + color_tree_edge
for v in range(2, N + 1):
	color_tree_edge[v][c[parent[v] - 1]] = []
parent = [0 for i in range(N + 1)]
visit = [None for i in range(N + 1)]
for v in vertex:
	if visit[v] is None:
		visit[v] = {}
		for nc in color_tree_edge[v]:
			color_tree_edge[parent[nc]][nc].append(v)
			visit[v][nc] = parent[nc]
			parent[nc] = v
	else:
		for nc in visit[v]:
			parent[nc] = visit[v][nc]

def bfs(color):
	deq = deque([0])
	res = []
	while deq:
		v = deq.popleft()
		res.append(v)
		for nv in color_tree_edge[v][color]:
			deq.append(nv)
	return res[::-1]
ans = [0] * (N + 1)
for color in range(1, N + 1):
	vertex = bfs(color)
	res = N * (N + 1) // 2
	for v in vertex:
		if v == 0 or c[v - 1] != color:
			tmp = size[v]
			for nv in color_tree_edge[v][color]:
				tmp -= size[nv]
			res -= tmp * (tmp + 1) // 2
	ans[color] = res
print('\n'.join(map(str, ans[1:])))


import sys
sys.setrecursionlimit(210000)

class Node(object):

	def __init__(self, idx, color):
		self.idx = idx
		self.color = color
		self.edges = []
		self.traced = False

	def trace(self, counts, excludes):
		self.traced = True
		num = 1
		for edge in self.edges:
			if edge.traced:
				continue
			excludes[self.color].append(0)
			n = edge.trace(counts, excludes)
			p = n - excludes[self.color].pop()
			counts[self.color] += p * (p - 1) // 2 + p
			num += n
		excludes[self.color][-1] += num
		return num

def main():
	N = int(input())
	nodes = [Node(i, v - 1) for (i, v) in enumerate(map(int, input().split()))]
	counts = [0] * N
	excludes = [[0] for _ in range(N)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		nodes[a - 1].edges.append(nodes[b - 1])
		nodes[b - 1].edges.append(nodes[a - 1])
	num = nodes[0].trace(counts, excludes)
	pair = num * (num - 1) // 2 + num
	for i in range(len(counts)):
		p = num - excludes[i][0]
		counts[i] += p * (p - 1) // 2 + p
	for c in counts:
		print(pair - c)
main()


N = int(input())
Cs = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
under_col = [0] * N
ans = [0] * N

def tri(n):
	return n * (n + 1) // 2

def go(curr, fro):
	col = Cs[curr] - 1
	prev_under = under_col[col]
	deg = 1
	for n in adj[curr]:
		if n == fro:
			continue
		curr_under = under_col[col]
		ch_deg = (yield go(n, curr))
		diff_under = under_col[col] - curr_under
		ans[col] += tri(ch_deg - diff_under)
		deg += ch_deg
	under_col[col] = prev_under + deg
	return deg

def tramp(gen):
	stack = [gen]
	val = None
	while stack:
		try:
			stack.append(stack[-1].send(val))
			val = None
		except StopIteration as e:
			stack.pop()
			val = e.value
	return val
tramp(go(0, -1))
for i in range(N):
	ans[i] += tri(N - under_col[i])
	print(tri(N) - ans[i])


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class BitSum:

	def __init__(self, n):
		self.n = n + 3
		self.table = [0] * (self.n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.table[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		res = 0
		while i > 0:
			res += self.table[i]
			i -= i & -i
		return res

def main():

	def dfs(u=0, pu=-1):
		ll[u] = len(uu)
		uu.append(u)
		for v in to[u]:
			if v == pu:
				continue
			dfs(v, u)
		rr[u] = len(uu)

	def sumlr(l, r):
		return bit.sum(r - 1) - bit.sum(l - 1)
	n = II()
	cc = LI1()
	to = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = MI1()
		to[a].append(b)
		to[b].append(a)
	ll = [-1] * n
	rr = [-1] * n
	uu = []
	dfs()
	bit = BitSum(n)
	for u in range(n):
		bit.add(u, 1)
	ctou = defaultdict(list)
	for (u, c) in enumerate(cc):
		ctou[c].append(u)
	pn = lambda x: x * (x + 1) // 2
	for c in range(n):
		log = []
		ans = pn(n)
		for u in sorted(ctou[c], key=lambda x: -ll[x]):
			us = 1
			for v in to[u]:
				if ll[v] < ll[u]:
					continue
				vs = sumlr(ll[v], rr[v])
				ans -= pn(vs)
				us += vs
			bit.add(ll[u], -us)
			log.append((ll[u], us))
		vs = sumlr(0, n)
		ans -= pn(vs)
		print(ans)
		for (i, s) in log:
			bit.add(i, s)
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
c = list(map(int, input().split()))
for i in range(N):
	c[i] -= 1
edge = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
subtree = [1] * N

def size(v, pv):
	for nv in edge[v]:
		if nv != pv:
			size(nv, v)
			subtree[v] += subtree[nv]
size(0, -1)
data = [[] for i in range(N)]
Parent = [[0] for i in range(N)]
parent = [0] * N

def dfs(v, pv, nop):
	pp = parent[nop]
	parent[nop] = v
	Parent[nop].append(v)
	data[c[v]].append((parent[c[v]], v))
	for nv in edge[v]:
		if nv != pv:
			dfs(nv, v, c[v])
	parent[nop] = pp
dfs(0, -1, 0)
for i in range(N):
	dic = {v: subtree[v] for v in Parent[i]}
	for (p, ch) in data[i]:
		dic[p] -= subtree[ch]
	res = N * (N + 1) // 2
	for p in dic:
		res -= dic[p] * (dic[p] + 1) // 2
	print(res)


def euler_tour(tree: list, root: int):
	n = len(tree)
	par = {root: -1}
	trail = []
	is_up = []
	stack = [root]
	while stack:
		v = stack.pop()
		if v >= 0:
			trail.append(v)
			is_up.append(0)
			stack.append(~v)
			for nxt_v in tree[v]:
				if nxt_v not in par:
					par[nxt_v] = v
					stack.append(nxt_v)
		else:
			if ~v == root:
				continue
			trail.append(par[~v])
			is_up.append(1)
	return (trail, is_up)

class BIT:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def build(self, array):
		for i in range(1, self.size + 1):
			if i - 1 + (i & -i) >= self.size:
				self.bit[i] = array[i - 1]
			else:
				self.bit[i] = array[i - 1] - array[i + (i & -i) - 1]

	def _add(self, i, val):
		while i > 0:
			self.bit[i] += val
			i -= i & -i

	def get_val(self, i):
		i = i + 1
		s = 0
		while i <= self.size:
			s += self.bit[i]
			i += i & -i
		return s

	def add(self, l, r, val):
		self._add(r, val)
		self._add(l, -val)
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
c = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(n - 1)]
tree = [[] for i in range(n)]
for (a, b) in info:
	a -= 1
	b -= 1
	tree[a].append(b)
	tree[b].append(a)
plus = n + 1
for i in range(1, n):
	if len(tree[i]) == 1:
		info.append([i + 1, plus])
		plus += 1
info.append([1, plus])
new_n = len(info) + 1
tree = [[] for i in range(new_n)]
for (a, b) in info:
	a -= 1
	b -= 1
	tree[a].append(b)
	tree[b].append(a)
root = new_n - 1
(et, is_up) = euler_tour(tree, root)
bit = BIT(n)
stack = [[] for i in range(n)]
ans = [0] * n
for i in range(len(et)):
	if et[i] >= n:
		continue
	if is_up[i]:
		ind = i
		i = c[et[i]] - 1
		val = bit.get_val(i)
		ans[i] += val * (val + 1) // 2
		bit.add(i, i + 1, -val)
		if len(stack[i]) >= 1 and is_up[ind + 1]:
			tmp = stack[i].pop()
			bit.add(i, i + 1, tmp)
	else:
		i = c[et[i]] - 1
		val = bit.get_val(i)
		stack[i].append(val)
		bit.add(0, n, 1)
		bit.add(i, i + 1, -(val + 1))
for i in range(n):
	val = bit.get_val(i)
	ans[i] += val * (val + 1) // 2
for i in range(n):
	print(n * (n + 1) // 2 - ans[i])


def main():
	import sys
	sys.setrecursionlimit(10 ** 9)
	input = sys.stdin.readline
	N = int(input())
	C = [c - 1 for c in map(int, input().split())]
	tree = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		tree[a - 1].append(b - 1)
		tree[b - 1].append(a - 1)
	size_subtree = [1] * N
	num_v = [0] * N
	ans = [0] * N

	def dfs(v_now, v_parent, color_parent):
		color_now = C[v_now]
		num_v_now = num_v[color_now]
		num_v_parent = num_v[color_parent]
		for v2 in tree[v_now]:
			if v2 == v_parent:
				continue
			dfs(v2, v_now, color_now)
			size_subtree[v_now] += size_subtree[v2]
		num_v[color_now] = num_v_now + size_subtree[v_now]
		if color_parent != -1:
			k = size_subtree[v_now] - (num_v[color_parent] - num_v_parent)
			ans[color_parent] += k * (k + 1) // 2
	dfs(0, -1, -1)
	for color in range(N):
		if color == C[0]:
			continue
		k = N - num_v[color]
		ans[color] += k * (k + 1) // 2
	numAll = N * (N + 1) // 2
	ans = [numAll - ans for ans in ans]
	print(*ans, sep='\n')
main()


import sys
sys.setrecursionlimit(2 * 10 ** 5)
N = int(input())
colors = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(N - 1)]
graph = [[] for i in range(N + 1)]
for (u, v) in edges:
	graph[u].append(v)
	graph[v].append(u)
parent = {1: None}
children = {}

def rootTree(node):
	children[node] = []
	for nbr in graph[node]:
		if nbr not in parent:
			parent[nbr] = node
			children[node].append(nbr)
			rootTree(nbr)
rootTree(1)
colorlessCount = [0 for c in range(N + 1)]
colorlessTime = [0 for c in range(N + 1)]
t = 0

def buildComps(node):
	global t
	currColor = colors[node - 1]
	t += 1
	colorlessTime[currColor] += 1
	for child in children[node]:
		oldCount = t - colorlessTime[currColor]
		colorlessTime[currColor] = t
		buildComps(child)
		s = t - colorlessTime[currColor]
		colorlessCount[currColor] += s * (s + 1) // 2
		colorlessTime[currColor] = t - oldCount
buildComps(1)
for c in range(1, N + 1):
	s = t - colorlessTime[c]
	colorlessCount[c] += s * (s + 1) // 2
maxPairs = N * (N + 1) // 2
for c in range(1, N + 1):
	print(maxPairs - colorlessCount[c])


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)

def dfs(v, p, ccc, links, ans):
	ret_colors = defaultdict(int)
	ret_count = 1
	cv = ccc[v]
	for u in links[v]:
		if u == p:
			continue
		(sub_colors, sub_count) = dfs(u, v, ccc, links, ans)
		cc = sub_count - sub_colors[cv]
		ans[cv] -= cc * (cc + 1) // 2
		ret_count += sub_count
		if len(ret_colors) < len(sub_colors):
			(ret_colors, sub_colors) = (sub_colors, ret_colors)
		for (c, cnt) in sub_colors.items():
			ret_colors[c] += cnt
	ret_colors[cv] = ret_count
	return (ret_colors, ret_count)

def solve(n, ccc, links):
	if n == 1:
		return [1]
	all_pair = n * (n + 1) // 2
	ans = [all_pair] * (n + 1)
	(colors, count) = dfs(0, -1, ccc, links, ans)
	assert count == n
	for c in range(1, n + 1):
		cc = n - colors[c]
		ans[c] -= cc * (cc + 1) // 2
	return ans[1:]
(n, *cab) = map(int, sys.stdin.buffer.read().split())
ccc = cab[:n]
links = [set() for _ in range(n)]
for (a, b) in zip(cab[n + 0::2], cab[n + 1::2]):
	a -= 1
	b -= 1
	links[a].add(b)
	links[b].add(a)
print('\n'.join(map(str, solve(n, ccc, links))))


import sys

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

def solve():
	n = int(input())
	c = list(map(lambda x: int(x) - 1, input().split()))
	adj = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		adj[a].append(b)
		adj[b].append(a)
	stack = [[] for color in range(n)]
	size = [1] * n
	in_time = [-1] * n
	out_time = [-1] * n
	timer = 0
	total = n * (n + 1) // 2
	ans = [total] * n

	def dfs(parent, root):
		nonlocal timer
		in_time[root] = timer
		timer += 1
		for child in adj[root]:
			if parent == child:
				continue
			dfs(root, child)
			size[root] += size[child]
			cnt = size[child]
			while stack[c[root]]:
				x = stack[c[root]][-1]
				if in_time[x] > in_time[root] and out_time[x] != -1:
					cnt -= size[x]
					stack[c[root]].pop()
				else:
					break
			ans[c[root]] -= cnt * (cnt + 1) // 2
		out_time[root] = timer
		timer += 1
		stack[c[root]].append(root)
	sys.setrecursionlimit(10 ** 6)
	dfs(0, 0)
	for color in range(n):
		cnt = n
		while len(stack[color]) > 0:
			x = stack[color][-1]
			cnt -= size[x]
			stack[color].pop()
		ans[color] -= cnt * (cnt + 1) // 2
		print(ans[color])
solve()


import sys
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict
INF = float('inf')
MOD = 10 ** 9 + 7

class Graph(object):

	def __init__(self, N):
		self.N = N
		self.E = defaultdict(list)

	def add_edge(self, f, t, w=1):
		self.E[f].append(t)
		self.E[t].append(f)

def make_order(g, v):
	seen = [False] * g.N
	last_order = [-1] * g.N
	parent = [-1] * g.N
	size = [1] * g.N
	counter = {'last': 0}

	def recur(v):
		seen[v] = True
		for to in g.E[v]:
			if seen[to] == True:
				continue
			parent[to] = v
			recur(to)
			size[v] += size[to]
		last_order[counter['last']] = v
		counter['last'] += 1
	recur(v)
	return (last_order, parent, size)

def merge(d: dict, e: dict):
	if len(d) < len(e):
		(d, e) = (e, d)
	for k in e:
		d[k] += e[k]
	return d
N = int(input())
c = [x - 1 for x in map(int, input().split())]
A = [None] * (N - 1)
B = [None] * (N - 1)
for i in range(N - 1):
	(A[i], B[i]) = map(int, input().split())
g = Graph(N)
for (a, b) in zip(A, B):
	g.add_edge(a - 1, b - 1)
ans = [0] * N
ret = {}
(last_order, parent, size) = make_order(g, 0)
for curr in last_order:
	cn = c[curr]
	rrr = defaultdict(int)
	for dest in g.E[curr]:
		if dest == parent[curr]:
			continue
		child = ret.pop(dest)
		n = size[dest] - child[cn]
		ans[cn] += n * (n + 1) // 2
		rrr = merge(rrr, child)
	rrr[cn] = size[curr]
	ret[curr] = rrr
tot = N * (N + 1) // 2
for color in range(N):
	if color != c[0]:
		n = N - ret[0][color]
		ans[color] += n * (n + 1) // 2
	print(tot - ans[color])


import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
C = [int(a) - 1 for a in input().split()]
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)

def EulerTour(n, X, i0):
	f = lambda k: k * (k + 1) // 2
	USED = [0] * n
	ORG = [0] * n
	TMP = [0] * n
	P = [-1] * n
	ct = -1
	ET1 = [0] * n
	ET2 = [0] * n
	ANS = [f(n)] * n
	IND = [0] * n
	i = i0
	while i >= 0:
		ind = IND[i]
		if ind == 0:
			if i:
				ORG[i] = USED[C[P[i]]]
			ct += 1
			ET1[i] = ct
		if ind >= len(X[i]):
			ET2[i] = ct
			USED[C[i]] += 1 + TMP[i]
			if i:
				k = ET2[i] - ET1[i] + 1 - USED[C[P[i]]] + ORG[i]
				ANS[C[P[i]]] -= f(k)
				TMP[P[i]] += k
			i = P[i]
			continue
		j = X[i][ind]
		if P[i] == j:
			IND[i] += 1
			continue
		P[j] = i
		IND[i] += 1
		i = j
	for i in range(n):
		ANS[i] -= f(n - USED[i])
	return ANS
print(*EulerTour(N, X, 0), sep='\n')


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(505050)
N = int(input())
C = [int(c) - 1 for c in input().split()]
G = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
Cnt = [0] * N
Ans = [0] * N
Siz = [0] * N

def dfs1(v):
	siz = 1
	for u in G[v]:
		G[u].remove(v)
		siz += dfs1(u)
	Siz[v] = siz
	return siz

def dfs(v):
	color = C[v]
	cnt_old = Cnt[color]
	siz = 1
	siz_up = N
	for u in G[v]:
		Cnt[color] = N - Siz[u]
		s = dfs(u)
		siz += s
		siz_up -= s
		Ans[color] += s * (siz_up - cnt_old)
	Ans[color] += siz_up - cnt_old
	Cnt[color] = cnt_old + siz
	return siz
dfs1(0)
dfs(0)
print('\n'.join(map(str, Ans)))


import sys
input = sys.stdin.readline
n = int(input())
color = list(map(lambda x: int(x) - 1, input().split()))
out = [0] * n
total = n * (n + 1)
total //= 2
stacks = [[[0, 0]] for i in range(n)]
segs = [[] for i in range(n)]
adj = [[] for i in range(n)]
visited = [False] * n
dfs = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
visited[0] = True
dfs.append(0)
stacks[color[0]].append([1, 0])
curr = 1
while dfs:
	node = dfs[-1]
	(prev, rem) = stacks[color[node]][-1]
	diff = curr - prev - rem
	out[color[node]] += diff * (diff + 1) // 2
	stacks[color[node]][-1][1] += diff
	if adj[node]:
		nex = adj[node].pop()
		if not visited[nex]:
			visited[nex] = True
			dfs.append(nex)
			curr += 1
			stacks[color[nex]].append([curr, 0])
	else:
		dfs.pop()
		(prev, rem) = stacks[color[node]].pop()
		stacks[color[node]][-1][1] += rem + 1
for i in range(n):
	diff = curr - stacks[i][0][1]
	out[i] += diff * (diff + 1) // 2
	out[i] = total - out[i]
print('\n'.join(map(str, out)))