Problem:
 Score : 600 points    Problem Statement  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 1 3
1 2 1
1 2
2 3      Sample Output 1 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.       Sample Input 2 1
1      Sample Output 2 1       Sample Input 3 2
1 2
1 2      Sample Output 3 2
2       Sample Input 4 5
1 2 3 4 5
1 2
2 3
3 4
3 5      Sample Output 4 5
8
10
5
5       Sample Input 5 8
2 7 2 5 4 1 7 5
3 1
1 2
2 7
4 5
5 6
6 8
7 8      Sample Output 5 18
15
0
14
23
0
23
0

Solution (Python):
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)))

Solution (Python):


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)


if __name__ == '__main__':
  main()

Solution (Python):
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)

Solution (Python):
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]:
        
        
        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)

Solution (Python):
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 = map(lambda x: int(x) - 1, 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()

Solution (Python):

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])

Solution (Python):

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)

Solution (Python):

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):
    ans[i] = total - ans[i]
print(*ans[1:], sep="\n")

Solution (Python):

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])

Solution (Python):

import sys

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])

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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):
	global 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")

Solution (Python):
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):
	global 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")

Solution (Python):
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])

Solution (Python):
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()

Solution (Python):
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')


if __name__ == "__main__":
    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)

Solution (Python):
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")

Solution (Python):
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")

Solution (Python):
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')

Solution (Python):
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")