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:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]

'''
def main():
'''
n, q = map(int, input().split())
G = defaultdict(list)
for i in range(n - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
#print(G)

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

def dfs(v, pv):
    for nv in G[v]:
        if nv != pv:
            P[nv] += P[v]
            dfs(nv, v)


dfs(0, 0)
print(*P)


'''
if __name__ == '__main__':
    main()
'''

Submission status: Time Limit Exceeded

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

def dfs(v, pv):
    global P

    for nv in G[v]:
        if nv != pv:
            P[nv] += P[v]
            dfs(nv, v)

n,q = map(int, input().split())
G = [[] for _ in range(n)]              # adjacent list
for i in range(n-1):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

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


dfs(0, 0)
print(*P)

Submission status: Time Limit Exceeded

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

def dfs(v, pv):
    # global P

    for nv in G[v]:
        if nv != pv:
            P[nv] += P[v]
            dfs(nv, v)

n,q = map(int, input().split())
G = [[] for _ in range(n)]              # adjacent list
for i in range(n-1):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

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


dfs(0, 0)
print(*P)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
ABPX = [tuple(map(int,input().split())) for i in range(q+n-1)]
AB = iter(ABPX[:n-1])
PX = iter(ABPX[n-1:])

tree = dict()
for a,b in AB:
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

opr = {i+1:0 for i in range(n)}
for p,x in PX:
  opr[p] += x

stack = [1]
parent = [0] * (n+1)
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x]: continue
    parent[y] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

print(*ans)

Submission status: Time Limit Exceeded

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

tree = dict()
for i in range(n-1):
  a,b = map(int, input().split())
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

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

stack = [1]
parent = [0] * (n+1)
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x]: continue
    parent[y] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
 
tree = dict()
for i in range(n-1):
  a,b = map(int, input().split())
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

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

stack = [1]
parent = [0] * (n+1)
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x]: continue
    parent[y] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

print(*ans)

Submission status: Time Limit Exceeded

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

tree = dict()
for i in range(n-1):
  a,b = map(int, input().split())
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

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

stack = [1]
parent = [0]*n
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x-1]: continue
    parent[y-1] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def dfs(i):
    q = deque()
    q.append(i)
    p = i
    d[i] = 1
    while True:
        if len(q) == 0:
            print(" ".join(map(str, c)))
            return
        s = 0
        p = q[len(q) - 1]
        for j in G[p]:
            if d[j] == 0:
                c[j] += c[p]
                q.append(j)
                s = 1
                p = j
                d[j] = 1
                break
        if s == 0:
            q.pop()

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
#input = sys.stdin.readline

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
P = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    P[p-1] += x
ans = [-1] * N
#print(G)
#print(P)

def dfs(v, p):
    ans[v] = P[v] + p
    for vi in G[v]:
        if ans[vi] != -1:
            continue
        dfs(vi, ans[v])
dfs(0, 0)

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

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
P = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    P[p-1] += x
ans = [-1] * N
#print(G)
#print(P)
def dfs(v, p):
    ans[v] = P[v] + p
    for vi in G[v]:
        if ans[vi] != -1:
            continue
        dfs(vi, ans[v])

dfs(0, 0)

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

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
P = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    P[p-1] += x
ans = [-1] * N
#print(G)
#print(P)
def dfs(v, p):
    ans[v] = P[v] + p
    for vi in G[v]:
        if ans[vi] != -1:
            continue
        dfs(vi, ans[v])

dfs(0, 0)
#print(ans)
print(' '.join(map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

Solution code:
# D
import sys
sys.setrecursionlimit(10**9)                    #再帰の深さブースト

def now2next(root, pastnode, edge, score, ans):
    edge[root].remove(pastnode)
    childlist = edge[root]
    if childlist:
        ans[root-1] += score[root]
        for child in childlist:
            ans[child-1] += ans[root-1]
            now2next(child, root, edge, score, ans)
    else:
        ans[root-1] += score[root]
    
n,q = map(int, input().split())
edge = [[] for i in range(n+1)]
score = [0 for i in range(n+1)]
ans = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
edge[1].append(0)
for req in range(q):
    reqnode, x = map(int, input().split())
    score[reqnode] += x
now2next(1, 0, edge, score, ans)
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
# D
import sys
sys.setrecursionlimit(10**9)                    #再帰の深さブースト

def now2next(root, pastnode, edge, union):
    edge[root].remove(pastnode)
    childlist = edge[root]
    if childlist:
        for child in childlist:
            union[root].extend(now2next(child, root, edge, union))
        return union[root]
    else:
        return [root]
    
n,q = map(int, input().split())
edge = [[] for i in range(n+1)]
union = [[i] for i in range(n+1)]
ans = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
edge[1].append(0)
now2next(1, 0, edge, union)
for req in range(q):
    reqnode, x = map(int, input().split())
    for num in union[reqnode]:
        ans[num-1] += x
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
# D
import sys
sys.setrecursionlimit(10**9)                    #再帰の深さブースト

def now2next(root, pastnode, edge, union):
    edge[root].remove(pastnode)
    childlist = edge[root]
    if childlist:
        for child in childlist:
            union[root].extend(now2next(child, root, edge, union))
        return union[root]
    else:
        return union[root]
    
n,q = map(int, input().split())
edge = [[] for i in range(n+1)]
union = [[i] for i in range(n+1)]
ans = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
edge[1].append(0)
now2next(1, 0, edge, union)
for req in range(q):
    reqnode, x = map(int, input().split())
    for num in union[reqnode]:
        ans[num-1] += x
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
def o():return map(int,input().split())
n,q=o()
a=[[]for i in range(n)]
x=[0]*n
for i in range(n-1):
  u,v=o()
  a[u-1]+=[v-1]
  a[v-1]+=[u-1]
for i in range(q):
  u,v=o()
  x[u-1]+=v
p=[0]
m=[0]
while p:
  r=p.pop()
  m+=[r]
  for i in a[r]:
    if not(i in m):
      p+=[i]
      x[i]+=x[r]
print(*x)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
import sys
sys.setrecursionlimit(10**7)
tree = [[] for _ in range(N)]

for i in range(N-1):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    tree[y].append(x)
    tree[x].append(y)
ans = [0]*N
for i in range(Q):
    x,y = map(int,input().split())
    ans[x-1] += y


def dfs(cur,par):
    for chl in tree[cur]:
        if chl == par: #これで木の流れの逆行を防ぐ
            continue
        ans[chl] += ans[cur]
        dfs(chl,cur)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,q=map(int,input().split())
    a=[[None for i in range(n)]for i in range(n)]
    for i in range(n-1):
        x,y=map(int,input().split())
        a[x-1][y-1]=True
        a[y-1][x-1]=True
    cnt=[0]*n
    for i in range(q):
        x,y=map(int,input().split())
        cnt[x-1]+=y
    
    from collections import deque 
    d=deque()
    d.append(0)
    completed=[False]*n
    
    while d:
        now=d.popleft()
        completed[now]=True
        for x,aa in enumerate(a[now]):
            if aa==True and completed[x]==False:
                cnt[x]+=cnt[now]
                d.append(x)
    print(*cnt)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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


N, Q = map(int, input().split())
to = [[] for i in range(N)]  # 隣接リスト
c = [0] * N

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

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    c[p] += x
dfs(0)
print(*c)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
to = [[] for i in range(N)]  # 隣接リスト
c = [0] * N

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


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


for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    c[p] += x
dfs(0)
print(*c)

Submission status: Time Limit Exceeded

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

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

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

  def dfs(v,pv):      
    for nv in G[v]:
      if nv != pv:
        P[nv] += P[v]
        dfs(nv,v)

  dfs(0,0)
  print(*P)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

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

P = [0]*n
for i in range(q):
  p,x = map(int,input().split())
  P[p-1] += x
     
def dfs(v,pv):      
  for nv in G[v]:
    if nv != pv:
      P[nv] += P[v]
      dfs(nv,v)
        
dfs(0,0)
print(*P)

Submission status: Time Limit Exceeded

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

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

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

def dfs(v,p):
  ans[v] = p + P[v]
  visited[v] = 1
  
  for nv in G[v]:
    if visited[nv] == 0:
      dfs(nv,ans[v])
        
dfs(0,0)
print(*ans)

Submission status: Time Limit Exceeded

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

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

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

def dfs(v,p):
  ans[v] = p + P[v]
  visited[v] = 1
  
  for nv in dic[v]:
    if visited[nv] == 0:
      dfs(nv,ans[v])
        
dfs(0,0)
print(*ans)

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(n-1)]
px = [tuple(map(int,input().split())) for i in range(q)]

es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)


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

# DFS for tree
def dfs(v=0, parent=-1):# どこからきたかの情報を入れとく
    for to in es[v]:
        if to == parent: continue # 今回はcontinue

        if visited[to]: continue

        ans[to] += ans[v]
        dfs(to, v)


for p, x in px:
    ans[p-1] += x

dfs(0)

print(*ans, sep=' ')

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(n-1)]
px = [tuple(map(int,input().split())) for i in range(q)]

es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)


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

# DFS for tree
def dfs(v, parent = -1):# どこからきたかの情報を入れとく
    for to in es[v]:
        if to == parent: continue # 今回はcontinue

        # if visited[to]: continue # 今回はcontinueしない方がいいな

        ans[to] += ans[v]
        dfs(to, v)


for p, x in px:
    ans[p-1] += x

dfs(0)

print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
import sys
sys.setrecursionlimit(10**8)
T=[[] for i in range(N)]
S=[0 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)
for i in range(Q):
    p,x=map(int,input().split())
    S[p-1]+=x
seen=[False for i in range(N)]
def dps(i,seen,S,T):
    seen[i]=True
    for v in T[i]:
        if not seen[v]:
            S[v]+=S[i]
            dps(v,seen,S,T)
dps(0,seen,S,T)
print(*S)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
import sys
sys.setrecursionlimit(10**8)
T=[[] for i in range(N)]
S=[0 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)
for i in range(Q):
    p,x=map(int,input().split())
    S[p-1]+=x
seen=[False for i in range(N)]
def dps(i):
    seen[i]=True
    for v in T[i]:
        if not seen[v]:
            S[v]+=S[i]
            dps(v)
dps(0)
print(*S)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
import sys
sys.setrecursionlimit(10**8)
T=[set() for i in range(N)]
S=[0 for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    T[a-1].add(b-1)
    T[b-1].add(a-1)
for i in range(0,Q):
    p,x=map(int,input().split())
    S[p-1]+=x
seen=[False for i in range(N)]
def dps(i):
    seen[i]=True
    for v in T[i]:
        if seen[v]:
            continue
        else:
            S[v]+=S[i]
            dps(v)
dps(0)
print(*S)

Submission status: Time Limit Exceeded

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

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

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

def dfs(pre,now,point):
    for to in G[now]:
        if to==pre:continue
        ans[to]+=point
        dfs(now,to,ans[to])
dfs(-1,0,ans[0])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    vertex_num, operation_num = map(int, sys.stdin.buffer.readline().split())
    tree = [[] for _ in range(vertex_num)]
    for _ in range(vertex_num - 1):
        a, b = map(lambda x: int(x) - 1, sys.stdin.buffer.readline().split())
        tree[a].append(b)
        tree[b].append(a)
    answer = [[0, True] for _ in range(vertex_num)]
    answer[0][1] = False
    for _ in range(operation_num):
        p, x = map(int, sys.stdin.buffer.readline().split())
        answer[p - 1][0] += x
    q = [0]
    while not q == []:
        now = q.pop(0)
        for next_vertex in tree[now]:
            if answer[next_vertex][1]:
                answer[next_vertex][1] = False
                answer[next_vertex][0] += answer[now][0]
                q.append(next_vertex)
    print(" ".join(map(lambda x: str(x[0]), answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    vertex_num, operation_num = map(int, input().split())
    tree = [[] for _ in range(vertex_num)]
    for _ in range(vertex_num - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        tree[a].append(b)
        tree[b].append(a)
    answer = [[0, True] for _ in range(vertex_num)]
    answer[0][1] = False
    for _ in range(operation_num):
        p, x = map(int, input().split())
        answer[p - 1][0] += x
    q = [0]
    while not q == []:
        now = q.pop(0)
        for next_vertex in tree[now]:
            if answer[next_vertex][1]:
                answer[next_vertex][1] = False
                answer[next_vertex][0] += answer[now][0]
                q.append(next_vertex)
    print(" ".join(map(lambda x: str(x[0]), answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

tree = defaultdict(list)
cnt = defaultdict(int)
lines = sys.stdin.readlines()
lines = [line.strip() for line in lines]
N, Q = int(lines[0].split(' ')[0]), int(lines[0].split(' ')[1])

for i in xrange(1, N):
    a, b = int(lines[i].split(' ')[0]), int(lines[i].split(' ')[1])
    tree[a].append(b)
    tree[b].append(a)
    
for i in xrange(N, N+Q):
    p, x = int(lines[i].split(' ')[0]), int(lines[i].split(' ')[1])
    cnt[p] += x

ans = [0 for _ in range(N)]
visited = set()
def dfs(node, val):
    visited.add(node)
    val += cnt[node]
    ans[node-1] += val
    if not node in tree:
        return
    nexts = tree[node]
    for nx_node in nexts:
        if nx_node not in visited:
            dfs(nx_node, val)
dfs(1, 0)
ans = [str(val) for val in ans]
print ' '.join(ans)

Submission status: Time Limit Exceeded

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

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

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

ans = [0] * n

def dfs(count, v, parent):
    count += counter[v]
    ans[v] = count
    for child in connect[v]:
        if child != parent:
            dfs(count, child, v)

dfs(0, 0, -1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

#グラフの状態を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for a,b in ab:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    return G

from collections import deque
def bfs(G,v,p):
    #(G,v,p)=(グラフ(木の情報),探索中の頂点,vの親)
    #vの子の頂点を決めて、vをpに移す
    q=deque()
    q.append((v,p))
    while q:
        V,P=q.popleft()
        for new_v in G[V]:
            #new_vが頂点の時はアウト
            if new_v==P:continue
            ans[new_v]+=ans[V]
            q.append((new_v,V))

G=Graph(ab)
ans=[0]*n
#print(G)

for p,x in px:
    ans[p-1]+=x
bfs(G,0,-1)
print(*ans)

Submission status: Time Limit Exceeded

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


def dfs(cur, par):
    for child in edge[cur]:
        if child == par:
            continue
        counter[child] += counter[cur]
        dfs(child, cur)


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)]
counter = [0] * N

edge = [[] for _ in range(N)]
for i in range(N-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

for i in range(Q):
    p = px[i][0] - 1
    x = px[i][1]
    counter[p] += x


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

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
A = [LIST() for i in range(N-1)]
P = [LIST() for i in range(Q)]

tree = defaultdict(list)

# ノードの重み

cnt = [0] * N

# tree 隣接リスト
for i in range(N-1):
    tree[A[i][0]-1].append(A[i][1]-1)
    tree[A[i][1]-1].append(A[i][0]-1)

for i in range(Q):
    cnt[P[i][0]-1] += P[i][1]

ans = [0] * N
q = deque([])
# 始点
q.append(0)
# 各頂点を見たかどうかのフラグ
checked = [0] * N
checked[0] = 1

while q:
    v = q.pop()
    checked[v] = 1
    for u in tree[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        q.append(u)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
A = [LIST() for i in range(N-1)]
P = [LIST() for i in range(Q)]

tree = defaultdict(list)

# ノードの重み

cnt = [0] * N

# tree 隣接リスト
for i in range(N-1):
    tree[A[i][0]-1].append(A[i][1]-1)
    tree[A[i][1]-1].append(A[i][0]-1)

for i in range(Q):
    cnt[P[i][0]-1] += P[i][1]

ans = [0] * N
q = deque([])
# 始点
q.append(0)
# 各頂点を見たかどうかのフラグ
checked = [0] * N

while q:
    v = q.pop()
    checked[v] = 1
    for u in tree[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        q.append(u)
print(*cnt)

Submission status: Time Limit Exceeded

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

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

def dfs(now, prev = -1):
    for next in G[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next, now)

dfs(0)
print(*point)

Submission status: Time Limit Exceeded

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

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

def dfs(now, prev = -1):
    for next in G[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next, now)

dfs(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

tree = defaultdict(list)
for a, b in ab:
	tree[a-1].append(b-1)
	tree[b-1].append(a-1)

dic = defaultdict(int)

for p, x in px:
	dic[p-1] += x

ans = [0]*N

checked = [0]*N
checked[0] = 1

q = deque([])
q.append(0)

while q:
	n = q.popleft()
	ans[n] += dic[n]
	for node in tree[n]:
		if checked[node]:
			continue
		ans[node] += ans[n]
		checked[node] = 1
		q.append(node)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy
import bisect


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

#X = str(input()).split()
#a = [int(x) for x in input().split()]


sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())
G = [[] for i in range(N)]
Ope = [0]*N

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

val = [0]*N

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

dfs(0, 0, 0)

val = map(str, val)
vall = ' '.join(val)

print(vall)

Submission status: Time Limit Exceeded

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

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

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


def dfs(n, pre):
    for nxt in G[n]:
        if nxt == pre:
            continue
        val[nxt] += val[n]
        dfs(nxt, n)


dfs(0, 0)

answer = ' '.join(map(str, val[:]))
print(answer)