Buggy python submission (verdict: Time Limit Exceeded):
#!/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] = 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:
    ret[curr] = defaultdict(int)
    for dest in g.E[curr]:
        if dest == parent[curr]:
            continue
        child = ret[dest]

        n = size[dest]-child[c[curr]]
        ans[c[curr]] += n*(n+1)//2

        # マージ
        ret[curr] = merge(ret[curr], child)

    ret[curr][c[curr]] = size[curr]


for color in range(N):
    if color != c[0]:
        n = N-ret[0][color]
        ans[color] += n*(n+1)//2

tot = N*(N+1)//2
for a in ans:
    print(tot-a)


Fixed submission:
#!/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] = 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)

Buggy python submission (verdict: Time Limit Exceeded):
#!/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] = 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のノードで分割して、部分グラフ内での単純パスの総数を求めれば良い
# 各ノードに状態として辞書をもたせる。
# 辞書は色iを通らずに到達可能な頂点の数を持つ。

# 回答用
ans = [0]*N


def f(curr, par=-1):
    # 再帰関数
    # curr: 現在の節点
    # par : 親節点の番号
    ret = defaultdict(int)
    for dest, w in g.E[curr]:
        if dest == par:
            continue
        child = f(dest, curr)

        # 自身の色と同じ場合、子の頂点の数から加算
        n = 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]] = 0

    for color in range(N):
        if color != c[curr]:
            ret[color] += 1
    return ret


ret = f(0)
for color in range(N):
    if color != c[0]:
        n = ret[color]
        ans[color] += n*(n+1)//2

tot = N*(N+1)//2
for a in ans:
    print(tot-a)


Fixed submission:
#!/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] = 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)

Buggy python submission (verdict: Time Limit Exceeded):
#!/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] = 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のノードで分割して、部分グラフ内での単純パスの総数を求めれば良い
# 各ノードに状態として辞書をもたせる。
# 辞書は色iを通らずに到達可能な頂点の数を持つ。

# 回答用
ans = [0]*N


def f(curr, par=-1):
    # 再帰関数
    # curr: 現在の節点
    # par : 親節点の番号
    ret = defaultdict(int)
    for dest, w in g.E[curr]:
        if dest == par:
            continue
        child = f(dest, curr)

        # 自身の色と同じ場合、子の頂点の数から加算
        n = 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]] = 0

    for color in range(N):
        if color != c[curr]:
            ret[color] += 1
    return ret


ret = f(0)
for color in range(N):
    if color != c[0]:
        n = ret[color]
        ans[color] += n*(n+1)//2

tot = N*(N+1)//2
for a in ans:
    print(tot-a)


Fixed submission:
#!/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] = 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)

Buggy python submission (verdict: Time Limit Exceeded):
#!/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] = 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のノードで分割して、部分グラフ内での単純パスの総数を求めれば良い
# 各ノードに状態として辞書をもたせる。
# 辞書は色iを通らずに到達可能な頂点の数を持つ。

# 辞書
reachable = [defaultdict(int) for _ in range(N)]

# 回答用
ans = [0]*N


def f(curr, par=-1):
    # 再帰関数
    # curr: 現在の節点
    # par : 親節点の番号
    for dest, w in g.E[curr]:
        if dest == par:
            continue
        f(dest, curr)

        for color in range(N):
            n = reachable[dest][color]
            if color == c[curr]:
                # 自身の色と同じ場合、子の頂点の数から加算
                ans[color] += n*(n+1)//2
                reachable[curr][color] = 0
            else:
                # 自身の色以外については、子の情報から自分の情報を作る
                reachable[curr][color] += n
    for color in range(N):
        if color != c[curr]:
            reachable[curr][color] += 1
    return


f(0)
for color in range(N):
    if color != c[0]:
        n = reachable[0][color]
        ans[color] += n*(n+1)//2

tot = N*(N+1)//2
for a in ans:
    print(tot-a)


Fixed submission:
#!/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] = 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)

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
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)

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

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

# 辞書
reachable = [defaultdict(int) for _ in range(N)]

# 回答用
ans = [0]*N


def f(curr, par=-1):
    # 再帰関数
    # curr: 現在の節点
    # par : 親節点の番号
    for dest, w in g.E[curr]:
        if dest == par:
            continue
        f(dest, curr)

        for color in range(N):
            n = reachable[dest][color]
            if color == c[curr]:
                # 自身の色と同じ場合、子の頂点の数から加算
                ans[color] += n*(n+1)//2
                reachable[curr][color] = 0
            else:
                # 自身の色以外については、子の情報から自分の情報を作る
                reachable[curr][color] += n
    for color in range(N):
        if color != c[curr]:
            reachable[curr][color] += 1
    return


f(0)
for color in range(N):
    if color != c[0]:
        n = reachable[0][color]
        ans[color] += n*(n+1)//2

tot = N*(N+1)//2
for a in ans:
    print(tot-a)


Fixed submission:
#!/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] = 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)