Harryxun/stf_run huggingface dataset:
#coding: utf-8

import sys

def keitai(n1,n2):
    li1 = ['.', ',', '!', '?',' '] 
    li2 = ['a','b','c']
    li3 = ['d','e','f']
    li4 = ['g','h','i']
    li5 = ['j','k','l']
    li6 = ['m','n','o']
    li7 = ['p','q','r','s']
    li8 = ['t','u','v']
    li9 = ['w','x','y','z']
    li = [li1,li2,li3,li4,li5,li6,li7,li8,li9]
    lis = li[n1 - 1]
    n2 = n2 % len(lis)
    a = lis[n2 - 1]
    return a

for line in sys.stdin:
    a = str(line)
    num = 0
    string = ''
    for i in range(len(a)):
        if int(a[i]) == 0:
            string = string + keitai(b,num)
            num = 0
        else:
            num = num + 1
            b = int(a[i])
    print string

### FIXED CODE ###

#coding: utf-8
 
n = int(raw_input())
 
def keitai(n1,n2):
    li1 = ['.', ',', '!', '?',' '] 
    li2 = ['a','b','c']
    li3 = ['d','e','f']
    li4 = ['g','h','i']
    li5 = ['j','k','l']
    li6 = ['m','n','o']
    li7 = ['p','q','r','s']
    li8 = ['t','u','v']
    li9 = ['w','x','y','z']
    li = [li1,li2,li3,li4,li5,li6,li7,li8,li9]
    lis = li[n1 - 1]
    n2 = n2 % len(lis)
    a = lis[n2 - 1]
    return a
 
for k in range(n):
    a = str(raw_input())
    num = 0
    string = ''
    for i in range(len(a)):
        if int(a[i]) == 0:
            if num != 0:
                string = string + keitai(b,num)
                num = 0
            else:
                pass
        else:
            num = num + 1
            b = int(a[i])
    print string
while 1:
    try:
        ipt = raw_input().split()
    except EOFError:
        break;
    s = []
    for i in range(len(ipt)):
        if ipt[i].isdigit():
            s.append(float(ipt[i]))
        else:
            b = s.pop(); a = s.pop();
            if ipt[i]=='+':
                s.append(a+b)
            elif ipt[i]=='-':
                s.append(a-b)
            elif ipt[i]=='*':
                s.append(a*b)
            else:
                s.append(a/b)
    print "%.6f"%s[0]

### FIXED CODE ###

import sys
for s in sys.stdin.readlines():
    st = []
    for c in s.strip().split():
        if c=='+':
            st.append(st.pop()+st.pop())
        elif c=='-':
            st.append(-st.pop()+st.pop())
        elif c=='*':
            st.append(st.pop()*st.pop())
        elif c=='/':
            st.append(1/st.pop()*st.pop())
        else:
            st.append(float(c))
    print st.pop()
import math

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

a,b = map(int,input().split())
print(permutations_count(a,b))

### FIXED CODE ###

n, k = map(int, input().split())
print(k * (k-1)**(n-1))
n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m+1):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

csbit = []
for i in cs:
    csum = 0
    for j in i:
        csum += 2**(j-1)
    csbit.append(csum)

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(m):
    for j in range(1 << n):
        dp[j | csbit[i]] = min(dp[j | csbit[i]], dp[j] + ab[i][0])

if dp[-1] == float("inf"):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(m):
    csbit = 0
    for j in cs[i]:
        csbit += 2**(j-1)
    for j in range(1 << n):
        dp[j | csbit] = min(dp[j | csbit], dp[j] + ab[i][0])

if dp[-1] == float("inf"):
    print(-1)
else:
    print(dp[-1])
#!/usr/bin/env python3

n_nodes, q_query = map(int, input().split())

edges = [[] for _ in range(n_nodes)]
for _ in range(n_nodes - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

queries = []
for _ in range(q_query):
    p, x = map(int, input().split())
    queries.append([p - 1, x])

# print(n_nodes, q_query)
# print(edges, queries)

res = [0 for _ in range(n_nodes)]
for node, point in queries:
    res[node] += point


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            res[v_next] += res[v]
            dfs(v_next, v)


dfs(0, None)

print(*res)


### FIXED CODE ###

#!/usr/bin/env python3

import sys

input = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 6)

N, Q = map(int, input().split())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])

counter = [0 for _ in range(N)]
for p, x in query:
    counter[p - 1] += x


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            counter[v_next] += counter[v]
            dfs(v_next, v)


root = 0
dfs(root, None)

print(*counter)
m,n=int(input().slide())
print((m-1)*n)

### FIXED CODE ###

m,n=map(int,input().split())
print((m-1)*(n-1))
h = input()
w = input()
n = input()
if h < w:
    h = w
print(int(n / h))

### FIXED CODE ###

import math
h = int(input())
w = int(input())
n = int(input())
if h < w:
    h = w
print(math.ceil(n / h))
a=1
while 1:
	l = map(int,raw_input().split())
	if l == [0,0]:
		break
	else :
		print ' '.join(map(str,sorted(l)))
		a += 1

### FIXED CODE ###

a=1
while 1:
	i = int(raw_input())
	if i == 0 :
		break
	else :
		print 'Case %d: %d'%(a, i)
        a += 1
import math
n=int(input())
A=B=1
for i in range(n):
    x,y=[int(i) for i in input().split()]
    n=max(-(-A//x),-(-B//y))
    A=n*x
    B=n*y
print(A+B)

### FIXED CODE ###

iro=[int(i) for i in input().split()]
x=set(iro)
print(len(x))
import re
s1 = input()
t = input()
pre = ""
count = 0
ans = ""
start = 0
end = 0
it = ""

for w in s1:
  if w == t[count]:
    count += 1
    it += w
  elif pre == "?" and w == t[0]:
    count = 1
    it = w
  elif w != "?" and pre == "?":
    pre = w
    count = 0
    it = ""
  elif w == "?" and pre == "?":
    count += 1
    it += w
  else:
    if w == "?":
      pre = w
      count += 1
      it += w
  # if count >= len(t):
  #   print("きたよ")
  #   print(w)
  #   end = s1.index(w)
  #   start = end - len(t)
#print(f"count is {count}")
#print("endは" + end)
#replace = "?" * len(t)
#print("replace is" + it)
if count >= len(t):
  it = it.replace("?","\?")
  # 合致した最も後方のものを置換
  ans = re.sub(it,t,s1)
  ans = ans.replace("?","a")
  #print(ans)
  # if end < len(s1) - 1:
  #   ans = s1[:start] + t + s1[end+1:]
  #   # 全てaに置換
  #   ans = ans.replace("?","a")
  #   print(ans)
  # else:
  #   ans = s1[:start] + t
  #   ans = ans.replace("?","a")
  print(ans)
else:
  print("UNRESTORABLE")

### FIXED CODE ###

# pythonはindexでstringの文字を変更できない
s = list(input())
t = list(input())
x = 0
ans = []
gotk = False

# pythonて関数にするとスコープの外の変数参照できないんだっけ？

# 0 <= k <= s - t
def match(k):
  for i in range(len(t)):
    if s[i + k] != t[i] and s[i + k] != "?":
      return False
  return True

def construct(k,s):
  for i in range(len(t)):
    s[i + k] = t[i]
  for i in range(len(s)):
    if s[i] == "?":
      s[i] = "a"
  return s

# 大きいkから探せば良い(今回逆順にしてるためrangeの第二引数が直前まで処理されることに注意！)
for i in range(len(s) - len(t),-1,-1):
  if match(i):
    x = i
    gotk = True
    break

if gotk == True:
  ans = construct(x,s)
  print("".join(ans))
else:
  print("UNRESTORABLE")
a,b,c=map(int,input().split())
print(a+b+c)

### FIXED CODE ###

l=[int(i) for i in input()]
print(sum(l))
from collections import deque
def resolve():
    N = int(input())
    As = list(map(int, input().split(" ")))
    pos = []
    neg = []
    for a in As:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)
    pos = deque(sorted(pos))
    neg = deque(sorted(neg))
    x = 0
    y = 0
    ops = []
    while True:
        if len(pos) > 0 and len(neg) > 0:
            if len(pos) > len(neg):
                x = neg.popleft()
                y = pos.pop()
            else:
                x = pos.pop()
                y = neg.popleft()
        elif len(pos) > 1 and len(neg) == 0:
                x = pos.popleft()
                y = pos.pop()
        elif len(neg) > 1 and len(pos) == 0:
                x = pos.pop()
                y = pos.popleft()
        else:
            raise Exception("Unreachable?")
        
        ops.append("{} {}".format(x, y))
        xmy = x - y

        if len(pos) == 0 and len(neg) == 0:
            print(xmy)
            break

        if xmy >= 0:
            pos.append(xmy)
        else:
            neg.appendleft(xmy)
        
    [print(i) for i in ops]

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

from collections import deque
def resolve():
    N = int(input())
    As = list(map(int, input().split(" ")))
    pos = []
    neg = []
    for a in As:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)
    pos = deque(sorted(pos))
    neg = deque(sorted(neg))
    x = 0
    y = 0
    ops = []
    while True:
        if len(pos) > 0 and len(neg) > 0:
            if len(pos) > len(neg):
                x = neg.popleft()
                y = pos.pop()
            else:
                x = pos.pop()
                y = neg.popleft()
        elif len(pos) > 1 and len(neg) == 0:
                x = pos.popleft()
                y = pos.pop()
        elif len(neg) > 1 and len(pos) == 0:
                x = neg.pop()
                y = neg.popleft()
        else:
            raise Exception("Unreachable?")
        
        ops.append("{} {}".format(x, y))
        xmy = x - y

        if len(pos) == 0 and len(neg) == 0:
            print(xmy)
            break

        if xmy >= 0:
            pos.append(xmy)
        else:
            neg.appendleft(xmy)
        
    [print(i) for i in ops]

if '__main__' == __name__:
    resolve()
n,m=map(int,input().split())
a=[int(b) for b in input()]
def func(n,a):
    if n< sum(a):return "-1"
    else: 
        return n-sum(a)
print(func(n,a))

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(b) for b in input().split()]
def func(n,a):
    if n< sum(a):return "-1"
    else: 
        return n-sum(a)
print(func(n,a))
def divide(x, y):
    s = 1
    if(x < 0):s *= -1
    if(y < 0):s *= -1
    return abs(x) / abs(y) * s     
 
def _split(_src):
    c = 0
    l = len(_src)
    if l == 0:
        return []
    while c < l and ord('0') <= ord(_src[c]) <= ord('9'):
        c += 1
    if c == 0:
        tmp = _split(_src[1:])
        if tmp != [] and tmp[0] == "-":
            tmp = ["(", 0 , "-", 1, ")", "*"] + tmp[1:]
        return [_src[0]] + tmp
    else:
        return [int(_src[:c])] + _split(_src[c:])
         
 
def evaluate(src):
    if len(src) == 1:
        return src[0]
         
    if "(" in src:
        l = src.index("(")
        r = l
        st = 1
        while st:
            r += 1
            if src[r] == "(": st += 1
            if src[r] == ")": st -= 1
        
        
        mid = evaluate(src[l + 1:r])
        return evaluate( src[:l] + [mid] + src[r + 1:])
     
    operators = [("+", lambda x,y:x + y),
                 ("-", lambda x,y:x - y),
                 ("*", lambda x,y:x * y),
                 ("/", divide)
                ]  
     
    for (op,func) in operators:
        if op in src:
            p = src.index(op)
            l = evaluate(src[:p])
            r = evaluate(src[p + 1:])
            return func(l, r)
     
for t in xrange(input()):
    _src = "0+" + raw_input().strip("=")
    src = _split(_src)
    print evaluate(src)

### FIXED CODE ###

def divide(x, y):
    s = 1
    if(x < 0):s *= -1
    if(y < 0):s *= -1
    return abs(x) / abs(y) * s     

operator = {"+":(lambda x,y: x+y),
            "-":(lambda x,y: x-y),
            "*":(lambda x,y: x*y),
            "/":divide
            }

def ind(src, x):
    if x not in src:return 1<<30
    return src.index(x)
 
def _split(_src):
    c = 0
    l = len(_src)
    if l == 0:
        return []
    while c < l and ord('0') <= ord(_src[c]) <= ord('9'):
        c += 1

    if c == 0:
        return [_src[0]] + _split(_src[1:])
    else:
        return [int(_src[:c])] + _split(_src[c:])
         
 
def evaluate(src):
    if len(src) == 1:
        return src[0]
         
    if "(" in src:
        l = src.index("(")
        r = l
        st = 1
        while st:
            r += 1
            if src[r] == "(": st += 1
            if src[r] == ")": st -= 1
        
        mid = evaluate(src[l + 1:r])
        return evaluate( src[:l] + [mid] + src[r + 1:])
    
    pos = min(ind(src, "*"), ind(src,"/"))
    if(pos == 1<<30):
        pos = min(ind(src, "+"), ind(src, "-"))
    op = src[pos]
    l, r = src[pos - 1], src[pos + 1]
    mid = operator[op](l, r)
    return evaluate(src[:pos - 1] + [mid] + src[pos + 2:])

     
for t in xrange(input()):
    _src = raw_input().strip("=")
    src = _split(_src)
    print evaluate(src)
def abc070_d():
    import sys
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    n = next(inp)
    adjmtx = np.zeros((n, n), dtype=np.int64)
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjmtx[a, b] = c
        adjmtx[b, a] = c

    q = next(inp)
    k = next(inp) - 1

    graph = csr_matrix(adjmtx)
    dist = dijkstra(csgraph=graph, indices=k)

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = int(dist[x] + dist[y])
        print(ans)

if __name__ == '__main__':
    abc070_d()

### FIXED CODE ###

def abc070_d():
    import sys
    sys.setrecursionlimit(10010010)
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    n = next(inp)
    adjlist = [[] for _ in range(n)]
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjlist[a].append((b, c))
        adjlist[b].append((a, c))

    q = next(inp)
    k = next(inp) - 1

    dist = [-1] * n

    def dfs(x:int, d:int):
        dist[x] = d
        for nx, nd in adjlist[x]:
            if dist[nx] != -1: continue
            dfs(nx, d + nd)

    dfs(k, 0)

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = dist[x] + dist[y]
        print(ans)

if __name__ == '__main__':
    abc070_d()
import itertools

def is_lit(i, bit):
    l = [bit[j-1] for j in sockets[i]]
    return p[i] == l.count(True) % 2

count = 0
N, M = map(int, input().split())
bit_list = list(itertools.product([True, False], repeat = N))

sockets = []
for i in range(M):
    args = input().split(' ')
    k = int(args[0])
    sockets.append([int(args[i+1]) for i in range(k)])

p = [int(x) for x in input().split(' ')]

for bit in bit_list:
    o = [is_lit(i, bit) for i in range(M)]
    if o.count(True) == len(o):
        count += 1

print(count)


### FIXED CODE ###

A ,P = map(int,input().split())
print(int((3*A + P) /2))
A=int(input())
B=int(input())
C=int(input())
X=int(input())

count = 0

for ac in range(A)
    for bc in range(A)
        for cc in range(A)
            if 500*ac+100*bc+50*cc == X:
                count += 1

print(count)

### FIXED CODE ###

A=int(input())
B=int(input())
C=int(input())
X=int(input())

count = 0

for ac in range(A+1):
    for bc in range(B+1):
        for cc in range(C+1):
            if 500*ac+100*bc+50*cc == X:
                count += 1

print(count)
x=int(inptu())

if x<1200:
  print('ABC')
else:
  print('ARC')

### FIXED CODE ###

x=int(input())
 
if x<1200:
  print('ABC')
else:
  print('ARC')
a,b,c = map(int,input().split())

m = [a + b,a + c,b + c]

print(m(min))


### FIXED CODE ###

a,b,c = map(int,input().split())

m = min(a + b,a + c,b + c)

print(m)
import sys
import numpy as np

n, m = input().strip().split(" ")
n = int(n) ;m = int(m)

c = n

a = []
for line in sys.stdin :
    a.append(line)
    c -= 1
    if c == 0 :
        break

c = m

b = []
for line in sys.stdin :
    b.append(line)
    c -= 1
    if c == 0 :
        break

for i in range(0, len(a)) :
    a[i] = a[i].strip().split(" ")
    for j in range(0, len(a[i])) :
        a[i][j] = int(a[i][j])

for i in range(0, len(b)) :
    b[i] = int(b[i].strip())

a = np.array(a)
b = np.array(b)

for i in np.dot(a, b) :
    print(i)



### FIXED CODE ###


import sys

n, m = input().strip().split(" ")
n = int(n) ;m = int(m)

c = n

a = []
for line in sys.stdin :
    a.append(line)
    c -= 1
    if c == 0 :
        break

c = m

b = []
for line in sys.stdin :
    b.append(line)
    c -= 1
    if c == 0 :
        break

for i in range(0, len(a)) :
    a[i] = a[i].strip().split(" ")
    for j in range(0, len(a[i])) :
        a[i][j] = int(a[i][j])

for i in range(0, len(b)) :
    b[i] = int(b[i].strip())

for i in range(0, n) :
    sum = 0
    for j in range(0, m) :
        sum += a[i][j]*b[j]
    print(sum)
import sys
import math as mas

def sieve(n):
	p=[True for i in range(n+1)]
	p[0]=p[1]=False
	end=int(n**0.5)
	for i in range(2,end+1):
		if p[i]:
			for j in range(i*i,n+1,i):
				p[j]=False
	return p
	
sosu=sieve(1000010)
for i in sys.stdin:
	print(sum(sosu[t] for t in range(int(i)))

#	a,b=map(int,i.split())
#	print(gcd(a,b),lcm(a,b))

### FIXED CODE ###

import sys
import math as mas

def sieve(n):
	p=[True for i in range(n+1)]
	p[0]=p[1]=False
	end=int(n**0.5)
	for i in range(2,end+1):
		if p[i]:
			for j in range(i*i,n+1,i):
				p[j]=False
	return p
	
sosu=sieve(1000010)
for i in sys.stdin:
	t=int(i)
	if t<2:print(0)
	elif t==2:print(1)
	else:print(1+sum(sosu[t] for t in range(3,int(i)+1,2)))

#	a,b=map(int,i.split())
#	print(gcd(a,b),lcm(a,b))
list = int(input().split())
num = []
ans = 753
for i in range(len(list)-2):
  num.append((list[i] * 100) + (list[i+1] * 10) + list[i+2])
  if(num[i] >= 753):
    if(ans >= (num[i] - 753)):
      ans = num[i] - 753
  else:
    if(ans > (753 - ans[i])):
      ans = 753 - ans[i]
print(ans)

### FIXED CODE ###

s = input()
list = [int(c) for c in s]
num = []
ans = 753
for i in range(len(list)-2):
	num.append((list[i] * 100) + (list[i+1] * 10) + list[i+2])
	if(num[i] >= 753):
		if(ans >= (num[i] - 753)):
			ans = num[i] - 753
	else:
		if(ans > (753 - num[i])):
			ans = 753 - num[i]
print(ans)
import math

N,K,*A = map(int,open(0).read().split())
g = A[0]
for i in A:
   g = math.gcd(g,i)
print("POSSIBLE" if K % g == 0 and K <= max(A) else "IMPOSSIBLE")  

### FIXED CODE ###

import fractions
from functools import reduce
N,K,*A = map(int,open(0).read().split())
g = reduce(fractions.gcd,A)
print("POSSIBLE" if K % g == 0 and K <= max(A) else "IMPOSSIBLE")
(n, k) = [int(x) for x in input().split()]

s = set()

for i in range(k):
	input()
    s |= set(input().split)
    
print(n-len(s))

### FIXED CODE ###

(n, k) = [int(x) for x in input().split()]

s = set()

for i in range(k):
    input()
    s |= set(input().split())
    
print(n-len(s))
a, b = map(float,input().split())
print(int((a*b)//1))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
    if a[i] == 0:
        print(0)
        exit()
for i in range(n):
    ans *= a[i]
    if ans > 1e18:
        print(-1)
        exit()
if ans > 1e18:
    print(-1)
else:
    print(ans)
from sys import stdin
readline = stdin.readline


R, S, P = 1, 2, 3
W, L, D = 1, 2, 3

rps = {
    (R, S, P):{R:D, S:D, P:D},
    (R, S)   :{R:W, S:L},
    (S, P)   :{S:W, P:L},
    (R, P)   :{P:W, R:L}
}

while True:
    hand = int(readline())
    if hand == 0:
        break
    hands = [hand] + [int(readline()) for _ in range(4)]
    hand_set = tuple(sorted(set(hands)))
    for h in hands:
        print(rps[hand_set][h])

### FIXED CODE ###

from sys import stdin
readline = stdin.readline


R, S, P = 1, 2, 3  # rock, scissors, paper
W, L, D = 1, 2, 3  # win, lose, draw

rps = {
    (R, S, P): {R: D, S: D, P: D},
    (R, S):    {R: W, S: L},
    (S, P):    {S: W, P: L},
    (R, P):    {P: W, R: L},
    (R,):       {R: D},
    (S,):       {S: D},
    (P,):       {P: D}
    }

while True:
    hands = []
    hands.append(int(readline()))
    if hands[0] == 0:
        break
    for _ in range(4):
        hands.append(int(readline()))

    hands_set = tuple(sorted(set(hands)))
    for h in hands:
        print(rps[hands_set][h])
n, x = [int(i) i in input().split()]

3 <= n <= 100

if n == x == 0:
    break

for a in range(n+1):
    for b in range(a+1):
        for c in range(b+1):
             if a == b == c or a == b or a == c or b == c:
             None
             if a + b + c == x:
             return
             else:
             None
print()

### FIXED CODE ###

while True:
    n, x = [int(i) for i in input().split()]

    if n == x == 0:
        break

    count = 0
    for s in range(1, n+1):
        for m in range(s+1, n):
            for e in range(m+1, n+1):
                if x == sum([s, m, e]):
                    count += 1

    print(count)
N,X=map(int,input().split())
a=[1]
p=[1]
for i in range(N):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)

def f(n,x):
    if x==1:
        return 0
    if x<=a[n-1]+1:
        return f(n-1,x-1)
    return p[n-1]+f(n-1,x-a[n-1]-2)+1
print(f(N,X))

### FIXED CODE ###

N,X=map(int,input().split())
a=[1]
p=[1]
for i in range(N):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)

def f(n,x):
    if n==0:
        return 0 if x<=0 else 1
    if x<=a[n-1]+1:
        return f(n-1,x-1)
    return p[n-1]+f(n-1,x-a[n-1]-2)+1
print(f(N,X))
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)

# 区間データを保管するテーブル
class BIT():
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)  # 今回は1で初期化する。 BIT の先頭は 1からなのでずらす
        
    def add(self, i, s):  # i の情報を更新する
        while i <= self.size:
            self.data[i] += s
            i += i & -i
    
    def sum(self, i):  # 1～i 番目までの合計
        tmp = 0
        while i > 0:
            tmp += self.data[i]
            i -= i & -i
        return tmp

def dfs(u, p = -1):

    global k, I, O
    
    us = 1
    I[u] = k
    k += 1
    
    for v in E[u]:
        if not v == p:
            us += dfs(v, u)
    O[u] = k

    return us

# 経路の組み合わせ数を計算する
def comb2(n):
    return n*(n+1)//2

k = 1
I = [0] * N  # 走査に入ったタイミング
O = [0] * N  # 上に戻ったタイミング
dfs(0)

# 色番号ごとに、頂点をまとめる。まとめらたら、子要素から操作するように並べ替える
VC = [ [] for _ in range(N)]
for j in range(N):
    VC[C[j]].append(j)

for j in range(N):
    VC[j].sort(key=lambda x:I[x], reverse=True)


total = comb2(N)

for j in range(N):
    
    bit = BIT(N)
    for i in range(N):
        bit.add(i+1, 1)
    
    ans = total
    for u in VC[j]:
        cnt = 1
        for v in E[u]:
            if I[u] > I[v]:
                continue
            num = bit.sum(O[v]-1) - bit.sum(I[v]-1)
            ans -= comb2(num)
            cnt += num
        bit.add(I[u], -cnt)
    ans -= comb2(bit.sum(N))
    print(ans)

### FIXED CODE ###

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)