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:
N, Q = [int(x) for x in input().split()]

V = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    V[a].add(b)

C = [0] * N

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

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


dfs(0, 0)

print(" ".join([str(x) for x in ANS]))

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    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 = ""
try:
    for i in range(1, N+1):
        output_str += str(output_lst[i]) + " "
except:
    pass
print(output_str)

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, id, parent=None):
        self.id = id
        self.parent = parent
        self.children = []

    def add_all(self):
        for child in self.children:
            counter[child.id] += counter[self.id]
            child.add_all()

N, Q = map(int, input().split())
tree = [None] * N
counter = [0] * N
tree[0] = Node(0) # root (1)
for i in range(N-1):
    a, b = map(int, input().split())
    tree[b-1] = Node(b-1, a-1)
    tree[a-1].children.append(tree[b-1])

for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
    
tree[0].add_all()
print(' '.join(list(map(str, counter))))

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    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)
try:
    count_add(info_lst, pi_xi_sum_lst, output_lst, current_node=1, adding=pi_xi_sum_lst[1])
except:
    pass
output_str = ""
for i in range(1, N+1):
    output_str += str(output_lst[i]) + " "

print(output_str)

Submission status: Runtime Error

Solution code:
input_line = list(map(int, input().split()))
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]
a = []
for i in range(input_line[1]):
    count_info = list(map(int, input().split()))
    counter[count_info[0]-1] += count_info[1]
    for i in range(1,len(input_line[0])):
        counter[i] += counter[i-1]
print(" ".join(counter))

Submission status: Runtime Error

Solution code:
def parent(array,count,index,root):
    array[index-1].remove(root)
    count[index-1]+=count[root-1]
    for i in array[index-1]:
        parent(array,count,i,index)
num,q=map(int,input().split())
counter=[0 for _ in range(num)]
roots=[set() for _ in range(num)]
for _ in range(num-1):
    a,b=map(int,input().split())
    roots[a-1].add(b)
    roots[b-1].add(a)
for _ in range(q):
    p,x=map(int,input().split())
    counter[p-1]+=x
for ele in roots[0]:
    parent(roots,counter,ele,1)
print(" ".join([str(counter[i]) for i in range(num)]))

Submission status: Runtime Error

Solution code:
import numpy as np
n, q =  list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(n-1)]
y = [list(map(int, input().split())) for i in range(q)]

res = np.zeros(n)
for i in range(q):
    res[y[i][0]-1] += y[i][1]
    for j in range(n-1):
        if x[j][0] >= y[i][0]:
            res[x[j][1]-1] += y[i][1]
for i in res:
    if i == n-2:
        print(res[i], end="")
    else:
        print(s, end =" ")

Submission status: Runtime Error

Solution code:
N, Q = map(int,input().split())
graph = {i:[] for i in range(N)}
G = {i:[] for i in range(N)}
ans = [0 for i in range(N)]
c = [0 for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  graph[a-1] += [b-1]
  graph[b-1] += [a-1]
stuck = [0]
log = [0 for i in range(N)]
log[0]=1
ls = [0]
while stuck:
  x = stuck.pop()
  A = graph[x]
  flag = True
  ki = []
  for a in A:
    if log[a]==0:
      stuck+=[a]
      ki+=[a]
      log[a]=1
      flag = False
  for l in ls:
    G[l] += ki
  ls += ki
  if flag:
    ls.remove(x)
for i in range(Q):
  p, x = map(int,input().split())
  p = p-1
  c[p]+=x

for k in G.keys():
  for x in G[k]:
    ans[x]+=c[k]
  ans[k]+=c[k]
A = map(str,ans)
print(' '.join(ans))

Submission status: Runtime Error

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

tree_dict = {}
for i in range(n-1):
    a, b = map(int, input().split())
    if tree_dict.get(a) == None:
        tree_dict[a] = {}
    tree_dict[a][len(tree_dict[a])] = b

ans = [0]*(n+1)

def add(p_, x_,):
    for i in range(len(tree_dict[p_])):
        ans[  tree_dict[p_][i] ] += x_
        if tree_dict.get(tree_dict[p_][i]) != None:
            add(tree_dict[p_][i], x_)

p = [0]* q
x = [0]* q
for j in range(q):
    p, x = map(int, input().split())
    ans[p] += x
    if tree_dict.get(p) != None:
        add(p,x)

print(*ans[1:])

Submission status: Runtime Error

Solution code:

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

G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

## クエリを覚えておく
scores = [0]*N
for i in range(Q):
    p,x = map(int, input().split())
    scores[p-1] += x 

ans = [0]*N
ans[0] = scores[0]

used = [False] * N
def dfs(G, v):
   # vを訪問済みにする
   used[v] = True
   #グラフ中の次のVについて
   for next_v in G[v]:
       # すでに見られていたら無視
       if used[next_v]: continue
       # 見られていない場合、再帰的に探索
       # 親のスコアも足していく
       ans[next_v] = ans[v] + scores[next_v]
       dfs(G, next_v)

dfs(G,0)
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, q =  list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(n-1)]
y = [list(map(int, input().split())) for i in range(q)]

res = np.zeros(n)
for i in range(q):
    res[y[i][0]-1] += y[i][1]
    for j in range(n-1):
        if x[j][0] >= y[i][0]:
            res[x[j][1]-1] += y[i][1]
for i in res:
    if i == n-1:
        print(res[i], end="")
    else:
        print(s, end =" ")

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    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)]
#try:
for _ in range(N-1): # 10**5
    ai, bi = map(int, input().split())
    info_lst[ai].append(bi)
    info_lst[bi].append(ai)
#except:
#    print() # これでWAになると思われる


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

pi_xi_sum_lst = [0]*(N+1)
#try:
for _ in range(Q): # 10**5
    pi, xi = map(int, input().split())
    pi_xi_sum_lst[pi] += xi
#except:
#    print() # これでWAになると思われる

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 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
    tree[b][a] = 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 pprint

def comp(s, l):
    ans = set(s)
    l2 = s
    for i in l2:
        if i != 0:
            ans = ans | comp(l[i], l)
    return ans


def solve():
    n, q = map(int, input().split())
    l = [[0] for i in range(n+1)]
    ans = [0]*(n+1)
    for i in range(n-1):
        a, b = map(int, input().split())
        l[a].append(b)
    for i in range(q):
        num, point = map(int, input().split())
        li = list(comp(l[num], l))
        li.append(num)
        li = list(set(li))
        for j in li:
            ans[j] += point
    ans2 = list(map(str, ans))
    ans3 = ' '.join(ans2[1::])
    print(ans3)


if __name__=="__main__":
    solve()

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    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)]
#try:
for _ in range(N-1): # 10**5
    ai, bi = map(int, input().split())
    info_lst[ai].append(bi)
    info_lst[bi].append(ai)
#except:
#    print() # これでWAになると思われる


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)
#try:
for _ in range(Q): # 10**5
    pi, xi = map(int, input().split())
    pi_xi_sum_lst[pi] += xi
#except:
#    print() # これでWAになると思われる

output_lst = [0]*(N+1)
try:
    count_add(info_lst, pi_xi_sum_lst, output_lst, current_node=1, adding=pi_xi_sum_lst[1])
except:
    pass
output_str = ""
for i in range(1, N+1):
    output_str += str(output_lst[i]) + " "

print(output_str)

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    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)]
#try:
for _ in range(N-1): # 10**5
    ai, bi = map(int, input().split())
    info_lst[ai].append(bi)
    info_lst[bi].append(ai)
#except:
#    print() # これでWAになると思われる


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)
try:
    for _ in range(Q): # 10**5
        pi, xi = map(int, input().split())
        pi_xi_sum_lst[pi] += xi
except:
    print() # これでWAになると思われる

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())
ans = [0] * n
ki = {1 : [1]}
for _ in range(n - 1):
  a, b = map(int, input().split())
  if not ki.get(b):
    ki[b] = []
  ki[b] = ki[a] + [b]
ki = ki.values()

p = {}
for _ in range(q):
  c, d = map(int, input().split())
  if c not in p.keys():
    p[c] = d
  else:
    p[c] = p[c] + d

for e, f in p.items():
  for n, k in enumerate(ki):
    if e in k:
      ans[n] += f
  
ans2 = ''
for e in ans:
  print(e, end=' ')

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    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)]
try:
    for _ in range(N-1): # 10**5
        ai, bi = map(int, input().split())
        info_lst[ai].append(bi)
        info_lst[bi].append(ai)
except:
    print() # これでWAになると思われる


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)
try:
    for _ in range(Q): # 10**5
        pi, xi = map(int, input().split())
        pi_xi_sum_lst[pi] += xi
except:
    print() # これでWAになると思われる

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())
l = [ [] for i in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    l[a-1].append(b-1)
ans = [0 for _ in range(n)]
p = [list(map(int,input().split())) for i in range(q)]
def f(p,x):
    ans[p] +=x
    for i in l[p]:
        f(i,x)
for p1 in p:
    f(p1[0]-1,p1[1])
print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    output_lst[current_node] += adding
    try:
        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]
    except:
        pass # これでWAになると思われる

def glaph_2_tree(info_lst, passed_place, current_node):
#    try:
    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

 #   except:
  #      print() # これでWAになると思われる

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:
#!/usr/bin/env python

def addToChild(i,ci):
    global c, visit
    visit[i]= True
    #
    for v in edge[i]:
        if visit[v]: continue
        c[v]+= ci
        addToChild(v,c[v])

import sys

n,q = [ int(x) for x in sys.stdin.readline().strip().split() ]
edge= [ [] for _ in range(n) ]
for i in range(n-1):
    a,b = [ int(x)-1 for x in sys.stdin.readline().strip().split() ]
    edge[a].append( b )
    edge[b].append( a )
#
sys.setrecursionlimit(n)
c= [ 0 for _ in range(n) ]
for i in range(q):
    p,x= [ int(x) for x in sys.stdin.readline().strip().split() ]
    c[p-1]+= x
#
visit= [ False for _ in range(n) ]
addToChild(0,c[0])
for ci in c: print( ci,end=" " )

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):
        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())
try:
  n, q = f()
  tree = Tree(n)
  for i in xrange(n - 1):
    tree.addNode(*f())
except:
    print ""
    exit()
for i in xrange(q):
     tree.update(*f())
tree.ans()

Submission status: Runtime Error

Solution code:

def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    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):
    try:
        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

    except:
        print() # これでWAになると思われる

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())
counter = [0 for _ in range(n)]
tree = [None for _ in range(n)]

edges = defaultdict(list)
for _ in range(n - 1):
  a, b = map(lambda x: int(x) - 1, input().split())
  edges[a].append(b)
  edges[b].append(a)

def construct(indices):
  rt = set()
  for index in indices:
    children = edges.pop(index)
    tree[index] = set(children) - roots
    roots.update({index})
    rt = rt.union(tree[index], construct(tree[index]))
  return rt

roots = {0}
tree[0] = construct({0})

for _ in range(q):
  p, x = map(int, input().split())
  counter[p-1] += x
  children = tree[p-1]
  for child in children:
    counter[child] += x

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

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=[]

node_append= node.append
apex_append= apex.append
for i in range(n+2):
	node_append([])
	apex_append(0)

for i in range(1,n):
	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:
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:
  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:
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):
        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())
try:
  n, q = f()
  tree = Tree(n)
  for i in xrange(n - 1):
    tree.addNode(*f())
except:
    print ""
    exist()
for i in xrange(q):
     tree.update(*f())
tree.ans()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
edge = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

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

ans = [0] * n
def dfs(v,p,value): #p: parent of v
    value += cost[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)
# def dfs(cur, c, root):
    # # print(cur, c, root)
    # ans[cur] = c
    # for nex in edge[cur]:
        # if nex != root:
            # dfs(nex, c + cost[nex], cur)

dfs(0, -1, 0)
print(*ans)

Submission status: Runtime Error

Solution code:
N,Q=list(map(int,input().split()))
cnt=[0]*N
dic={}
for _ in range(N-1):
    temp=list(map(int,input().split()))
    dic.setdefault(temp[0],[]).append(temp[1])
p=[]
X=[]
for _ in range(Q):
    temp2=list(map(int,input().split()))
    p.append(temp2[0])
    X.append(temp2[1])
k=dic.keys()

def tree(o):
    for y in dic[o]:
        cnt[y-1]+=add
        if y in k:
            tree(y)

for x in range(Q):
    add=X[x]
    cnt[p[x]-1]+=add
    if p[x] in k:
        tree(p[x])

print(*cnt)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline


class Node:
    def __init__(self, id):
        self.id = id
        self.next = []
        self.val = 0

    def set_node(self, node):
        self.next.append(node)


def add_val(node, val):
    global tree
    node.val += val
    if not node.next:
        return
    for i in node.next:
        add_val(tree[i], val)


n, q = map(int, input().split())
tree = [Node(id) for id in range(n + 1)]
query = [0 for _ in range(n + 1)]

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

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

for i in range(1, n + 1):
    val = query[i]
    if val != 0:
        add_val(tree[i], val)

print(*[tree[i].val for i in range(1, n + 1)])

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:
    if a[1] not in relations[a[0]]:
      relations[a[0]].append(a[1])
    
for q in qlist:
  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:
n, q = map(int, input().split())

# 各ノードのリンクを記録
link_dict = dict()
keys = []
for i in range(n-1):
  a,b = map(int, input().split())
  if a in keys:
    link_dict[str(a-1)].add(b)
  else:
    keys.append(a)
    link_dict[str(a-1)] = {b}
  
# 各ノードの部分木の全てのノードをリストアップ
link_set = [set() for i in range(n-1)]
for i in sorted(keys, reverse=True):
  link_set[int(i) - 1] = set(link_dict[str(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:
import sys

input = sys.stdin.readline


class Node:
    def __init__(self, id):
        self.id = id
        self.next = []
        self.val = 0

    def set_node(self, node):
        self.next.append(node)


def add_val(node, val):
    global tree
    node.val += val
    if not node.next:
        return
    for i in node.next:
        add_val(tree[i], val)


n, q = map(int, input().split())
tree = [Node(id) for id in range(n + 1)]
query = [0 for _ in range(n + 1)]

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

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

for i in range(n):
    val = query[i]
    if val != 0:
        add_val(tree[i], val)

print(*[tree[i].val for i in range(1, n + 1)])

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
ans = [0] * n
ki = {1 : [1]}
for _ in range(n - 1):
  a, b = map(int, input().split())
  ki[b] = ki[a] + [b]
ki = ki.values()

p = {}
for _ in range(q):
  c, d = map(int, input().split())
  if c not in p.keys():
    p[c] = d
  else:
    p[c] = p[c] + d

for e, f in p.items():
  for n, k in enumerate(ki):
    if e in k:
      ans[n] += f
  
ans2 = ''
for e in ans:
  print(e, end=' ')