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 collections
 
n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1): #木グラフの隣接リストを作成
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
for _ in range(q): #各頂点についてcount[v]を計算
 v,val=map(int,input().split())
 cnt[v]+=val
q=collections.deque()
q.append(1) #DFSのスタックによる実装、まずスタックに始点1を積む
while q:
 v=q.pop()
 for u in g[v]:
   cnt[u]+=cnt[v]
   q.append(u) #スタックに子ノードuを積む
print(*cnt[1:]) #各頂点のcountが答えとなる

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(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
point = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x
done = [-1]*N
def dfs(cur, fr, p):
    done[cur] = p
    for nex in G[cur]:
        if nex == fr: continue
        dfs(nex, cur, p+point[nex])
dfs(0, -1, point[0])
ans = []
for i in range(N):
    ans.append(done[i])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
tree = [[] for _ in range(n)]
point = [0] * n
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

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

q = [[0, 0]]
while True:
    if len(q) == 0:
        break
    child, parent = q.pop(0)
    p = point[child]
    for i in tree[child]:
        if i == parent:
            continue
        point[i] += p
        q.append([i, child])

print(*point)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
tree = [[] for _ in range(n)]
point = [0] * n
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

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

q = [[0, 0]]
while True:
    if len(q) == 0:
        break
    child, parent = q.pop(0)
    for i in tree[child]:
        if i == parent:
            continue
        point[i] += point[child]
        q.append([i, child])

print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N,Q = (int(x) for x in input().rstrip('\n').split())
r = {1:0}
d = [[x] for x in range(N+1)]
for _ in range(N-1):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a in r:
    r[b] = a
    d[b].extend(d[a])
  else:
    r[a] = b
    d[a].extend(d[b])
res = [0]*(N)
for _ in range(Q):
  p,s = (int(x) for x in input().rstrip('\n').split())
  ad = [x for x in range(1,N+1) if p in d[x]]
  for x in ad:
    res[x-1] += s
print(*res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N,Q = (int(x) for x in input().rstrip('\n').split())
r = {1:0}
d = {x:[x] for x in range(1,N+1)}
for _ in range(N-1):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a in r:
    r[b] = a
    d[b].extend(d[a])
  else:
    r[a] = b
    d[a].extend(d[b])
res = [0]*(N)
for _ in range(Q):
  p,s = (int(x) for x in input().rstrip('\n').split())
  ad = [x for x in range(1,N+1) if p in d[x]]
  for x in ad:
    res[x-1] += s
print(*res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N,Q = (int(x) for x in input().rstrip('\n').split())
r = {1:0}
d = {x:{x} for x in range(1,N+1)}
for _ in range(N-1):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a in r:
    r[b] = a
    d[b] = d[b] | d[a]
  else:
    r[a] = b
    d[a] = d[a] | d[b]
res = [0]*(N)
for _ in range(Q):
  p,s = (int(x) for x in input().rstrip('\n').split())
  ad = [x for x in range(1,N+1) if p in d[x]]
  for x in ad:
    res[x-1] += s
print(*res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N,Q = (int(x) for x in input().rstrip('\n').split())
r = {1:0}
d = {x:{x} for x in range(1,N+1)}
for _ in range(N-1):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a in r:
    r[b] = a
    d[b] = d[b] | d[a]
  else:
    r[a] = b
    d[a] = d[a] | d[b]
res = [0]*(N)
for _ in range(Q):
  p,s = (int(x) for x in input().rstrip('\n').split())
  ad = [x for x in range(1,N+1) if p in d[x]]
  for x in ad:
    res[x-1] += s
print(*res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def readinput():
    n,q=map(int,input().split())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    for i in range(n-1):
        a,b=map(int,input().split())
        nList[a].append(b)
        nList[b].append(a)
    px=[]
    for i in range(q):
        p,x=map(int,input().split())
        px.append((p,x))
    return n,q,nList,px

childList=[]
def setDepth(s,nList):
    global depth
    global color
    global childList

    for next in nList[s]:
        if color[next]==WHITE:
            childList[s].append(next)
            depth[next]=depth[s]+1
            color[next]=GRAY
            childList[s].extend(setDepth(next,nList))
    color[s]=BLACK
    return childList[s]

def addCounter(s,x,nList):
    global depth
    global counter

    for next in nList[s]:
        if depth[next]>depth[s]:
            counter[next]+=x
            addCounter(next,x,nList)
    

WHITE=0
GRAY=1
BLACK=2
color=[]
depth=[]
counter=[]
def main(n,q,nList,px):
    global depth
    global color
    global counter
    global childList

    color=[WHITE]*(n+1)
    depth=[0]*(n+1)
    counter=[0]*(n+1)
    for _ in range(n+1):
        childList.append([])

    #print(nList)

    depth[1]=0
    color[1]=GRAY
    setDepth(1,nList)
    #print(depth)
    #print(childList)

    for p,x in px:
        # counter[p]+=x
        # addCounter(p,x,nList)
        counter[p]+=x
        for c in childList[p]:
            counter[c]+=x

    return counter[1:]

if __name__=='__main__':
    n,q,nList,px=readinput()
    ans=main(n,q,nList,px)
    print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))
PX = (tuple(map(int, input().split())) for _ in range(q))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for p,x in PX:
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

n,q = map(int,readline().split())
AB = (tuple(int(x) for x in readline().split()) for _ in range(n-1))
PX = (tuple(int(x) for x in readline().split()) for _ in range(q))
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for p,x in PX:
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))
PX = (tuple(map(int, input().split())) for _ in range(q))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for p,x in PX:
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for _ in range(q):
  p,x = map(int, input().split())
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]

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())
  Counter[p] += x

P = [-1 for _ in range(n+1)]  

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
Tree = {i:[] for i in range(1, n+1)}
Counter = {i:0 for i in range(1, n+1)}

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())
  Counter[p] += x

P = [-1 for _ in range(n+1)]  

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter.values())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = map(int, input().split())
pathes = []
for _ in range(N-1):
    a, b = map(int, input().split())
    pathes.append((a, b))
childs = [[] for i in range(N+1)]
for a, b in pathes:
    childs[a].append(b)
    childs[b].append(a)
cnt = [0]*(N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x
closed = []
nodes = deque()
nodes.append(1)
while len(nodes) != 0:
    node = nodes.popleft()
    closed.append(node)
    for c in childs[node]:
        if c in closed:
            continue
        nodes.append(c)
        cnt[c] += cnt[node]
for i in range(1, N+1):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 14, 2020 09:41:55 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from collections import defaultdict
from sys import stdin
input = stdin.readline


def main():
  # input
  N, Q = list(map(int, input().split()))

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

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

  # solve
  ans = [0]*(N+1)
  S = [1] # Stack
  visited = set()
  temp = PX[1]

  while len(S):
    now = S[-1]
    visited.add(now)

    for next_ in G[now]:
      if next_ not in visited:
        S.append(next_)
        temp += PX[next_]
        break
    else:
      S.pop()
      ans[now] = temp
      temp -= PX[now]

  print(*ans[1:], sep=' ')


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 14, 2020 09:41:55 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from collections import defaultdict
from sys import stdin
input = stdin.readline


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

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

  ans = [0]*(N+1)
  S = [1]
  visited = set()
  temp = PX[1]

  while len(S):
    now = S[-1]
    visited.add(now)
    is_leaf = True
    for next_ in G[now]:
      if next_ not in visited:
        S.append(next_)
        temp += PX[next_]
        is_leaf = False
        break
    # else:
    if is_leaf:
      S.pop()
      ans[now] = temp
      temp -= PX[now]

  print(*ans[1:], sep=' ')


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 14, 2020 09:41:55 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from collections import defaultdict
from sys import stdin
input = stdin.readline


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

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

  ans = [0]*(N+1)
  S = [1]
  is_visited = set()
  temp = PX[1]

  while len(S):
    now = S[-1]
    is_visited.add(now)
    for next_ in G[now]:
      if next_ not in is_visited:
        S.append(next_)
        temp += PX[next_]
        break
    else:
      S.pop()
      ans[now] = temp
      temp -= PX[now]

  print(*ans[1:], sep=' ')


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n, q = map(int, input().split())
edges = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
def dfs(now, prev):
    for next in edges[now]:
        if next == prev:
            continue
        counter[next] += counter[now]
        dfs(next, now)
dfs(0, -1)
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n, q = map(int, input().split())
edges = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
def dfs(now, prev):
    for next in edges[now]:
        if next == prev:
            continue
        counter[next] += counter[now]
        dfs(next, now)
dfs(0, -1)
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(4100000)

def dfs(node):
  global ts
  visited[node-1] = True
  first_order[node-1] = ts
  ts += 1
  
  for next_node in tree[node]:
    if visited[next_node-1]:
      continue
    dfs(next_node)
  
  last_order[node-1] = ts
  ts += 1

N, Q = map(int, input().split())
tree = dd(list)
visited = [False] * N
first_order = [0] * N
last_order = [0] * N
ts = 0
counter = [0] * N
operation = []
for _ in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b) 
  tree[b].append(a) 
for _ in range(Q):
  operation.append(tuple(map(int, input().split())))

dfs(1)
for p, x in operation:
  for i in range(N):
    if first_order[p-1] <= first_order[i-1] and last_order[i-1] <= last_order[p-1]:
      counter[i-1] += x
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(4100000)

def dfs(node):
  global ts
  visited[node-1] = True
  first_order[node-1] = ts
  ts += 1
  
  for next_node in tree[node]:
    if visited[next_node-1]:
      continue
    dfs(next_node)
  
  last_order[node-1] = ts
  ts += 1

N, Q = map(int, input().split())
tree = dd(list)
operation = []
counter = [0] * N
for _ in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b) 
  tree[b].append(a) 
for _ in range(Q):
  operation.append(tuple(map(int, input().split())))

for p, x in operation:
  visited = [False] * N
  first_order = [0] * N
  last_order = [0] * N
  ts = 0
  dfs(1)
  for i in range(N):
    if first_order[p-1] <= first_order[i-1] and last_order[i-1] <= last_order[p-1]:
      counter[i-1] += x
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.buffer.readline
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

N,Q=map(int,input().split())
G=[[] for i 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)
point=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    point[p-1]+=x
dfs(G,0,-1)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline


class Graph:
    def __init__(self, n, dictated=False, edge=[]):
        self.n = n
        self.dictated = dictated
        self.conj = [set() for _ in range(self.n)]
        self.visit = set()
        self.second_visit = set()
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self,x,y):
        self.conj[x].add(y)
        if self.dictated == False:
            self.conj[y].add(x)

    def dfs2(self, info, p=0, goal=None, use_visit=False):
        """
        引継ぎが必要な場合に使う再帰関数版の dfs
        :param info: 各頂点の付加情報。[x]*N のリストで与えられる
        :param p: スタート地点
        :param goal: ゴール地点
        :param use_visit: 前回の探索結果を保持するかどうか
        :return: 引継ぎ後の info
        """
        if use_visit==False:
            self.visit = set()
            self.second_visit = set()

        def rec(p, past_p, t):
            self.visit.add(p)
            for q in self.conj[p]:
                if q == past_p:
                    # 逆流した際の処理
                    continue
                if q in self.second_visit:
                    # 帰り道に訪れた際の処理
                    continue
                if q in self.visit:
                    continue
                if q == goal:
                    # ゴール時の処理
                    # return t+1
                    continue
                # p から q への引継ぎ処理
                info[q] += info[p]

                rec(q, p, t+1)
            self.second_visit.add(p)
            # 帰り際の処置（壊した道を元に戻す等)
            # visit.discard(p)
            return info

        past_p = None
        t = 0
        return rec(p, past_p, t)


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False)

for _ in range(M):
    x, y = map(int, input().split())
    x -= 1                                    # デクリメントが不要な場合は消す
    y -= 1
    graph.add_edge(x,y)

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

print(*graph.dfs2(info, p=0))

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

Submission status: Time Limit Exceeded

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

ans = px
queue = [(0, 0)]

while len(queue) > 0:
    prev, a = queue.pop(0)
    for c in ab[a]:
        if c != prev:
            ans[c] += ans[a]
            queue.append((a, c))

print(*ans)

Submission status: Time Limit Exceeded

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


def DFS(num,parent,point):
    D[num]=point+Q[num]
    for i in M[num]:
        if i!=parent:
            DFS(i,num,D[num])


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

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

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

D=[0]*n
DFS(0,-1,0)
print(*D)

Submission status: Time Limit Exceeded

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


def DFS(num,parent,point):
    D[num]=point+Q[num]
    for i in M[num]:
        if i!=parent:
            DFS(i,num,D[num])


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

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

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

D=[0]*(n+1)
DFS(1,0,0)
print(*D[1:])

Submission status: Time Limit Exceeded

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


def DFS(num,point):
    D[num]=point+Q[num]
    color[num]="gray"
    for i in M[num]:
        if color[i]=="white":
            DFS(i,D[num])
    color[num]="black"


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

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

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

color=["white" for _ in range(n+1)]
D=[0]*(n+1)

DFS(1,0)
print(*D[1:])

Submission status: Time Limit Exceeded

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

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

from collections import defaultdict
counter = defaultdict(int)
for _ in range(Q):
  p,x = map(int,input().split())
  p -= 1
  counter[p] += x

weight = [-1] * N
def dfs(node, wei):
  weight[node] = wei

  for nei in adj[node]:
    if weight[nei] == -1:
      dfs(nei, wei+counter[nei])

dfs(0, counter[0])
print(" ".join(map(str,weight)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = map(int, input().split())
root = [[] for i in range(N)]
ans = [0]*N

for i in range(N-1):
  a, b = map(int, input().split())
  root[a-1].append(b)
  
for i in range(Q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
now = 1
visit = deque([1])
while len(visit) < N:
  if root[now-1] == []:
    now = visit[visit.index(now)-1]
  else:
    go = root[now-1][0]
    root[now-1].pop(0)
    visit.append(go)
    ans[go-1] += ans[now-1]
    now = go
    
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7


n, q = map(int, input().split())
g = [[] for _ in range(n)]
val = [0] * n

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

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

seen = [False] * n
def dfs(v):
    seen[v] = True
    for nv in g[v]:
        if seen[nv]:
            continue
        val[nv] += val[v]
        dfs(nv)

dfs(0)
print(*val)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp

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

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

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,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  que=[0]
  done=[0]*n  
  done[0]=1
  while(que):
    now=que.pop(0)

    for i in l[now]:
      if done[i]==0:
        done[i]=1
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp

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

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

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,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  que=[0]
  done=[0]*n  
  while(que):
    now=que.pop(0)
    done[now]=1
    for i in l[now]:
      if done[i]==0:
        que.append(i)
        ans[i]+=ans[now]
        
dfs()
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp

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

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

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,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  
  que=[0]
  done=[0]*n  

  while(que):
    now=que.pop(0)
    if done[now]==1:
      continue
    done[now]=1

    for i in l[now]:
      if done[i]==0:
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp

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

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

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,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  val=0
  que=[[0,val]]
  done=[0]*n  

  while(que):
    now,val=que.pop(0)
    if done[now]==1:
      continue
    val+=ans[now]
    ans[now]=val
    done[now]=1

    for i in l[now]:
      if done[i]==0:
        que.append([i,val])

dfs()
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp

n,q=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
pul=[0]*n
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,x=map(int,input().split())
  pul[p-1]+=x


ans=[0]*n
def dfs():
  val=0
  que=[[0,val]]
  done=[0]*n  

  while(que):
    now,val=que.pop(0)
    if done[now]==1:
      continue
    val+=pul[now]
    ans[now]=val
    done[now]=1

    for i in l[now]:
      if done[i]==0:
        que.append([i,val])

dfs()
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,q = inpl()
g = [[]for i in range(n)]
c = [0 for i in range(n)]
seen = [False] * n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for i in range(q):
    a,b = inpl()
    c[a-1] += b
def dfs(node):
    for v in g[node]:
        if seen[v]:
            continue
        c[v] += c[node]
        seen[v] = True
        dfs(v) 
seen[0] = True
dfs(0)
print(*c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, q = map(int, input().split())
g = [[] for i in range(n)]
k = []
for i 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):
  a,b = map(int, input().split())
  k.append([a-1,b])
m = [-1]*n
m[0] = 0
q = deque()
q.append(0)
while len(q):
  d = q.popleft()
  for i in g[d]:
    if m[i] == -1:
      m[i] = m[d]+1
      q.append(i)
kyori = [[] for i in range(max(m)+1)]
for i,j in enumerate(m):
  kyori[j].append(i)
ans= [0]*n
for i,j in k:
  t = m[i]
  ans[i]+=j
  for r in range(t+1,len(kyori)):
    for z in kyori[r]:
      ans[z]+=j
print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, q = map(int, input().split())
g = [[] for i in range(n)]
k = []
for i 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):
  a,b = map(int, input().split())
  k.append([a-1,b])
m = [-1]*n
m[0] = 0
q = deque()
q.append(0)
while len(q):
  d = q.popleft()
  for i in g[d]:
    if m[i] == -1:
      m[i] = m[d]+1
      q.append(i)
ans = [0]*n
for i,j in k:
  t = m[i]
  for x,y in enumerate(m):
    if i == x or t < y:
      ans[x]+=j
print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
tree=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)
cnt=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

def DFS(v,p_v):
    for next_v in tree[v]:
        if next_v==p_v:
            continue
        cnt[next_v]+=cnt[v]
        DFS(next_v,v)

DFS(0,-1)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,q=map(int,input().split())
tree=[[0]*n for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    tree[a-1][b-1]=1
    tree[b-1][a-1]=1
cnt=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x
colors=["white" for _ in range(n)]

stack=deque([0])
colors[0]="gray"
while stack:
    current=stack.pop()
    for i in range(n):
        if tree[current][i]==1 and colors[i]=="white":
            stack.append(i)
            colors[i]="gray"
        if tree[current][i]==1 and colors[i]!="black":
            cnt[i]+=cnt[current]
    colors[current]="black"
print(*cnt)