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,copy
def LI(): return list(map(int,input().split()))
N,Q = LI()
ans = [0]*(N+1)
graph = [collections.deque() for _ in range(N+1)] #1_index
for _ in range(N-1):
    a,b = LI()
    graph[a].append(b)
    graph[b].append(a)
for _ in range(Q):
    p,x = LI()
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import collections,copy
def LI(): return list(map(int,input().split()))
N,Q = LI()
ans = [0]*(N+1)
graph = {i:collections.deque() for i in range(1,N+1)} #1_index
for _ in range(N-1):
    a,b = LI()
    graph[a].append(b)
    graph[b].append(a)
for _ in range(Q):
    p,x = LI()
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = [0]*(N+1) #1_indexed
graph = [[] for _ in range(N+1)] #1_indexed
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [-1]*(N+1) #1_indexed
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for g_NO in graph[s]:
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import collections
def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = [0]*(N+1) #1_index
graph = [collections.deque() for _ in range(N+1)] #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import collections
def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = [0]*(N+1) #1_index
graph = {i:collections.deque() for i in range(1,N+1)} #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [-1]*(N+1)  #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import collections,copy
def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = {i:0 for i in range(1,N+1)} #1_index
graph = {i:collections.deque() for i in range(1,N+1)} #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = {i:-1 for i in range(1,N+1)} #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*[a for a in ans.values()])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N-1)]
B = [list(map(int,input().split())) for i in range(Q)]

from collections import defaultdict,deque

G = defaultdict(list)

for i in range(N-1):
    G[A[i][0]].append(A[i][1])
    G[A[i][1]].append(A[i][0])

H = defaultdict(int)

for i in range(Q):
    H[B[i][0]] += B[i][1]

#bfs

r = 0
P = [0]*(N+1)  #ポイント

D = [0]+[-1]*(N)
D[1] = 1
P[1] = H[1]
q = deque([1])

while q:
    n = q.pop()
    for d in G[n]:
        if D[d] != -1:
            continue
        else:
            D[d] = 1
            q.appendleft(d)
            P[d] = P[n] + H[d]
del P[0]

print(*P)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N-1)]
B = [list(map(int,input().split())) for i in range(Q)]

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

for i in range(N-1):
    G[A[i][0]].append(A[i][1])
    G[A[i][1]].append(A[i][0])

from collections import defaultdict,deque

H = defaultdict(int)

for i in range(Q):
    H[B[i][0]] += B[i][1]

#bfs

r = 0
P = [0]*(N+1)  #ポイント

D = [0]+[-1]*(N)
D[1] = 1
P[1] = H[1]
q = deque([1])

while q:
    n = q.pop()
    for d in G[n]:
        if D[d] != -1:
            continue
        else:
            D[d] = 1
            q.appendleft(d)
            P[d] = P[n] + H[d]
del P[0]

print(*P)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500*500)

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

graph = [[] for _ in range(N+1)]
value = [0] * (N + 1)

for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

for que in process:
    value[que[0]] += que[1]

def dfs(s, parent, add):
    value[s] += add
    for x in graph[s]:
        if x == parent:
            continue
        dfs(x, s, value[s])

dfs(1, 0, 0)

ans =  ' '.join(map(str, value[1:]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
N,Q = map(int,input().split())
tree = [[] for _ in range(N)]
cnt = [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())
    cnt[p-1] += x
sys.setrecursionlimit(10 ** 6)
def dfs(cur,parent):
    li = tree[cur]
    for chi in li:
        if chi == parent:
            continue
        cnt[chi] += cnt[cur]
        dfs(chi,cur)
dfs(0,-1)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
N,Q = map(int,input().split())
tree = [[] for _ in range(N)]
cnt = [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())
    cnt[p-1] += x
sys.setrecursionlimit(10 ** 6)
def dfs(cur,parent):
    li = tree[cur]
    for chi in li:
        if chi == parent:
            continue
        cnt[chi] += cnt[cur]
        dfs(chi,cur)
dfs(0,-1)
print(" ".join(map(str,cnt)))

Submission status: Time Limit Exceeded

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

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

def dfs(cur, par):
    for chi in tree[cur]:
        if chi == par:
            continue
        cnt[chi] += cnt[cur]
        dfs(chi, cur)
dfs(0, -1)
print(*cnt)

Submission status: Time Limit Exceeded

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

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

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

ans = [0] * N

def dfs(v, pv, w):
    w += weight[v]
    ans[v] = w
    for nv in edge[v]:
        if nv == pv: continue
        dfs(nv, v, w)

dfs(0, -1, 0)
print(*ans, sep=" ")

Submission status: Time Limit Exceeded

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

def main():
    N, Q = list(map(int, input().split()))
    graph = [[] for i in range(N)]
    # 最初にroot pointを定めて:
    # graph構造に大して点を与える...
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    
    points = [0] * N
    for _ in range(Q):
        p, x = list(map(int, input().split()))
        points[p-1] += x
    
    visited = [False] * N
    
    nodes = graph[0]
    visited[0] = True
    
    
    def dfs(old_node, node):
        if visited[node]:
            return
        points[node] += points[old_node]
        visited[node] = True
        nodes = graph[node]
        [dfs(node, _node) for _node in nodes if not visited[_node]]

    for _node in nodes:
        dfs(0, _node)
    
    print(*points)
    
main()

Submission status: Time Limit Exceeded

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

N, Q = list(map(int, input().split()))
graph = [[] for i in range(N)]
# 最初にroot pointを定めて:
# graph構造に大して点を与える...
for i in range(N-1):
    a, b = list(map(int, input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

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

visited = [False] * N

nodes = graph[0]
visited[0] = True


def dfs(old_node, node):
    if visited[node]:
        return
    points[node] += points[old_node]
    visited[node] = True
    nodes = graph[node]
    for _node in nodes:
        dfs(node, _node)
for _node in nodes:
    dfs(0, _node)

print(*points)

Submission status: Time Limit Exceeded

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

N, Q = list(map(int, input().split()))
graph = [[] for i in range(N)]
# 最初にroot pointを定めて:
# graph構造に大して点を与える...
for i in range(N-1):
    a, b = list(map(int, input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

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

visited = [False] * N
tot_points = [0] * N
tot_points[0] = points[0]

nodes = graph[0]
visited[0] = True


def dfs(old_node, node):
    if visited[node]:
        return
    tot_points[node] = tot_points[old_node] + points[node]
    visited[node] = True
    nodes = graph[node]
    for _node in nodes:
        dfs(node, _node)
for _node in nodes:
    dfs(0, _node)

for x in tot_points:
    print(x, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
import queue
sys.setrecursionlimit(1000000000)

N, Q = list(map(int, input().split()))
graph = [[] for i in range(N)]
# 最初にroot pointを定めて:
# graph構造に大して点を与える...
for i in range(N-1):
    a, b = list(map(int, input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

points = np.zeros(N, dtype=int)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    points[p-1] += x

visited = np.zeros(N, dtype=bool)
tot_points = np.zeros(N, dtype=int)
tot_points[0] = points[0]
top_nodes = np.full(N, -1, dtype=int)

nodes = graph[0]
top_nodes[nodes] = 0
old_node = 0
visited[0] = True


def dfs(old_node, node):
    if visited[node]:
        return
    tot_points[node] = tot_points[old_node] + points[node]
    visited[node] = True
    nodes = queue.deque(graph[node])
    for _node in nodes:
        dfs(node, _node)
for _node in nodes:
    dfs(0, _node)
    

for x in tot_points.tolist():
    print(x, end=" ")

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)

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

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

        c[next] += c[now]
        dfs(next, now)

dfs(0)
print(*c)

Submission status: Time Limit Exceeded

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

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

import sys
sys.setrecursionlimit(10**8)
def dfs(v):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            ans[u] += ans[v]
            visited[u]=True
            dfs(u)
    return

visited = [False]*N
visited[0]= True
dfs(0)
print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n,q=map(int,input().split())
graph=[[] for _ in range(n+1)]
ab=[list(map(int,input().split())) for _ in range(n-1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
px=[list(map(int,input().split())) for _ in range(q)]
seen=[0]*(n+1)
ans=[0]*(n+1)
for p,x in px:
    ans[p]+=x
def dfs(i):
    seen[i]=1
    for li in graph[i]:
        if seen[li]==0:
            ans[li]+=ans[i]
            dfs(li)
dfs(1)
print(' '.join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
#input=sys.stdin.readline

def dfs(u,s):
  visited[u]=True
  ans_list[u]=s+dic_score[u]
  
  for v in tree_list[u]:
    if not visited[v]:
      dfs(v,ans_list[u])    
  return s

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

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

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

ans_list=[0]*(N+1)
visited=[False]*(N+1)
dfs(1,0)

print(*ans_list[1:])

Submission status: Time Limit Exceeded

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

def dfs(u,par):
  ans_list[u]+=ans_list[par]
  visited[u]=True
  
  for v in tree_list[u]:
    if not visited[v]:
      dfs(v,u)      
  return

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

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

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

visited=[False]*(N+1)
dfs(1,0)

print(*ans_list[1:])

Submission status: Time Limit Exceeded

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

def dfs(u,s):
  ans_list[u]=s+list_score[u]
  for v in tree_list[u]:
    if ans_list[v]==-1:
      dfs(v,ans_list[u])
  return s

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

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

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

ans_list=[-1]*(N+1)
dfs(1,0)

print(*ans_list[1:])

Submission status: Time Limit Exceeded

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

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

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

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

seen=["False" for _ in range(N)]
def solve(n):
  seen[n]="True"
  for i in graph[n]:
    if seen[i]=="False":
      ans[i]+=ans[n]
      solve(i)
  return

solve(0)
print(*ans)

Submission status: Time Limit Exceeded

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

def dfs(v,s):
  #global dic_score
  #global tree_list
  #global ans_list
  visited[v]=True
  score=s
  if v in dic_score:
    score+=dic_score[v]
    
  ans_list[v]+=score
  for vv in tree_list[v]:
    if not visited[vv]:
      dfs(vv,score)
    
  return s

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

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

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

ans_list=[0]*(N+1)
visited=[False]*(N+1)
dfs(1,0)

print(*ans_list[1:])

Submission status: Time Limit Exceeded

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

def dfs(i, source, count=0):
    node[i]+=count
    for next_node in to[i]:
        if next_node == source: continue 
        dfs(next_node, i, node[i])
dfs(0, -1, 0)

print(' '.join(list(map(str, node))))

Submission status: Time Limit Exceeded

Solution code:
# import sys
from collections import deque
# sys.setrecursionlimit(10 ** 5)

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

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

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

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

done = [True for _ in range(N)]
stack = deque([])
done[0] = False
for e in edge[0]:
    stack.append([e, 0])
while stack:
    s = stack.pop()
    if done[s[0]]:
        done[s[0]] = False
        counter[s[0]] += counter[s[1]]
        for n in edge[s[0]]:
            stack.append([n, s[0]])

[print(c, end=" ") for c in counter]

Submission status: Time Limit Exceeded

Solution code:
# import sys
from collections import deque
# sys.setrecursionlimit(10 ** 5)

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

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

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

def dfs():
    global counter
    done = [True for _ in range(N)]
    stack = deque([])
    done[0] = False
    for e in edge[0]:
        stack.append([e, 0])
    while stack:
        s = stack.pop()
        if done[s[0]]:
            done[s[0]] = False
            counter[s[0]] += counter[s[1]]
            for n in edge[s[0]]:
                stack.append([n, s[0]])
                
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p - 1] += x
dfs()

[print(c, end=" ") for c in counter]

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)

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

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

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

def dfs():
    global counter
    done = [True for _ in range(N)]
    stack = deque([])
    done[0] = False
    for e in edge[0]:
        stack.append([e, 0])
    while stack:
        s = stack.pop()
        if done[s[0]]:
            done[s[0]] = False
            counter[s[0]] += counter[s[1]]
            for n in edge[s[0]]:
                stack.append([n, s[0]])
                
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p - 1] += x
dfs()

[print(c, end=" ") for c in counter]

Submission status: Time Limit Exceeded

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

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

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

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

def dfs():
    global counter
    done = [True for _ in range(N)]
    stack = deque([])
    done[0] = False
    for e in edge[0]:
        stack.append([e, 0])
    while stack:
        s = stack.pop()
        if done[s[0]]:
            done[s[0]] = False
            counter[s[0]] += counter[s[1]]
            for n in edge[s[0]]:
                stack.append([n, s[0]])
                
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p - 1] += x
dfs()

[print(c, end=" ") for c in counter]

Submission status: Time Limit Exceeded

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

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

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

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

def dfs(p, x):
    global counter
    flag = False
    done = [True for _ in range(N)]
    done[0] = False
    if p == 0:
        counter[0] += x
        flag = True
    stack = deque(edge[0])
    while stack:
        s = stack.popleft()
        if done[s]:
            if s == p:
                flag = True
                while stack:
                    stack.pop()
            if flag:
                counter[s] += x
            done[s] = False
            for n in edge[s]:
                stack.append(n)
                
for _ in range(Q):
    p, x = map(int, input().split())
    dfs(p - 1, x)

[print(c, end=" ") for c in counter]

Submission status: Time Limit Exceeded

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

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

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

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

def dfs(p, x):
    global counter
    flag = False
    done = [True for _ in range(N)]
    done[0] = False
    if p == 0:
        counter[0] += x
        flag = True
    stack = deque(edge[0])
    while stack:
        s = stack.pop()
        if done[s]:
            if s == p:
                flag = True
                while stack:
                    stack.pop()
            if flag:
                counter[s] += x
            done[s] = False
            for n in edge[s]:
                stack.append(n)
                
for _ in range(Q):
    p, x = map(int, input().split())
    dfs(p - 1, x)

[print(c, end=" ") for c in counter]

Submission status: Time Limit Exceeded

Solution code:
N, Q=map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
tree=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

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

ans=[0]*N
def dfs(start, pre, preval):
  addval=preval+add[start]
  ans[start]+=addval
  for next_node in tree[start]:
    if next_node==pre:
      continue
    dfs(next_node, start,addval)
dfs(0,-1,0)  
for a in ans:
  print(a, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().rstrip().split())
to = [[] for _ in range(N)]
ans = [0] * N
def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)
for _ in range(N-1):
    a, b = map(int, input().rstrip().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    p, x = map(int, input().rstrip().split())
    p -= 1
    ans[p] += x
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())
to = [[] for _ in range(N)]
ans = [0] * N
def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)

Submission status: Time Limit Exceeded

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

def main():
    #入力
    N, Q = (int(_) for _ in input().split())
    edge = [[int(_) for _ in input().split()] for __ in range(N-1)]
    query = [[int(_) for _ in input().split()] for __ in range(Q)]

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

    cc = [0] * (N+1)
    seen = [False] * (N+1)

    for p, x in query:
        cc[p] += x

    def dfs(x):
        for p in tree[x]:
            if seen[p] == False:
                seen[p] = True
                cc[p] += cc[x]
                dfs(p)
        return

    seen[1] = True
    dfs(1)

    print(*cc[1:])

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000000)
def main():
    #入力
    N, Q = (int(_) for _ in input().split())
    edge = [[int(_) for _ in input().split()] for __ in range(N-1)]
    query = [[int(_) for _ in input().split()] for __ in range(Q)]

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

    cc = [0] * (N+1)
    seen = [False] * (N+1)

    for p, x in query:
        cc[p] += x

    def dfs(x):
        for p in tree[x]:
            if seen[p] == False:
                seen[p] = True
                cc[p] += cc[x]
                dfs(p)
        return

    seen[1] = True
    dfs(1)

    print(*cc[1:])
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
edges = [[] for _ in range(n)]

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

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


def dfs(v, parent):
    for v2 in edges[v]:
        if v2 == parent:
            continue
        count[v2] += count[v]
        dfs(v2, v)


dfs(0, None)
print(*count)

Submission status: Time Limit Exceeded

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

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


def dfs(v, parent):
    for v2 in edges[v]:
        if v2 == parent:
            continue
        counts[v2] += counts[v]
        dfs(v2, v)


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