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)  # 根を深さ 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(A, B):

    if len(A) < len(B):

        A, B = B, A

    for key, cnt in B.items():

        A[key] += cnt

    return A





dp = [defaultdict(int) for _ in range(N + 1)]  # 部分木内で、消去済の頂点数の分布

size = [0] * (N + 1)  # 部分木の大きさ

answer = [N * (N + 1) // 2] * (N + 1)



for v in order[::-1]:

    size[v] += 1

    p = parent[v]

    dp[v][C[v]] = size[v]

    if not p:

        break

    size[p] += size[v]

    c = C[p]

    x = size[v] - dp[v][c]

    answer[c] -= x * (x + 1) // 2

    dp[p] = merge(dp[p], dp[v])



A = dp[root]

for c in range(1, N + 1):

    x = N - A[c]

    answer[c] -= x * (x + 1) // 2



print(*answer[1:], sep='\n')

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

        p = parent[v]

        x = (ind_R[v] - ind_L[v]) // 2 + 1  # subtree size

        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

print(('\n'.join(map(str, answer[1:]))))

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)  # 根を深さ 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(A, B):
    if len(A) < len(B):
        A, B = B, A
    for key, cnt in B.items():
        A[key] += cnt
    return A


dp = [defaultdict(int) for _ in range(N + 1)]  # 部分木内で、消去済の頂点数の分布
size = [0] * (N + 1)  # 部分木の大きさ
answer = [N * (N + 1) // 2] * (N + 1)
for v in order[::-1]:
    size[v] += 1
    p = parent[v]
    dp[v][C[v]] = size[v]
    if not p:
        break
    size[p] += size[v]
    c = C[p]
    x = size[v] - dp[v][c]
    answer[c] -= x * (x + 1) // 2
    dp[p] = merge(dp[p], dp[v])
A = dp[root]
for c in range(1, N + 1):
    x = N - A[c]
    answer[c] -= x * (x + 1) // 2
print(*answer[1:], sep="\n")

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 = list(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
        p = parent[v]
        x = (ind_R[v] - ind_L[v]) // 2 + 1  # subtree size
        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
print(("\n".join(map(str, answer[1:]))))

-from collections import defaultdict + + +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 + +graph = [[] for _ in range(N + 1)] -m = map(int, read().split()) -AB = zip(m, m) -graph = [[] for _ in range(N + 1)] -for a, b in AB: +m = list(map(int, read().split())) +for a, b in zip(m, m): -root = 1 -parent = [0] * (N + 1) -depth = [0] * (N + 1)  # 根を深さ 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(A, B): -    if len(A) < len(B): -        A, B = B, A -    for key, cnt in B.items(): -        A[key] += cnt -    return A - - -dp = [defaultdict(int) for _ in range(N + 1)]  # 部分木内で、消去済の頂点数の分布 -size = [0] * (N + 1)  # 部分木の大きさ +tour, ind_L, ind_R, parent = EulerTour(graph) +removed = [0] * (N + 1) -for v in order[::-1]: -    size[v] += 1 -    p = parent[v] -    dp[v][C[v]] = size[v] -    if not p: -        break -    size[p] += size[v] -    c = C[p] -    x = size[v] - dp[v][c] -    answer[c] -= x * (x + 1) // 2 -    dp[p] = merge(dp[p], dp[v]) -A = dp[root] -for c in range(1, N + 1): -    x = N - A[c] -    answer[c] -= x * (x + 1) // 2 -print(*answer[1:], sep="\n") +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  # subtree size +        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 +print(("\n".join(map(str, answer[1:]))))