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: interview

Starter code:

Solutions:
import sys
from collections import defaultdict

# 再帰制限を緩和するおまじない
sys.setrecursionlimit(10**6)

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

# 部分木のサイズと、「色iを封鎖したときに到達できない頂点の個数」を持つ辞書を返す
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
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")

#!/usr/bin/env python3
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] = list(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
sys.setrecursionlimit(10**6)
 
N = int(input())  # 頂点数
C = [int(x) - 1  for x in input().split()]  # 頂点の色番号 (1~N) -> (0~N-1)
 
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)  # 色ごとに stack しておく
    
    s = 1  # 部分木サイズ（を格納する）
    for v in E[u]:
        if v == p:
            continue
            
        child[u] = 0  # v の方向にある子孫のうち辿れる頂点の数 = s - 子孫にある、同色を根とする部分木のサイズの合計
        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  # 辿っている子の中でのの残り数　とりあえず 0で初期化
root_size = [N] * 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**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)

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
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
    done = [0] * n
    while Q:
        i = Q.pop()
        if i < 0:
            i = ~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
            continue
        done[i] = 1
        if i: ORG[i] = USED[C[P[i]]]
        ct += 1
        ET1[i] = ct
        for a in X[i]:
            if done[a]: continue
            P[a] = i
            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
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  # n_st[i] = (頂点iの部分木の頂点数)
cnt = [0] * n  # cnt[i] = (訪問済み頂点のうち、色iを通過しないとたどり着けない頂点数)
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
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


n = int(input())
C = list(map(int,input().split()))

# ci = [set() for _ in range(n)]
# for i,c in enumerate(C):
#     ci[c-1].add(i)

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
# index:color
reached = [False]*n
size = [0]*n
# index:vertex

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()
    # size[p] += s
    if cparent[c]:
        size[cparent[c][-1]] -= s
    else:
        root_size[c] -= s
    # ans[c] -= size[p] * (size[p] - 1)//2
    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))


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
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 = map(int,input().split())
    a -= 1
    b -= 1
    path[a].add(b)
    path[b].add(a)
    
ans = [n*(n+1)//2]*n
size = [0]*n
cparent = [[] for _ in range(n)]
reached = [False]*n
root_size = [n]*n

def dfs (p):
    c = C[p] - 1
    cparent[c].append(p)
    s = 1
    for nxt in path[p]:
        #print (nxt)
        
        if reached[nxt]:
            continue
        size[p] = 0
        reached[nxt] = True
        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[0] = True
dfs (0)

for i in range(n):
    print (ans[i]-root_size[i]*(root_size[i]+1)//2)

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


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)

    # 1回以上 > 全体 - 1回も通らない
    # 選べる数 = n(n+1)//2
    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()


#!/usr/bin/env python3
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] = list(map(int, input().split()))

g = Graph(N)
for a, b in zip(A, B):
    g.add_edge(a-1, b-1)

# k=1, 2, ..., Nに対して
# 色kが塗られている頂点を一度以上通るような単純パスの数を求める
# 全パスの個数 - 色kが塗られている頂点を一度も通らない単純パスの数
# 全パスの個数はN*(N+1)/2

# グラフを色kのノードで分割して、部分グラフ内での単純パスの総数を求めれば良い
# 各ノードに状態として辞書をもたせる。
# x辞書は色iを通らずに到達可能な頂点の数を持つ。
# o辞書は色iを通らずに到達不可能な頂点の数を持つ。

# 回答用
ans = [0]*N


def f(curr, par=-1):
    # 再帰関数
    # curr: 現在の節点
    # par : 親節点の番号
    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
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:
        if IND[i] == 0:
            if i: ORG[i] = USED[C[P[i]]]
            ct += 1
            ET1[i] = ct
        
        if IND[i] >= 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
        
        if P[i] == X[i][IND[i]]:
            IND[i] += 1
            continue
        P[X[i][IND[i]]] = i
        IND[i], i = IND[i] + 1, X[i][IND[i]]
    
    for i in range(n):
        ANS[i] -= f(n - USED[i])
    return ANS

print(*EulerTour(N, X, 0), sep = "\n")

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 = [len(x) for x in X]
    i = i0
    while i >= 0:
        ind = IND[i]
        if not ind:
            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 - 1]
        if P[i] == j:
            IND[i] -= 1
            continue
        
        P[j] = i
        IND[i] -= 1
        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, X, 0), sep = "\n")

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)
# print(size)
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):
    # print(h[col])
    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
            # print(v, q)
            p.append(v)
        else:
            p.append(v)
    q = n - acc[-1]
    # print(-1, q)
    ans[col] -= q*(q+1)//2
print(*ans[1:], sep='\n')