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: Time Limit Exceeded

Solution code:
N,Q=[int(s) for s in input().split()]
e_list=[[int(s) for s in input().split()] for i in range(N-1)]
q_list=[[int(s) for s in input().split()] for i in range(Q)]
#########深さ優先探索DFS
#########到達可能なもののうち新しく追加されたものを見る
#########訪れた順番を出力
def euler_tour(edge_list,start):
  reach=[[start,1,0]]
  ans=[start]
  path=[start]
  e_list=[[e[0],e[1],0] for e in edge_list]
  vertex=start
  endflag=0
  depth=1
  while True :
    ###まずvertexから到達可能なものをすべてreachに入れる
    #辺の始点がvertexであるもの
    for e in e_list:
      if (e[0]==vertex and e[2]==0):
        reach.append([e[1],0,depth])
        e[2]=1
      elif (e[1]==vertex and e[2]==0):
        reach.append([e[0],0,depth])
        e[2]=1
    ###起点になっていないもののうち最後にreachに入ったものを、次の起点とする
    for i in range(len(reach)+1):
      if reach[-i][1]==0 :
        vertex=reach[-i][0]
        #####depthが戻ったか？
        if reach[-i][2]<depth:
           ##戻った分だけpathをansに追加
          for j in range(1,depth-reach[-i][2]+1):
            path.remove(path[-1])
            ans.append(path[-1])
        ans.append(vertex)
        path.append(vertex)
        depth=reach[-i][2]+1
        #####ここでprint(vertex)などを入れる
        reach[-i][1]=1
        break
      if i==len(reach):  ####全ての場所に行っていれば終了
        for j in range(len(path)-1):
            path.remove(path[-1])
            ans.append(path[-1])
        return ans
        break
euler=euler_tour(e_list,1)
def eu(num):
  if num==1:
    return [i+1 for i in range(N)]
  ans=[]
  i=-1
  while True :
    i+=1
    if euler[i]==num:
      ii=euler[i-1]
      break
  while True:
    if euler[i]==ii:
      break
    ans.append(euler[i])
    i+=1
  return list(set(ans))
answer=[0 for i in range(N)]
for q in q_list:
  for v in eu(q[0]):
    answer[v-1]+=q[1]
print(*answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def main(edge, counter):

    def add_count(node, before=-1):
        for target in edge[node]:
            if target!=before:
                counter[target] += counter[node]
                add_count(target, node)

    add_count(0)

    return " ".join(str(i) for i in counter)


if __name__ == "__main__":
    n, q = map(int, input().split())
    edge = [[] for _ in range(n)]

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

    add_list = [0]*n

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

    print(main(edge, add_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def main(edge, counter):

    def add_count(node):
        for target in edge[node]:
            counter[target] += counter[node]
            edge[target].remove(node)
            add_count(target)

    add_count(0)

    return " ".join(str(i) for i in counter)


if __name__ == "__main__":
    n, q = map(int, input().split())
    edge = [[] for _ in range(n)]

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

    add_list = [0]*n

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

    print(main(edge, add_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def main(edge, counter):

    def add_count(node):
        for target in edge[node]:
            counter[target] += counter[node]
            edge[target].remove(node)
            add_count(target)

    add_count(0)

    return " ".join(str(i) for i in counter)


if __name__ == "__main__":
    n, q = map(int, input().split())
    edge = [[] for _ in range(n)]

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

    add_list = [0]*n

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

    print(main(edge, add_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def main(edge, counter):

    def add_count(node, before=-1):
        for target in edge[node]:
            if target != before:
                counter[target] += counter[node]
                add_count(target, node)

    add_count(0)

    return " ".join(str(i) for i in counter)


if __name__ == "__main__":
    n, q = map(int, input().split())
    edge = [[] for _ in range(n)]

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

    add_list = [0]*n

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

    print(main(edge, add_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200001)
N, Q = map(int, input().split())
a_b = [list(map(int, input().split())) for _ in range(N-1)]
p_x = [list(map(int, input().split())) for _ in range(Q)]
 
rin = [[] for _ in range(N)]
for v in a_b:
    rin[v[0]-1].append(v[1]-1)
    rin[v[1]-1].append(v[0]-1)
    
score = [0 for _ in range(N)]
for ele in p_x:
    score[ele[0]-1] +=ele[1]
#print(score)
 
def dfs(p, bp=-1):
    for c in rin[p]:
        if c != bp:
            #print(c)
            score[c]+= score[p]
            dfs(c, p)
 
dfs(0)
print(*score)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(20001)
N, Q = map(int, input().split())
a_b = [list(map(int, input().split())) for _ in range(N-1)]
p_x = [list(map(int, input().split())) for _ in range(Q)]

rin = deque([[] for _ in range(N)])
for v in a_b:
    rin[v[0]-1].append(v[1]-1)
    rin[v[1]-1].append(v[0]-1)
    
score = [0 for _ in range(N)]
for ele in p_x:
    score[ele[0]-1] +=ele[1]
#print(score)

def dfs(p, bp=-1):
    for c in rin[p]:
        if c != bp:
            #print(c)
            score[c]+= score[p]
            dfs(c, p)




dfs(0)
print(*score)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import *
sys.setrecursionlimit(10**8)
 
tree = [[] for _ in range(200001)]
scores = [0 for _ in range(200001)]

def dfs(pre, p):
    for child in tree[p]:
        if child == pre: continue
        scores[child] += scores[p]
        dfs(p, child)

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

    for _ in range(Q):
        p, x = map(int, input().split())
        scores[p] += x
    dfs(0, 1)
    print(' '.join(map(str, scores[1:N+1])))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
class Tree():
  def __init__(self,id):
    self.count = 0
    self.link = []
    self.parent = None
    self.child = []
    self.depth = None
    self.id = id

N, Q = [int(x) for x in input().split()]
G = [Tree(i) for i in range(1,N+1)]

for i in range(N-1):
  a,b = [int(x) for x in input().split()]
  G[a-1].link.append(b)
  G[b-1].link.append(a)
  
G[0].depth = 0
q = queue.Queue()
q.put(G[0])

while not q.empty():
  g = q.get()
  for l in g.link:
    if(l != g.parent):
      G[l-1].parent = g.id
      G[l-1].depth = g.depth + 1
      q.put(G[l-1])

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

q = queue.Queue()
q.put(G[0])

while not q.empty():
  g = q.get()
  for l in g.link:
    if(l != g.parent):
      G[l-1].count += g.count      
      q.put(G[l-1])

for i in range(N):
  if (i < N-1):  	
    print(G[i].count,end = " ")
  else:
    print(G[i].count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
cnd = [1]   # current_node
while len(cnd)>0:
    nd = cnd[0] # node
    if visited[nd-1]==0:
        ko = tree[nd-1]
        for i in range(len(ko)):
            k = ko[i]
            if visited[k-1]==0:
                c[k-1] += c[nd-1]
                cnd.append(k)
    visited[nd-1]=1
    cnd.pop(0)
print(" ".join(map(str,c)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
visited[0] = 1
while sum(visited)!=n:
    for i in range(1,n):
        if visited[i]==0:
            for j in range(len(tree[i])):
                node_tmp = tree[i][j]
                if visited[node_tmp-1]==1:
                    c[i] += c[node_tmp-1]
                    visited[i] = 1
print(" ".join(map(str,c)))

Submission status: Time Limit Exceeded

Solution code:
# import sys
# input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
for i in range(len(px)):
    c[px[i][0]-1] += px[i][1]
visited = [0]*n
visited[0] = 1
while sum(visited)!=n:
    for i in range(1,n):
        if visited[i]==0:
            for j in range(len(tree[i])):
                node_tmp = tree[i][j]
                if visited[node_tmp-1]==1:
                    c[i] += c[node_tmp-1]
                    visited[i] = 1
print(" ".join(map(str,c)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
px = [ list(map(int,input().split())) for _ in range(q) ]
# print(tree)
# print(px)
c = [0]*n
for i in range(len(px)):
    c[px[i][0]-1] += px[i][1]
# print(c)
# for i in range(1,n):
#     c[i] += c[min(tree[i])-1]
visited = [0]*n
visited[0] = 1
while sum(visited)!=n:
    for i in range(1,n):
        if visited[i]==0:
            for j in range(len(tree[i])):
                node_tmp = tree[i][j]
                if visited[node_tmp-1]==1:
                    c[i] += c[node_tmp-1]
                    visited[i] = 1
print(" ".join(map(str,c)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
px = [ list(map(int,input().split())) for _ in range(q) ]
# print(tree)
# print(px)
c = [0]*n
for i in range(len(px)):
    c[px[i][0]-1] += px[i][1]
# print(c)
# for i in range(1,n):
#     c[i] += c[min(tree[i])-1]
visited = [0]*n
visited[0] = 1
while sum(visited)!=n:
    for i in range(1,n):
        for j in range(len(tree[i])):
            node_tmp = tree[i][j]
            if visited[node_tmp-1]==1 and visited[i]==0:
                c[i] += c[node_tmp-1]
                visited[i] = 1
            else:
                pass
print(" ".join(map(str,c)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
px = [ list(map(int,input().split())) for _ in range(q) ]
# print(tree)
# print(px)
c = [0]*n
for i in range(len(px)):
    c[px[i][0]-1] += px[i][1]
# print(c)
# for i in range(1,n):
#     c[i] += c[min(tree[i])-1]
visited = [0]*n
visited[0] = 1
check = sum(visited)
while check!=n:
    for i in range(1,n):
        for j in range(len(tree[i])):
            node_tmp = tree[i][j]
            if visited[node_tmp-1]==1 and visited[i]==0:
                c[i] += c[node_tmp-1]
                visited[i] = 1
            else:
                pass
    check = sum(visited)
print(" ".join(map(str,c)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q = map(int, input().split())
# print(n,q)
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
px = [ list(map(int,input().split())) for _ in range(q) ]

# print(tree)
# print(px)

c = [0]*n

for i in range(len(px)):
    c[px[i][0]-1] += px[i][1]

# print(c)

# for i in range(1,n):
#     c[i] += c[min(tree[i])-1]

visited = [False]*n
visited[0] = True
# print(visited)
check = visited.count(False)
# print(check)
while check!=0:
    for i in range(1,n):
        # mi = min(tree[i])-1
        for j in range(len(tree[i])):
            node_tmp = tree[i][j]
            if visited[node_tmp-1]==True and visited[i]==False:
                c[i] += c[node_tmp-1]
                visited[i] = True
                # print("OK")
            else:
                pass
                # print("NG")
    check = visited.count(False)

print(" ".join(map(str,c)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(50000)

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

ki = [[] for _ in range(250005)]
result = [0] * N

for i in range(N - 1):
    p,c = map(int,input().split())
    ki[p - 1].append(c - 1)
    ki[c - 1].append(p - 1)

for i in range(Q):
    n,x = map(int,input().split())
    result[n - 1] += x

def dfs(start, parent):
    for child in ki[start]:
        if child == parent:
            continue

        result[child] += result[start]
        dfs(child, start)

dfs(0, -1)
print(" ".join(map(str, result)))

Submission status: Time Limit Exceeded

Solution code:
def get_answer(ki):
    n = ki[0][0]
    q = ki[0][1]
    #n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    #q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    n_data = ki[1:-q]
    #q_data = ki[-q:]
    q_index = [0] * n
    for qq in ki[-q:]:
        q_index[qq[0] - 1] += qq[1]

    score = [0] * n

    """
        assert get_answer(["4 3",
                       "1 3", "1 4", "2 3",
                       "2 10", "1 100", "3 1"]) == "100 111 101 100"
    """
    t_index = []
    for i in range(0, n + 1):
        t_index.append([])
    for nn in n_data:
        t_index[nn[0]].append(nn[1])
        t_index[nn[1]].append(nn[0])

    k_stack = [[1, 0]]
    #t_stack = [1]
    #s_stack = [0]
    r_flag = [0] * n
    while len(k_stack) > 0:
        #i = t_stack.pop()
        #s = s_stack.pop()
        k = k_stack.pop()
        i = k[0]
        s = k[1]
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        s += q_index[i - 1]
        score[i - 1] += s
        k_stack += [[t, s] for t in t_index[i]]
        #t_stack += t_index[i]
        #s_stack += [s] * len(t_index[i])

    s_value = str(score[0])
    for i in range(1, n):
        s_value += " " + str(score[i])
    return s_value


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            s = input1.split(" ")
            input_ki.append([int(s[0]), int(s[1])])
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Time Limit Exceeded

Solution code:
def get_answer(ki):
    n = ki[0][0]
    q = ki[0][1]
    #n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    #q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    n_data = ki[1:-q]
    #q_data = ki[-q:]
    q_index = [0] * n
    for qq in ki[-q:]:
        q_index[qq[0] - 1] += qq[1]

    score = [0] * n

    """
        assert get_answer(["4 3",
                       "1 3", "1 4", "2 3",
                       "2 10", "1 100", "3 1"]) == "100 111 101 100"
    """
    t_index = []
    for i in range(0, n + 1):
        t_index.append([])
    for nn in n_data:
        t_index[nn[0]].append(nn[1])
        t_index[nn[1]].append(nn[0])

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        s += q_index[i - 1]
        score[i - 1] += s
        t_stack += t_index[i]
        s_stack += [s] * len(t_index[i])

    s_value = str(score[0])
    for i in range(1, n):
        s_value += " " + str(score[i])
    return s_value


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            s = input1.split(" ")
            input_ki.append([int(s[0]), int(s[1])])
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Time Limit Exceeded

Solution code:
import queue

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

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

c = [0]*n

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

ans = [0]*n
visited = [0]*n

que = queue.Queue()

que.put(0)
visited[0]=1
ans[0]+=c[0]

while not que.empty():
    x = que.get()
    for y in d[x]:
        if visited[y]==1:
            continue
        else:
            ans[y]+=ans[x]+c[y]
            visited[y]=1
            que.put(y)



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

Submission status: Time Limit Exceeded

Solution code:
def get_answer(ki):
    n = ki[0][0]
    q = ki[0][1]
    #n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    #q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    n_data = ki[1:-q]
    #q_data = ki[-q:]
    q_index = [0] * n
    for qq in ki[-q:]:
        q_index[qq[0] - 1] += qq[1]

    score = [0] * n

    """
        assert get_answer(["4 3",
                       "1 3", "1 4", "2 3",
                       "2 10", "1 100", "3 1"]) == "100 111 101 100"
    """
    t_index = {}
    for i in range(1, n + 1):
        t_index[i] = []
    for nn in n_data:
        t_index[nn[0]].append(nn[1])
        t_index[nn[1]].append(nn[0])


    """
    for qq in q_data:
        i = qq[0]
        if i in q_index.keys():
            q_index[i] += qq[1]
        else:
            q_index[i] = qq[1]
    """

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        s += q_index[i - 1]
        score[i - 1] += s
        t_stack += t_index[i]
        #for si in range(len(t_index[i])):
        #    s_stack.append(s)
        s_stack += [s] * len(t_index[i])

    s_value = str(score[0])
    for i in range(1, n):
        s_value += " " + str(score[i])
    return s_value


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            s = input1.split(" ")
            input_ki.append([int(s[0]), int(s[1])])
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Time Limit Exceeded

Solution code:
def get_answer(ki):
    n = ki[0][0]
    q = ki[0][1]
    #n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    #q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    n_data = ki[1:-q]
    q_data = ki[-q:]
    score = [0] * n

    """
        assert get_answer(["4 3",
                       "1 3", "1 4", "2 3",
                       "2 10", "1 100", "3 1"]) == "100 111 101 100"
    """
    t_index = {}
    for i in range(1, n + 1):
        t_index[i] = []
    for nn in n_data:
        t_index[nn[0]].append(nn[1])
        t_index[nn[1]].append(nn[0])

    q_index = {}
    for qq in q_data:
        i = qq[0]
        if i in q_index.keys():
            q_index[i] += qq[1]
        else:
            q_index[i] = qq[1]

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        if i in q_index.keys():
            s += q_index[i]
        score[i - 1] += s
        t_stack += t_index[i]
        for si in range(len(t_index[i])):
            s_stack.append(s)

    s_value = str(score[0])
    for i in range(1, n):
        s_value += " " + str(score[i])
    return s_value


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            s = input1.split(" ")
            input_ki.append([int(s[0]), int(s[1])])
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
N,Q = map(int,input().split())

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

adds = {}
ans = {}
for i in range(1,N+1):
    adds[i] = 0
    ans[i] = 0
for q in range(Q):
    p,x = map(int,input().split())
    adds[p] += x

checked = [False for _ in range(N+1)]
def dig(i,tmp):
    tmp += adds[i]
    ans[i] = tmp
    checked[i] = True
    for v in tree[i]:
	    if not checked[v]: dig(v,tmp)

tmp = 0
dig(1,tmp)

print(' '.join(str(ans[i]) for i in range(1,N+1)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
N,Q = map(int,input().split())

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

adds = {}
ans = {}
for i in range(1,N+1):
    adds[i] = 0
    ans[i] = 0
for q in range(Q):
    p,x = map(int,input().split())
    adds[p] += x

checked = [False for _ in range(N+1)]
def dig(i,tmp):
    global checked
    tmp += adds[i]
    ans[i] = tmp
    checked[i] = True
    for v in tree[i]:
	    if not checked[v]: dig(v,tmp)

tmp = 0
dig(1,tmp)

print(' '.join(str(ans[i]) for i in range(1,N+1)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
from queue import deque
N,Q = map(int,input().split())

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

adds = {}
ans = {}
for i in range(1,N+1):
    adds[i] = 0
    ans[i] = 0
for q in range(Q):
    p,x = map(int,input().split())
    adds[p] += x
# print(tree)
# print(adds)

checked = [False for _ in range(N+1)]
def dig(i,tmp):
    global checked
    tmp += adds[i]
    ans[i] = tmp
    checked[i] = True
    for v in tree[i]:
	    if not checked[v]: dig(v,tmp)

tmp = 0
dig(1,tmp)

print(' '.join(str(ans[i]) for i in range(1,N+1)))

Submission status: Time Limit Exceeded

Solution code:
def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    score = [0] * n

    """
        assert get_answer(["4 3",
                       "1 3", "1 4", "2 3",
                       "2 10", "1 100", "3 1"]) == "100 111 101 100"
    """
    t_index = {}
    for i in range(1, n + 1):
        t_index[i] = []
    for nn in n_data:
        t_index[nn[0]].append(nn[1])
        t_index[nn[1]].append(nn[0])

    q_index = {}
    for qq in q_data:
        i = qq[0]
        if i in q_index.keys():
            q_index[i] += qq[1]
        else:
            q_index[i] = qq[1]

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        if i in q_index.keys():
            s += q_index[i]
        score[i - 1] += s
        t_stack += t_index[i]
        for si in range(len(t_index[i])):
            s_stack.append(s)

    s_value = str(score[0])
    for i in range(1, n):
        s_value += " " + str(score[i])
    return s_value


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N-1)]
px = [list(map(int,input().split())) for _ in range(Q)]

query = [0] * N
ans = [0] * N

for p,x in px:
    query[p-1] = query[p-1] + x
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(a-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    val += query[v]
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
    return 
        
dfs(0,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N,Q = map(int,input().split())
ab_list = [tuple(map(int,input().split())) for _ in range(N-1)]
px_list = [tuple(map(int,input().split())) for _ in range(Q)]

px_dict = {}
for i in range(N+1):
    px_dict[i] = 0

for p, x in px_list:
    px_dict[p] += x

ab_dict = {}
for i in range(N+1):
    ab_dict[i] = []

for a,b in ab_list:
    ab_dict[a].append(b)
    ab_dict[b].append(a)
    
passed = [0 for _ in range(N+1)]

scores = [0 for _ in range(N+1)] # 1子おおい

def add_cnt(v, score):
    passed[v] = 1
    # pxdictから持ってきてスコアを足す
    score += px_dict[v]

    #今いる頂点に現在のスコアをめも
    scores[v] = score
    
    # 繋がっている頂点に今のスコアを投げる
    for b in ab_dict[v]:
        if passed[b] == 0:
            add_cnt(b,score)

add_cnt(1,0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, q = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
adj = [[] for _ in range(n)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

query = [0]*n
for _ in range(q):
    a, v = map(int, input().split())
    query[a-1] += v

q = [0]
ans = [0]*n
visited = [False]*n
visited[0] = True
while q:
    cur = q.pop(0)
    visited[cur] = True
    ans[cur] += query[cur]
    for nex in adj[cur]:
        if not visited[nex]:
            ans[nex] += ans[cur]
            q.append(nex)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)

query = [0]*N
for _ in range(Q):
    a, v = map(int, input().split())
    query[a-1] += v

Q = [[0, 0]]
ans = [0]*N
visited = [False]*N
visited[0] = True
while Q:
    cur, add = Q.pop(0)
    add += query[cur]
    ans[cur] = add
    visited[cur] = True
    for nex in adj[cur]:
        if not visited[nex]:
            Q.append([nex, add])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)

query = [0]*N
for _ in range(Q):
    a, v = map(int, input().split())
    query[a-1] += v

Q = [[0, 0]]
ans = [0]*N
visited = [False]*N
visited[0] = True
while Q:
    cur, add = Q.pop(0)
    add += query[cur]
    ans[cur] = add
    for nex in adj[cur]:
        if not visited[nex]:
            Q.append([nex, add])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)

query = [0]*N
for _ in range(Q):
    a, v = map(int, input().split())
    query[a-1] += v

Q = [[0, -1, 0]]
ans = [0]*N
while Q:
    cur, prev, add = Q.pop(0)
    add += query[cur]
    ans[cur] = add
    for nex in adj[cur]:
        if nex != prev:
            Q.append([nex, cur, add])
print(*ans)