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:
def main():
    import sys
    input=sys.stdin.readline
    N,Q = map(int,input().split())
    AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
    PX = [[x for x in map(int,input().split())] for _ in range(Q)]

    G = [[] for _ in range(N+1)]
    for a,b in AB:
        G[a].append(b)
        G[b].append(a)

    cnt = [0]*N
    for p,x in PX:
        cnt[p-1] += x

    color = ["WHITE"] * (N+1)
    stack = []

    def dfs(u):
        stack.append(u)
        color[u] = "GRAY"

        while len(stack) > 0:
            u = stack[-1]
            if len(G[u]) == 0:
                color[u] = "BLACK"
                stack.pop()
            else:
                u_next = G[u].pop(0)
            if color[u_next] == "WHITE":
                color[u_next] = "GRAY"
                cnt[u_next-1] += cnt[u-1]
                stack.append(u_next)
    dfs(1)
    print(*cnt)


    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q = map(int,input().split())
AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
PX = [[x for x in map(int,input().split())] for _ in range(Q)]
 
G = [[] for _ in range(N+1)]
for a,b in AB:
    G[a].append(b)
    G[b].append(a)
 
cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x

color = ["WHITE"] * (N+1)
stack = []

def dfs(u):
    stack.append(u)
    color[u] = "GRAY"

    while len(stack) > 0:
        u = stack[-1]
        if len(G[u]) == 0:
            color[u] = "BLACK"
            stack.pop()
        else:
            u_next = G[u].pop(0)
            if color[u_next] == "WHITE":
                color[u_next] = "GRAY"
                cnt[u_next-1] += cnt[u-1]
                stack.append(u_next)
dfs(1)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
PX = [[x for x in map(int,input().split())] for _ in range(Q)]
 
G = [[] for _ in range(N+1)]
for a,b in AB:
    G[a].append(b)
    G[b].append(a)
 
cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x

color = ["WHITE"] * (N+1)
stack = []

def dfs(u):
    stack.append(u)
    color[u] = "GRAY"

    while len(stack) > 0:
        u = stack[-1]
        if len(G[u]) == 0:
            color[u] = "BLACK"
            stack.pop()
        else:
            u_next = G[u].pop(0)
            if color[u_next] == "WHITE":
                color[u_next] = "GRAY"
                cnt[u_next-1] += cnt[u-1]
                stack.append(u_next)
dfs(1)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a = II()
    s = input()
    print(s if a >= 3200 else "red")
    return

#B
def B():
    II()
    a = LI()
    ans = 0
    for ai in a:
        ans += 1 / ai
    print(1/ans)
    return

#C
def C():
    n = II()
    v = LI()
    q = []
    for vi in v:
        heappush(q, vi)
    while 1:
        a = heappop(q)
        if q:
            b = heappop(q)
            heappush(q, (a + b) / 2)
        else:
            print(a)
            return

#D
def D():
    n, q = LI()
    tree = [[] for i in range(n)]
    for _ in range(n - 1):
        a, b = LI_()
        tree[a].append(b)
        tree[b].append(a)
    ans = [0] * n
    c = defaultdict(int)
    def dfs(now):
        for nex in tree[now]:
            if c[nex]:
                continue
            c[nex] += 1
            ans[nex] += ans[now]
            dfs(nex)
    for _ in range(q):
        p, x = LI_()
        x += 1
        ans[p] += x
    c[0] = 1
    dfs(0)
    print(*ans)
    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input=lambda :sys.stdin.readline()

def sol():

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

  for _ in range(Q):
    p, x = map(int,input().split())
    ans[p-1] += x 
 
  def dfs(v,p=-1):
    for u in graph[v]:
      if u == p: continue
      ans[u] += ans[v]
      dfs(u,v)
  dfs(0)
  print(*ans)

sol()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input=lambda :sys.stdin.readline().rstrip()

def sol():

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

  for _ in range(Q):
    p, x = map(int,input().split())
    ans[p-1] += x 
 
  def dfs(v,p=-1):
    for u in graph[v]:
      if u == p: continue
      ans[u] += ans[v]
      dfs(u,v)
  dfs(0)
  print(*ans)

sol()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input=lambda :sys.stdin.readline().rstrip()

def dfs(v,p=-1):
  for u in graph[v]:
    if u == p: continue
    ans[u] += ans[v]
    dfs(u,v)

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

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

dfs(0)
print(*ans)

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)]
#まずQを頂点ごとに集計
v_list=[0 for s in range(N+1)]
for q in q_list:
  v_list[q[0]]+=q[1]
#print(v_list)

#########オイラーツアー（部分木の出力）
#########到達可能なもののうち新しく追加されたものを見る
#########訪れた順番を出力
def euler_tour(edge_list):  
  ans_list=[0 for s in range(N+1)]
  reach=[[1,1,0]]
  route=[1]
  val_q=v_list[1] #この値を増減させてans_listにいれる
  ans_list[1]=val_q
  path=[1]
  e_list=[[e[0],e[1],0] for e in edge_list]
  vertex=1
  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])
          #  route.append(path[-1])
          val_q=ans_list[path[-1]]
        val_q+=v_list[vertex]
        ans_list[vertex]=val_q
      #  route.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])
      #      route.append(path[-1])
        return ans_list
        break
print(*euler_tour(e_list)[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

T=[[] for i in range(N)]

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

O=[0 for i in range(N)]

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

def dfs(n):
    for i in T[n]:
        if r[i]:continue
        r[i]=1
        O[i]+=O[n]
        dfs(i)

r=[1]+[0]*(N-1)

dfs(0)

print(*O)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

T=[[] for i in range(N)]

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

O=[0 for i in range(N)]

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

def dfs(n):
    for i in T[n]:
        if r[i]==1:continue
        r[i]=1
        O[i]+=O[n]
        dfs(i)

r=[1]+[0]*(N-1)

dfs(0)

print(*O)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

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

T=[[] for i in range(N)]

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

O=[0 for i in range(N)]

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

def dfs(n,r):
    for i in T[n]:
        if i!=r:
            O[i]+=O[n]

            dfs(i,n)

dfs(0,-1)

print(*O)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input=lambda :sys.stdin.readline().rstrip()

def dfs(v,p=-1):
  for u in graph[v]:
    if u == p: continue
    ans[u] += ans[v]
    dfs(u,v)

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

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

dfs(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def dfs(v,p=-1):
  for u in graph[v]:
    if u == p: continue
    ans[u] += ans[v]
    dfs(u,v)

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

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

dfs(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def dfs(v,p=-1):
  for u in graph[v]:
    if u == p: continue
    ans[u] += ans[v]
    dfs(u,v)

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

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

dfs(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def dfs(v,p=-1):
  for u in graph[v]:
    if u == p: continue
    ans[u] += ans[v]
    dfs(u,v)

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

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

dfs(1)
print(' '.join([str(a) for a in ans[1:]]))

Submission status: Time Limit Exceeded

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

Edges = [list(map(int,input().split())) for i in range(n-1)]

Graph = [[] for i in range(n)]
for edge in Edges:
    Graph[edge[0]-1].append(edge[1]-1)
    Graph[edge[1]-1].append(edge[0]-1)

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

Counter = [0 for i in range(n)]
for point in Points:
  Counter[point[0]-1] += point[1]

Parents = [-1 for i in range(n)]
Parents[0] = 0

stack = [0]
while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Parents[adj] == -1:
            Parents[adj] = node
            Counter[adj] += Counter[node]
            stack.append(adj)

print(*Counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)
    ans=[0]*n
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        ans[p]+=x

    def dfs(v,p=-1):
        for u in E[v]:
            if u==p: continue
            ans[u]+=ans[v]
            dfs(u,v)

    dfs(0)
    print(*ans)

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class EulerTour(object):
    def __init__(self,E,root=0):
        """
        E: list of int (adjacency list)
        root: int
        """
        n=len(E)
        self.__V=list(range(n))
        self.__E=E
        self.__begin=[0]*n
        self.__end=[0]*n
        self.__k=0
        self.__dfs(root,-1)
        del self.__k

    def __dfs(self,v,p):
        self.__begin[v]=self.__k
        self.__k+=1
        for u in self.__E[v]:
            if u==p: continue
            self.__dfs(u,v)
            self.__k+=1
        self.__end[v]=self.__k

    @property
    def begin(self):
        return self.__begin

    @property
    def end(self):
        return self.__end

def resolve():
    # input
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
        E[b].append(a)
    # build
    tree=EulerTour(E)
    # calculate
    imos=[0]*(2*n)
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        imos[tree.begin[p]]+=x
        imos[tree.end[p]]-=x
    for i in range(2*n-1):
        imos[i+1]+=imos[i]
    # output
    print(*[imos[tree.begin[i]] for i in range(n)])
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class EulerTour(object):
    def __init__(self,E,root=0):
        """
        E: list of int (adjacency list)
        root: int
        """
        n=len(E)
        self.__V=list(range(n))
        self.__E=E
        self.__begin=[0]*n
        self.__end=[0]*n
        self.__tour=[0]*(2*n-1)
        self.__k=0
        self.__dfs(root,-1)
        del self.__k

    def __dfs(self,v,p):
        self.__begin[v]=self.__k
        self.__tour[self.__k]=v
        self.__k+=1
        for u in self.__E[v]:
            if u==p: continue
            self.__dfs(u,v)
            self.__tour[self.__k]=v
            self.__k+=1
        self.__end[v]=self.__k

    @property
    def begin(self):
        return self.__begin

    @property
    def end(self):
        return self.__end

    @property
    def tour(self):
        return self.__tour

def resolve():
    # input
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
        E[b].append(a)
    # build
    tree=EulerTour(E)
    # calculate
    imos=[0]*(2*n)
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        imos[tree.begin[p]]+=x
        imos[tree.end[p]]-=x
    for i in range(2*n-1):
        imos[i+1]+=imos[i]
    # output
    print(*[imos[tree.begin[i]] for i in range(n)])
resolve()

Submission status: Time Limit Exceeded

Solution code:
#D
from collections import deque
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0]*(n+1))
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=deque([1])
done=[0]*(n+1)
while h:
    a=h.popleft()
    for l in data[a]:
        if done[l]==0:
            counter[l]+=counter[a]
            h.append(l)
    done[a]=1
counter.popleft()
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
#D
from collections import deque
from heapq import heappush, heappop
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0]*(n+1))
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
done=[0]*(n+1)
while h:
    a=heappop(h)
    for i in range(len(data[a])):
        if done[data[a][i]]==1:
            continue
        counter[data[a][i]]+=counter[a]
        heappush(h,data[a][i])
    done[a]=1
counter.popleft()
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
#D
from collections import deque
from heapq import heappush, heappop
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0 for i in range(n+1)])
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
done=[]
while h:
    a=heappop(h)
    for i in range(len(data[a])):
        if data[a][i] in done:
            continue
        counter[data[a][i]]+=counter[a]
        heappush(h,data[a][i])
    done.append(a)
counter.popleft()
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
#D
from collections import deque
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0 for i in range(n+1)])
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=deque([1])
while h:
    a=h.popleft()
    for i in range(len(data[a])):
        counter[data[a][i]]+=counter[a]
        h.append(data[a][i])
        data[data[a][i]].remove(a)
counter.popleft()
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
#D
from collections import deque
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0 for i in range(n+1)])
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=deque([1])
while h:
    a=h.popleft()
    for i in range(len(data[a])):
        counter[data[a][i]]+=counter[a]
        h.append(data[a][i])
        data[data[a][i]].remove(a)
counter.popleft()
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
#D
from collections import deque
from heapq import heappush, heappop
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0 for i in range(n+1)])
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
while h:
    a=heappop(h)
    for i in range(len(data[a])):
        counter[data[a][i]]+=counter[a]
        heappush(h,data[a][i])
        data[data[a][i]].remove(a)
counter.popleft()
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n,q=[int(_) for _ in input().split()]
ki=[[] for _ in range(n)]
ans=[0]*n
 
def dfs(numQ):
    for child in ki[numQ]:
        ans[child]+=ans[numQ]
        dfs(child)
 
for i in range(n-1):
    a,b=[int(_) for _ in input().split()]
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
 
for i in range(q):
    p,x=[int(_) for _ in input().split()]
    ans[p-1]+=x
 
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

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

r = {}

for i in range(n-1):
    s, e = list(map(lambda x: int(x), input().split()))
    if s-1 in r.keys():
        r[s-1].append(e-1)
    else:
        r[s-1] = [e-1]
    if e-1 in r.keys():
        r[e-1].append(s-1)
    else:
        r[e-1] = [s-1]
        
queries = {}

for i in range(q):
    p, val = list(map(lambda x: int(x), input().split()))
    if p-1 in queries.keys():
        queries[p-1] += val
    else:
        queries[p-1] = val

ans = [0] * n    
checked = [0] * n

p = [[0, 0]]

while True:
    if len(p) > 0:
        point, value = p.pop()
        checked[point] = 1
    else:
        break
    
    if point in queries.keys():
        v = value + queries[point]
    else:
        v = value
    
    ans[point] = v
    for e in r[point]:
        if checked[e] == 0:
            p.append([e, v])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# def main():
#     N, Q = list(map(int, input().split()))
#     parents = [[] for i in range(N+1)]
#     ans = [0] * (N+1)

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

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

#     print(parents[1:])

#     for i in range(1, N+1):
#         for p in parents[i]:
#             ans[i] += ans[p]

#     print(*ans[1:])

import queue


def main():
    N, Q = map(int, input().split())
    tree = [[] for i in range(N+1)]
    ans = [0] * (N+1)
    visit = [False]*(N+1)

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

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

    q = queue.Queue()
    q.put(1)
    visit[1] = True

    while (not q.empty()):
        n = q.get()
        # print(tree[n])
        for i in tree[n]:
            if visit[i] is False:
                ans[i] += ans[n]
                # print(i, '+=', n)
                visit[i] = True
                q.put(i)

    print(*ans[1:])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# def main():
#     N, Q = list(map(int, input().split()))
#     parents = [[] for i in range(N+1)]
#     ans = [0] * (N+1)

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

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

#     print(parents[1:])

#     for i in range(1, N+1):
#         for p in parents[i]:
#             ans[i] += ans[p]

#     print(*ans[1:])

import queue


def main():
    N, Q = list(map(int, input().split()))
    tree = [[] for i in range(N+1)]
    ans = [0] * (N+1)
    visit = [False]*(N+1)

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

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

    q = queue.Queue()
    q.put(1)
    visit[1] = True

    while (not q.empty()):
        n = q.get()
        # print(tree[n])
        for i in tree[n]:
            if visit[i] is False:
                ans[i] += ans[n]
                # print(i, '+=', n)
                visit[i] = True
                q.put(i)

    print(*ans[1:])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

l=[list() for i in range(n)]
s=[0]*n

def dfs(t,p):
  for c in l[t]:
    if c==p:
      continue
    s[c]+=s[t]
    dfs(c,t)

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

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

dfs(0,n)

print(*s)
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

l=[list() for i in range(n)]
s=[0]*(n+1)

def dfs(t,p):
  for c in l[t]:
    if c==p:
      continue
    s[c]+=s[t]
    dfs(c,t)

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

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

dfs(0,n)

for i in range(n):
  print(s[i],' ',end="")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

l=[list() for i in range(n)]
s=[0]*(n+1)

def dfs(t,p):
  s[t]+=s[p]
  for c in l[t]:
    if c!=p:
      dfs(c,t)

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

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

dfs(0,n)

for i in range(n):
  print(s[i],' ',end="")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,q=[int(_) for _ in input().split()]
ki=[[] for _ in range(n)]
ans=[0]*n

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n,q=map(int,input().split())
ki=[[] for _ in range(n)]
ans=[0]*n

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n,q=map(int,input().split())
ki=[[] for _ in range(n)]
ans=[0]*n

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n,q=map(int,input().split())
ki=[[] for _ in range(n)]
ans=[0]*n

def dfs(numQ,parent):
    for child in ki[numQ]:
        if child!=parent:
            ans[child]+=ans[numQ]
            dfs(child,numQ)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
n,q=map(int,input().split())
ki=[[] for _ in range(n)]
ans=[0]*n

def dfs(numQ,parent):
    for child in ki[numQ]:
        if child!=parent:
            ans[child]+=ans[numQ]
            dfs(child,numQ)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
n,q=[int(i) for i in input().split()]
ki=[[] for _ in range(n)]
ans=[0]*n

def dfs(numQ,parent):
    for child in ki[numQ]:
        if child!=parent:
            ans[child]+=ans[numQ]
            dfs(child,numQ)

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

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

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

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

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

edge = [[] for _ in range(n)]

counter = [0] * n

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

for _ in range(q):
    a, b = [int(x) for x in input().split()]
    counter[a-1] += b

parent = [0]

for i in parent:
    for v in edge[i]:
        if v in parent:
            continue
        parent.append(v)
        counter[v] += counter[i]
        
print(" ".join(map(str, counter)))

Submission status: Time Limit Exceeded

Solution code:

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

edge = [[] for _ in range(n)]

counter = [0] * n

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

for _ in range(q):
    a, b = [int(x) for x in input().split()]
    counter[a-1] += b

parent = [0]

for i in parent:
    for v in edge[i]:
        if v in parent:
            continue
        parent.append(v)
        counter[v] += counter[i]
        
print(" ".join(map(str, counter)))

Submission status: Time Limit Exceeded

Solution code:

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

edge = [[] for _ in range(n)]

counter = [0] * n

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

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

parent = [0]
s_next = {0}

for i in parent:
    for v in edge[i]:
        # if v in parent:
        #     continue
        if v in s_next:
            continue
        s_next.add(v)
        parent.append(v)
        counter[v] += counter[i]
        
print(" ".join(map(str, counter)))