Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Runtime Error

Solution code:
from collections import defaultdict

A = defaultdict(lambda: [])
B = defaultdict(lambda: [])
_px = defaultdict(int)


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

# A = [0 for i in range(N)]
# B = [0 for i in range()]
# A = [{}]
# B = {}

ans = [0 for i in range(N)]
_a = [0 for i in range(N+1)]
PX = []

for i in range(N-1):
    a, b = map(int, input().split())
    A[a].append(b)
    B[b].append(a)
    _a[a] = 1

for q in range(Q):
    p, x = map(int, input().split())
    PX.append([p, x])
    _px[p] += x

# print(_px)
# print(A)
# print(B)
# print(PX)
counter = 0
# _px = dict(_px)
def find(x, plus):
    global counter
    for j in x:
        counter += 1
        ans[j-1] += plus
        if _a[j]:
            find(A[j], plus)

for i in range(1, N):
    counter += 1
    ans[i-1] += _px[i]
    find(A[i], _px[i])

# for px in _px:
#     counter += 1
#     ans[px[0]-1] += px[1]
#     find(A[px[0]], px[1])

print(*ans)

# print(counter)

Submission status: Runtime Error

Solution code:
import numpy as np

n,q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n+q-1)]

matrix = np.zeros((n,n))
ans = np.zeros((n,n))

for i in range(n-1):
    matrix[ab[i][0]-1,ab[i][1]-1] = 1
#  matrix[ab[i][1]-1,ab[i][0]-1] = 1

for l in range(n):
      for m in range(n):
            if matrix[l][m]:
                for o in range(n):
                    if matrix[m][o]:
                        matrix[l][o] = 1
          
ans = np.zeros((n))

for j in range(n-1,n+q-1):
    ans[ab[j][0]-1] += ab[j][1]
    for k in range(n):
        if matrix[ab[j][0]-1][k] == 1:
            ans[k] += ab[j][1]
            
for p in range(n):
    print(ans[p],end = " ")

Submission status: Runtime Error

Solution code:
from collections import defaultdict

A = defaultdict(lambda: [])
B = defaultdict(lambda: [])
_px = defaultdict(int)


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

# A = [0 for i in range(N)]
# B = [0 for i in range()]
# A = [{}]
# B = {}

ans = [0 for i in range(N)]
_a = [0 for i in range(N+1)]
PX = []

for i in range(N-1):
    a, b = map(int, input().split())
    A[a].append(b)
    B[b].append(a)
    _a[a] = 1

for q in range(Q):
    p, x = map(int, input().split())
    PX.append([p, x])
    _px[p] += x

print(_px)
# print(A)
# print(B)
# print(PX)
counter = 0
# _px = dict(_px)
def find(x, plus):
    global counter
    for j in x:
        counter += 1
        ans[j-1] += plus
        if _a[j]:
            find(A[j], plus)

for i in range(1, N):
    counter += 1
    ans[i-1] += _px[i]
    find(A[i], _px[i])

# for px in _px:
#     counter += 1
#     ans[px[0]-1] += px[1]
#     find(A[px[0]], px[1])

print(*ans)

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
#    try:
#        output_lst[current_node] += adding
#    except:
#        pass
    output_lst[current_node] += adding
    for i in info_lst[current_node]:   #先の枝についても再帰
        adding += pi_xi_sum_lst[i]
        count_add(info_lst, pi_xi_sum_lst, output_lst, i, adding)
        adding -= pi_xi_sum_lst[i]

def glaph_2_tree(info_lst, passed_place, current_node):
    next_nodes_lst = info_lst[current_node][:]
    for next_node in next_nodes_lst:
        if passed_place[next_node]: # 通ったことがあったら、
            info_lst[current_node].remove(next_node)
        else:
            passed_place[next_node] = True
            glaph_2_tree(info_lst, passed_place, next_node)
            passed_place[next_node] = False
    passed_place[next_node] = True

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

info_lst = [[] for _ in range(N+1)]

for _ in range(N-1): # 10**5
    ai, bi = map(int, input().split())
    info_lst[ai].append(bi)
    info_lst[bi].append(ai)

passed_place = [False] * (N+1)
passed_place[1] = True
glaph_2_tree(info_lst, passed_place, 1) # 10**5

pi_xi_sum_lst = [0]*(N+1)
for _ in range(Q): # 10**5
    pi, xi = map(int, input().split())
    pi_xi_sum_lst[pi] += xi

output_lst = [0]*(N+1)
count_add(info_lst, pi_xi_sum_lst, output_lst, current_node=1, adding=pi_xi_sum_lst[1])

output_str = ""
for i in range(1, N+1):
    output_str += str(output_lst[i]) + " "

print(output_str)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

q = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    q[p] += x

seen = [False] * (N + 1)
ans = [0] * (N + 1)


def dfs(e, v, x):
    seen[v] = True
    ans[v] += x
    for next_v in e[v]:
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v, x + q[next_v])


dfs(e, 1, q[1])
print(*ans[1:])

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
side=[[0 for i in range(2)]for j in range(N-1)]
yobun=[[0 for i in range(2)]for j in range(Q)]

l=[0]*N
ll=[0 for i in range(N)] for j in range(N)

for i in range(N-1):
    side[i][0],side[i][1]=map(int,input().split())
    
def kyusyu(p,x):
    l[p-1]+=x
    for i in range(N-1):
        if p==side[i][0]:
            kyusyu(side[i][1],x)
    
for i in range(Q):
    yobun[i][0],yobun[i][1]=map(int,input().split())
    kyusyu(yobun[i][0],yobun[i][1])



            
#for i in range(Q):
#    kyusyu(yobun[i][0],yobun[i][1])
    
    
print(l)

Submission status: Runtime Error

Solution code:
input_line = list(map(int,input().split()))
tree_info = []
for i in range(input_line[0]-1):
  info = list(input().split())
  tree_info.append(info)
counter = [0] * input_line[0]
for i in range(input_line[1]):
  count_info = list(map(int, input().split()))
  for n in range(tree_info):
    if tree_info[0]=count_info[0]:
      a = n
      break
  counter = counter[:n]+ list(map(lambda x: x+count_line[1],
                                  counter[n:]))
print(" ".join(counter))

Submission status: Runtime Error

Solution code:
def ans(p, x, dict, dict_count):
    for i in dict.keys():
        if p == i:
            for t in dict[p]:
                if t==p:
                    Dict_count[t]+=x
                else:
                    ans(t, x, Dict, Dict_count)
    if not p in dict.keys():
        Dict_count[p]+=x 

x = list(map(int, input().split()))
N = x[0]
Q = x[1]
Dict = {}
Dict_count = {}
for i in range(N-1):
    s = list(map(int, input().split()))
    if not s[0] in Dict_count.keys():
        Dict_count.setdefault(s[0], 0)
    if not s[1] in Dict_count.keys():
        Dict_count.setdefault(s[1],0)
    if not s[0] in Dict.keys():
        Dict.setdefault(s[0], []).append(s[0])
    Dict[s[0]].append(s[1])

for i in range(Q):
    s = list(map(int, input().split()))
    ans(s[0], s[1], Dict, Dict_count)

l = len(Dict_count)
for i in range(1,l+1):
    print(Dict_count[i], end=' ')
print()

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    try:
        output_lst[current_node] += adding
    except:
        pass
    for i in info_lst[current_node]:   #先の枝についても再帰
        adding += pi_xi_sum_lst[i]
        count_add(info_lst, pi_xi_sum_lst, output_lst, i, adding)
        adding -= pi_xi_sum_lst[i]

def glaph_2_tree(info_lst, passed_place, current_node):
    next_nodes_lst = info_lst[current_node][:]
    for next_node in next_nodes_lst:
        if passed_place[next_node]: # 通ったことがあったら、
            info_lst[current_node].remove(next_node)
        else:
            passed_place[next_node] = True
            glaph_2_tree(info_lst, passed_place, next_node)
            passed_place[next_node] = False
    passed_place[next_node] = True

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

info_lst = [[] for _ in range(N+1)]

for _ in range(N-1): # 10**5
    ai, bi = map(int, input().split())
    info_lst[ai].append(bi)
    info_lst[bi].append(ai)

passed_place = [False] * (N+1)
passed_place[1] = True
glaph_2_tree(info_lst, passed_place, 1) # 10**5

pi_xi_sum_lst = [0]*(N+1)
for _ in range(Q): # 10**5
    pi, xi = map(int, input().split())
    pi_xi_sum_lst[pi] += xi

output_lst = [0]*(N+1)
count_add(info_lst, pi_xi_sum_lst, output_lst, current_node=1, adding=pi_xi_sum_lst[1])

output_str = ""
for i in range(1, N+1):
    output_str += str(output_lst[i]) + " "

print(output_str)

Submission status: Runtime Error

Solution code:
n, q = map(int,input().split())
cnt = [0] * (n+1)
import sys
sys.setrecursionlimit(10**6)
import numpy as np
tree = np.zeros((n+1, n+1))
part = [0] * (n+1)
for i in range(n-1):
    a, b = map(int,input().split())
    tree[a][b] = 1
def dfs(i):
    ret = [i]
    global part
    if tree[i] == [0] * n:
        part[i] = ret
        return ret
    for j in range(n+1):
        if tree[i][j] == 1:
            ret.extend(dfs(j))
    part[i] = ret
    return ret
dfs(1)
for _ in range(q):
    p,x = map(int,input().split())
    for node in part[p]:
        cnt[node] += x
print(*cnt[1:])

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
from functools import lru_cache

def main():
    n, q = map(int, input().split())
    ab = [[],[]]
    
    for i in range(n-1):
        na,nb = map(int, input().split())
        ab[0].append(na)
        ab[1].append(nb)

    px = [[],[]]
    for i in range(q):
        np,nx = map(int, input().split())        
        px[0].append(np)
        px[1].append(nx)
    
    # print(n,q,ab,px)
    count = [0 for i in range(n)]

    lgth = max(ab[0])
    node =[[] for i in range(lgth)]
    for i in range(n-1):
        index = ab[0][i]-1
        put = ab[1][i]
        node[index].append(put)

    # print(node)

    def calc(idx,val):
        count[idx] += val

        if idx <= lgth-1:
            for j in node[idx]:
                calc(j-1,val)
        
    for i in range(len(px[0])):    
        calc(px[0][i]-1, px[1][i])
    
    print(' '.join(map(str,count)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
Ki_Oya=dict()
Ki_Dict=dict()
Ki_Count=dict()
for i in range(N-1):
  A,B = input().split()
  if A not in Ki_Dict:
    Ki_Dict[A]=set(A)
    Ki_Count[A]=0
    Ki_Oya[A]=set(A)
  if B not in Ki_Dict:
    Ki_Dict[B]=set(B)
    Ki_Count[B]=0
    Ki_Oya[B]=set(B)|Ki_Oya[A]
  Ki_Dict[A]|set(B)
  if A in Ki_Oya:
    for j in list(Ki_Oya[A]):
      Ki_Dict[j]|set(B)

for i in range(Q):
  P,X = input().split()
  X = int(X)
  for i in list(Ki_Dict[P]):
    Ki_Count[i] += X
Ki_List = list(Ki_Dict.keys())
ans=[]
for i in Ki_List:
  ans.append(str(Ki_Count[i]))
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])
candidate_list = []
tree_dict = [[]] * N
#Make tree dict
for i in range(N-1):
    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])
    candidate_list.append((a,b))
candidate_list.reverse()
for candidate in candidate_list:
    a = candidate[0]
    b = candidate[1]
    tree_dict[a] += tree_dict[b] + [b]
        
out_put_list = [0] * N
for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    out_put_list[p-1] += x
    for idx in tree_dict[p]:
        out_put_list[idx-1] += x
    
print(' '.join(map(str,out_put_list)))

Submission status: Runtime Error

Solution code:
import sys

def add_count(addnum, relations, counters, nodelist):
  new_nodelist = []
  for node in nodelist:
    if node not in relations:
      continue
    else:
      new_nodelist = new_nodelist + relations[node]
      for child in relations[node]:
        counters[child-1] += addnum
  
  if len(new_nodelist) == 0:
    return counters
  else:
    return add_count(addnum, relations, counters, new_nodelist)

N, Q = map(int, sys.stdin.readline().split())
alist = list(list(map(int, sys.stdin.readline().split())) for i in range(N-1))
qlist = list(list(map(int, sys.stdin.readline().split())) for i in range(Q))

counters = [0 for i in range(N)]
relations = {}
for a in alist:
  if a[0] not in relations:
    relations[a[0]] = [a[1]]
  else:
    relations[a[0]].append(a[1])
    
for q in qlist:
  if q[0] <= N-1:
    counters[q[0]-1] += q[1]
    counters = add_count(q[1], relations, counters, [q[0]])

print(' '.join(map(str,counters)))

Submission status: Runtime Error

Solution code:
import numpy as np
N,Q = map(int,input().split())
ans = np.array([0]*N)
test = np.array([1]*N)
test = np.diag(test)
p = []
x = []
for i in range(1,N):
    ai,bi = map(int,input().split())
    test[ai-1,bi-1]+=1
for j in range(Q):
    pj,xj = map(int,input().split())
    p.append(pj)
    x.append(xj)

for k in reversed(range(N)):
    check = np.where(test[k] > 0)
    test[k]+=np.sum(test[check],axis=0)
test = np.where(test > 0,1,0)
for j in range(Q):
    ans += test[p[j]-1]*x[j]
ans = ans.tolist()
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
N, Q = list(map(int, input().split()))
tree = {}
for i in range(N-1):
    a, b = list(map(int, input().split()))
    items = tree.get(a, [])
    items.append(b)
    tree[a] = items

q = []
for i in range(Q):
    q.append(list(map(int, input().split())))

ans = [0] * (N + 1)

def recc_sum(p, x, tree_p):
    for i in range(len(tree_p)):
        index = tree_p[i]
        ans[index] += x
        if tree.get(index, None) != None:
            recc_sum(index, x, tree[index])

for i in range(Q):
    p = q[i][0]
    x = q[i][1]
    ans[p] += x
    if tree.get(p, None) != None:
        recc_sum(p, x, tree[p])

print(" ".join(list(map(str, ans[1:]))))

Submission status: Runtime Error

Solution code:
def add_value(*l, p, x):
    if p != -1 and p not in l:
        result[p-1] += x
        l.append(p)
    for i in t:
        add_value(l, i, x)        

n, q = map(int, input().split(" "))
result = [ 0 for i in range(n)]
t = [[] for i in range(n)]

for i in range(n-1):
    a, b = map(int, input().split(" "))
    t[a-1].append(b)
    t[b-1].append(a)

for i in range(q):
    p, x = map(int, input().split(" "))
    temp = []
    add_value(temp, p=p, x=x)

for i in range(n):
    if i == n-1:
        print(str(result))
    else:
        print(str(result) + " ", end="")

Submission status: Runtime Error

Solution code:
n, q = map(int,input().split())
cnt = [0] * (n+1)
import sys
sys.setrecursionlimit(2000)
import numpy as np
tree = np.zeros((n+1, n+1))
part = [0] * (n+1)
for i in range(n-1):
    a, b = map(int,input().split())
    tree[a][b] = 1
def dfs(i):
    ret = [i]
    global part
    if tree[i] == [0] * n:
        part[i] = ret
        return ret
    for j in range(n+1):
        if tree[i][j] == 1:
            ret.extend(dfs(j))
    part[i] = ret
    return ret
dfs(1)
for _ in range(q):
    p,x = map(int,input().split())
    for node in part[p]:
        cnt[node] += x
print(*cnt[1:])

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
class Tree:
   def __init__(self, n):
        self.n = n
        self.tree = dd(list)
        self.value = dd(int)
    
   def addNode(self, u, v):
        if u>v:
            u, v = v, u
        self.tree[u].append(v)
    
   def update(self, u, n):
       self.value[u] += n
   
   def query(self,root):
       for node in self.tree[root]:
           self.value[node] += self.value[root]
           self.query(node)
   
   def ans(self):
       self.query(1)
       for i in xrange(1,self.n+1):
           print self.value[i],
       print ""

f = lambda : map(int, raw_input().split())
n, q = f()
tree = Tree(n)
for i in xrange(n - 1):
    tree.addNode(*f())

for i in xrange(q):
    tree.update(*f())

tree.ans()

Submission status: Runtime Error

Solution code:
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
 
val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,input().split())
    val[a-1] += b 
visited = [True for i in range(N)]
def dps(i):
    visited[i] = False
    if i == N :
        return 1
    else :
        for j in graph[i]:
            if visited[j]:
                val[j] += val[i]
                dps(j)
dps(0)
for i in val:
  print(i,end = " ")

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
#ABC138D
import sys
sys.setrecursionlimit(100000)

tmp = input().split()
n,q = list(map(lambda a: int(a), tmp))

apex=[]
node=[]

#for i in range(0,n+1):
#	node.append([])
#	apex.append(0)
node.append([])
node.append([])
node.append([])
apex.append(0)
apex.append(0)
apex.append(0)

for i in range(1,n):
	node.append([])
	apex.append(0)
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	node[hoge[0]].append(hoge[1])

for i in range(1,q+1):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	apex[hoge[0]]+=hoge[1]

#print(node)
#print(apex)

def calc(j):
	for i in node[j]:
		apex[i]+=apex[j]
		calc(i)

calc(1)
#print(apex)

ans=str(apex[1])
for i in range(2,n+1):
	ans += " " + str(apex[i])
print(ans)

Submission status: Runtime Error

Solution code:
def bubunki(akan,st):
    for l in range(st,n-1) :
        if(a[l] == akan) :
            z[b[l]] += x1
            bubunki(b[l],l+1) 
    return 

n,q = map(int,input().split())

a = []
b = []
z = [0] * (n+1)

for i in range(n-1) :
    a1,b1 = map(int,input().split())
    a.append(a1)
    b.append(b1)

c = zip(a,b)
c.sort()
a,b = zip(*c)

for j in range(q) :
    p1,x1 = map(int,input().split())
    z[p1] += x1
    bubunki(p1,0)        


s = ""
for l in range(1,n+1) :
    s +=  str(z[l]) + " "
    
print(s)

Submission status: Runtime Error

Solution code:
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,input().split())
    val[a-1] += b 
visited = [True for i in range(N)]
def dps(i):
    visited[i] = False
    if i == N :
        return 1
    else :
        for j in graph[i]:
            if visited[j]:
                val[j] += val[i]
                dps(j)
dps(0)
for i in val:
  print(val,end = " ")

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())

dic={}
inv_dic={}
for i in range(N-1):
    a,b=map(int,input().split())
    inv_dic[b]=a
for i in range(N):
    dic[i+1]=[i+1]
    
px_list=[]
point_dic={}
for i in range(Q):
    p,x=map(int,input().split())
    px_list.append((p,x))
    point_dic[p]=x
counts=[0]*N
for key,item in inv_dic.items():
    next_key=key
    while True:
        dic[item].append(key)
        counts[item]+=point_dic[key]
        if item in inv_dic.keys():
            item=inv_dic[item]
        else:
            break
            
print(" ".join([str(x) for x in counts]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)


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

p = [0] * n
for _ in range(q):
    i, x = map(int, input().split())
    p[i-1] += x

parent = [0] * n
res = [0] * n
visited = [False] * n
def dfs(x, n):
    res[x] += n
    visited[x] = True
    for ne in adj[x]:
        if not visited[ne]:
            dfs(ne, n + p[ne])

dfs(0, p[0])
print(' '.join([str(x) for x in res]))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def add(p, x):
    c[p] += x
    for i in E[p]:
        c[i] += x
        for j in E[i]:
            add(j, x)


N, Q = map(int, input().split())
E = [[] for i in range(N+1)]
PX = {}

c = [0 for i in range(N+1)]

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

for i in range(1, Q+1):
    p, x = map(int, input().split())
    if p in PX:
        PX[p] += x
    else:
        PX[p] = x


for k in PX.keys():
    add(k, PX[k])

print(' '.join(map(str, c[1:])))

Submission status: Runtime Error

Solution code:
#-*- coding: utf-8
#  -*-
"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_d -d test-d
oj test -d test-d -c "python abc116d.py"
oj test -d test-d -c "python abc116d.py" test-d/sample-3.in
"""
from collections import defaultdict
import sys
import math
from datetime import datetime


class TreeNode:
    def __init__(self):
        self.val = 0
        self.vertex = []
        self.children = [] # means all children!!!
trees = []
def make_trees(n, A, B):
    global trees
    trees = []
    for i in range(n):
        trees.append(TreeNode())
    for i in range(len(A)):
        a = A[i]-1
        b = B[i]-1
        trees[a].vertex.append(b)
    return trees

def set_all_children(node: TreeNode):
    if node:
        set_children(node, node)
        for i in node.vertex:
            set_children(trees[i], trees[i])

def set_children(anncestor: TreeNode, node: TreeNode):
    if node:
        for i in node.vertex:
            t = trees[i]
            anncestor.children.append(i)
            set_children(anncestor, t)


def dfs(node: TreeNode, x: int):
    if node:
        node.val += x
        for i in node.children:
            #dfs(trees[i], x)
            trees[i].val += x


def sol(n, q, A, B, P, X):
    make_trees(n, A, B)
    set_all_children(trees[0])
    for i in range(len(P)):
        p = P[i]-1
        x = X[i]
        t = trees[p]
        # dfs, give point x
        dfs(t, x)
    #
    return " ".join([str(t.val)  for t in trees])
    #return n, q, A, B, P, X



do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    print(parsed_lines)
    n = int(parsed_lines[0][0])
    q = int(parsed_lines[0][1])
    A = []
    B = []
    P = []
    X = []
    for i in range(1, n-1+1):
        a = int(parsed_lines[i][0])
        b = int(parsed_lines[i][1])
        A.append(a)
        B.append(b)
    for i in range(n, 1+n+q-1):
        p = int(parsed_lines[i][0])
        x = int(parsed_lines[i][1])
        P.append(p)
        X.append(x)

    # S = parsed_lines[1][0]
    # return n, k, S
    return n, q, A, B, P, X


if not do_submit:
    n, q, A, B, P, X = input_parse("""
    4 3
    1 2
    2 3
    2 4
    2 10
    1 100
    3 1
    """)
    print(sol(n, q, A, B, P, X))

    n, q, A, B, P, X = input_parse("""
        6 2
        1 2
        1 3
        2 4
        3 6
        2 5
        1 10
        1 10
    """)
    print(sol(n, q, A, B, P, X))

else:
    # n = int(input().strip())
    # q = int(input().strip())
    n, q = list(map(int, input().split()))
    A = []
    B = []
    P = []
    X = []
    for i in range(n-1):
        a, b = list(map(int, input().split()))
        # a = int(input().strip())
        # b = int(input().strip())
        A.append(a)
        B.append(b)
    for i in range(q):
        p, x = list(map(int, input().split()))
        # p = int(input().strip())
        # x = int(input().strip())
        P.append(p)
        X.append(x)
    print(sol(n, q, A, B, P, X))

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())

for i in range (N-1):
  a,b = map(int,input().split())
  flag = 0
  for j1, j2 in l:
    if (j1 == a) :
      flag = 1
      j2.append(b)
      '''
      j3 = j2
      print(j3)
      j3 = j3.append(b)
      l.append((j1,j3))
      '''
  if flag == 0:
    l.append((a,[b]))


ans = [0 for i in range(500000)]

for i in range(Q-1):
  p,q = map(int,input().split())
  flag = 0
  search = [p]
  while(flag != 1):
    for j1,j2 in l:
      if j1 == p:
        tmp = copy.copy(search)
        search = search + list(set(j2)-set(search))
        if(tmp == search) :
          flag = 1
  for k in search:
    ans[k] = ans[k] + q

for i in range(N+1):
  if i != 0:
    print (ans[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N, Q = map(int, input().split())
e = [[] for _ in range(2 * N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    e[a].append(b)

q = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    q[p] += x

seen = [False] * (2 * N + 1)
ans = [0] * (2 * N + 1)


def dfs(e, v, x):
    seen[v] = True
    ans[v] += x
    for next_v in e[v]:
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v, x + q[next_v])


dfs(e, 1, q[1])
ans = ans[1:]

for i in range(1, N + 1):
    print(ans[i], end=" ")

print()

Submission status: Runtime Error

Solution code:
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,input().split())
    val[a-1] += b 
visited = [True for i in range(N)]
def dps(i):
    visited[i] = False
    if i == N :
        return 1
    else :
        for j in graph[i]:
            if visited[j]:
                val[j] += val[i]
                dps(j)
dps(0)
print(val,end="")

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

class Node():
    def __init__(self):
        self.children = []
        self.count = 0



def add_count(G, v):
    for child in G[v].children:
        G[child].count += G[v].count
        add_count(G, child)


def main():
    G = [Node() for _ in range(N)]
    for _ in range(N-1):
        p, c = map(int, input().split())
        G[p-1].children.append(c-1)

    for _ in range(Q):
        p, x = map(int, input().split())
        G[p-1].count += x

    add_count(G, 0)

    counts = [node.count for node in G]
    print(*counts)

main()

Submission status: Runtime Error

Solution code:
#~~input~~
N,Q=map(int,input().split())
a=[]
b=[]
for i in range(N):
    A,B=input().split()
    a.append(int(A))
    b.append(int(B))
p=[]
x=[]
for i in range(Q):
    P,X=input().split()
    p.append(int(P))
    x.append(int(X))
#~add
def add_(c,tree_i,add_x):
  c[tree_i]+=add_x
  return c

#~~mk tree~~
counter=[0]*max(max(a)+1,max(b)+1)
dic = {}
for a_,b_ in zip(a,b):
  if a_ in dic.keys():
    dic[a_].append(b_)
  else:
    dic.setdefault(a_, []).append(b_)

for i in range(Q):
  j=p[i]
  def search_tree(j):
    #exist child
    for d_j in dic[j]:
      search_tree(d_j)
    #root add
    counter[j]+=x[i]
print(*counter)

Submission status: Runtime Error

Solution code:
import numpy as np

n,q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n+q-1)]

matrix = np.zeros((n,n))
ans = np.zeros((n,n))

for i in range(n-1):
  matrix[ab[i][0]-1,ab[i][1]-1] = 1
#  matrix[ab[i][1]-1,ab[i][0]-1] = 1

for l in range(n):
  for m in range(n):
    if matrix[l][m]:
      for o in range(n):
        if matrix[m][o]:
          matrix[l][o] = 1
          
ans = np.zeros((n))

for j in range(n-1,n+q-1):
  ans[ab[j][0]-1] += ab[j][1]
  for k in range(n):
    if matrix[ab[j][0]-1][k] == 1:
      ans[k] += ab[j][1]
  

for p in range(n):
  print(ans[p]、end = "")

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())

# 各ノードのリンクを記録
link_dict = dict()
for i in rage(n-1):
  a,b = map(int, input().split())
  if a in list(link_dict.keys()):
    link_dict(str(a-1)).add(b)
  else:
    link_dict(str(a-1)) = set(b)
  
# 各ノードの部分木の全てのノードをリストアップ
link_set = [set() for i in range(n-1)]
for i in list(link_dict.keys()).sort():
  link_set[int(i) - 1] = set(link_dict[i - 1])
  if int(i) < n - 1:
    for j in link_dict[str(int(i) - 1)]:
      if j < n - 1:
        link_set[i - 1] = link_set[i - 1] | link_set[j - 1]

# カウンターの計算を実施
counters = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  counters[p - 1] += x
  for node in link_set[p - 1]:
    counters[node - 1] += x
str_counters = [str(c) for c in counters]
print(' '.join(str_counters))

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self,name):
        self.name=name
        self.parent=[]
        self.counter=0
        self.children=[]
    def plus(self,num):
        self.counter+=num
        
n,q=[int(i) for i in input().split()]
henn=[]
        
#辺の情報    
for i in range(n-1):
    henn.append([int(i) for i in input().split()])


#カウンタの情報
plusdata=[]
for i in range(q):
    plusdata.append([int(i) for i in input().split()])   


#ノードの作成
nodelist=[]
for i in range(n):
    nodelist.append(Node(i+1))

#親の登録

#全て登録
for i in henn:
    nodelist[i[0]-1].parent.append(nodelist[i[1]-1])
    nodelist[i[1]-1].parent.append(nodelist[i[0]-1])
# for i in range(n):
#     print(nodelist[i].name,nodelist[i].parent,nodelist[i].counter)
    
node0=Node(0)
nodelist[0].parent.append(node0)

#排除
def parentdelete(node,i):
    for j in node.parent:
        if i==j:
            a=j
            node.parent.remove(a)
    node.children=node.parent
    for j in node.parent:
        parentdelete(j,node)
    node.parent=a
    
        
parentdelete(nodelist[0],node0)
    
# for i in range(n):
#     print(nodelist[i].name,nodelist[i].parent,nodelist[i].counter)
    
#カウンタの更新
for i in plusdata:
    nodelist[i[0]-1].plus(i[1])

# for i in nodelist:
#     print(i.counter)
    
anslist=[0 for i in range(n)]

def plusplus(node):
    global anslist
    name=node.name

    
def abc(node):
    node.counter+=node.parent.counter
    anslist[node.name-1]=node.counter
    for j in node.children:
        abc(j)
    
abc(nodelist[0])

for i in range(n):
    anslist[i]=str(anslist[i])
print(" ".join(anslist))