Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
from collections import deque
g = [[] for _ in range(n)]
fi = [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)
ls = [list(map(int,input().split())) for _ in range(q)]
def bfs(u):
    q = deque([u])
    d = [None]*n
    d[u] = 0
    while q:
        v = q.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                q.append(i)
    return d
ans = 0
for j in range(q):
    di = list(map(lambda x,y:x-y,bfs(0),bfs(ls[j][0]-1)))
    for k in range(len(di)):
        if di[k] == bfs(0)[ls[j][0]-1]:
            fi[k] += ls[j][1]                           
print(*fi)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

# input = sys.stdin.readline
# def main():

#---------------------------------------------------------

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

road = [[] for i in range(n)]
cnt  = [0 for i in range(n)]

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

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.popleft()
    for r in road[v]:
        if dist[r]!=-1:
            continue
        dist[r] = dist[v] + 1
        que.append(r)

for i in range(q):
    idx,v = map(int,input().split())
    for j in range(n):
        if j == idx-1:
            cnt[j] += v
        if dist[j] > dist[idx-1]:
            cnt[j] += v

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

# input = sys.stdin.readline
# def main():

#---------------------------------------------------------

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

road = [[] for i in range(n)]
cnt  = [0 for i in range(n)]

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

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.popleft()
    for i,r in enumerate(road[v]):
        if dist[r]!=-1:
            continue
        dist[r] = dist[v] + 1
        que.append(r)

for i in range(q):
    idx,v = map(int,input().split())
    for j in range(n):
        if j == idx-1:
            cnt[j] += v
        if dist[j] > dist[idx-1]:
            cnt[j] += v

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

# input = sys.stdin.readline
# def main():

#---------------------------------------------------------

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

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

road = [[] for i in range(n)]
cnt  = [0 for i in range(n)]

for i in tree:
    i[0]-=1
    i[1]-=1
    road[i[0]].append(i[1])
    road[i[1]].append(i[0])

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.popleft()
    for i,r in enumerate(road[v]):
        if dist[r]!=-1:
            continue
        dist[r] = dist[v] + 1
        que.append(r)

for i in ope:
    for j in range(n):
        if j == i[0]-1:
            cnt[j] += i[1]
        if dist[j] > dist[i[0]-1]:
            cnt[j] += i[1]

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 50

def dfs(current, node_vals, seen, to):
    for next, val in enumerate(to[current]):
        if val and not seen[next]:
            node_vals[next] += node_vals[current]
            seen[next] = 1
            dfs(next, node_vals, seen, to)


def run():
    N, Q = map(int, sysread().split())
    to = [[0] * (N+1) for _ in range(N+1)]
    for i in range(N-1):
        a,b = map(int,sysread().split())
        to[a][b] = 1
        to[b][a] = 1

    node_vals = [0] * (N+1)

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

    seen = [0] * (N+1)
    seen[1] = 1
    dfs(1, node_vals, seen, to)

    node_vals = [str(v) for v in node_vals]
    print(' '.join(node_vals[1:]))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal

INF = 1 << 50

def dfs(current, node_vals, seen, to):
    for next, val in enumerate(to[current]):
        if val and not seen[next]:
            node_vals[next] += node_vals[current]
            seen[next] = 1
            dfs(next, node_vals, seen, to)


def run():
    N, Q = map(int, sysread().split())
    to = [[0] * (N+1) for _ in range(N+1)]
    for i in range(N-1):
        a,b = map(int,sysread().split())
        to[a][b] = 1
        to[b][a] = 1

    node_vals = [0] * (N+1)

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

    seen = [0] * (N+1)
    seen[1] = 1
    dfs(1, node_vals, seen, to)

    node_vals = [str(v) for v in node_vals]
    print(' '.join(node_vals[1:]))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

# グラフの作成(無向グラフでは#を消す)
n, q = map(int, input().split())
graph = [deque([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b  = [int(x) for x in input().split()]
    graph[a].append(b)
    graph[b].append(a) # 無向グラフ
#print(graph)
#q_list = [list(map(int, input().split())) for _ in range(q)]
q_sum_list = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    q_sum_list[p-1] += x
#print(q_sum_list)
arrive_rireki = [-1] * (n + 1)

ans = [0]*n
score = [0]*n

# 深さ優先探索
def dfs(v):
    #arrive_rireki = [-1] * (n + 1)
    #print("check", graph_temp, arrive_rireki) #deepcopy の確認
    stack = [v]
    arrive_rireki[v] = 1
    while stack:
        #print("stack", stack)
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_rireki[w] < 0:
                arrive_rireki[w] = 1
                stack.append(w)
        else:
            stack.pop()
            #print("stack pop", v, stack)
            score[v-1] += q_sum_list[v-1]
            for i in range(len(stack)):
                score[v-1] += q_sum_list[stack[i]-1]
                #print(score, q_sum_list[stack[i]-1])
    return score

dfs(1)
#print(eda_list)
print(* score)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

# グラフの作成(無向グラフでは#を消す)
n, q = map(int, input().split())
graph = [deque([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b  = [int(x) for x in input().split()]
    graph[a].append(b)
    graph[b].append(a) # 無向グラフ
#print(graph)
#q_list = [list(map(int, input().split())) for _ in range(q)]
q_sum_list = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    q_sum_list[p-1] += x
#print(q_sum_list)
#arrive_rireki = [-1] * (N + 1)

ans = [0]*n
score = [0]*n

# 深さ優先探索
def dfs(v):
    arrive_rireki = [-1] * (n + 1)
    #print("check", graph_temp, arrive_rireki) #deepcopy の確認
    stack = [v]
    arrive_rireki[v] = 1
    while stack:
        #print("stack", stack)
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_rireki[w] < 0:
                arrive_rireki[w] = 1
                stack.append(w)
        else:
            stack.pop()
            #print("stack pop", v, stack)
            score[v-1] += q_sum_list[v-1]
            for i in range(len(stack)):
                score[v-1] += q_sum_list[stack[i]-1]
                #print(score, q_sum_list[stack[i]-1])
    return score

dfs(1)
#print(eda_list)
print(* score)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    ab[a-1].append(b)
    ab[b-1].append(a)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
yn=[0]*n
yn[0]=1
n1=1
queue=[]
queue2=[]
for i in range(n+10):
    for j in range(len(ab[n1-1])):
        n2=ab[n1-1][j]
        if yn[n2-1]==0:
            yn[n2-1]=1
            queue.append(n2)
    for j in range(len(queue)):
        ans[queue[0]-1]+=ans[n1-1]
        queue2.append(queue.pop(0))
    if len(queue)==0 and len(queue2)==0:
        break
    n1=queue2.pop(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    ab[a-1].append(b)
    ab[b-1].append(a)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
yn=[0]*n
yn[0]=1
n1=1
queue=[]
queue2=[]
for i in range(n+10):
    for j in range(len(ab[n1-1])):
        if yn[ab[n1-1][j]-1]==0:
            yn[ab[n1-1][j]-1]=1
            queue.append(ab[n1-1][j])
    for j in range(len(queue)):
        ans[queue[0]-1]+=ans[n1-1]
        queue2.append(queue[0])
        del(queue[0])
    if len(queue)==0 and len(queue2)==0:
        break
    n1=queue2.pop(-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

import networkx as nx

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

g = nx.Graph()
for i in range(n - 1):
    g.add_edge(*map(lambda x: int(x) - 1, input().split()))

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

d = deque([0])
b[0] = False

while len(d):
    p = d.popleft()
    for i in g.neighbors(p):
        if b[i]:
            a[i] += a[p]
            b[i] = False
            d.append(i)
print(*a)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

import networkx as nx

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

g = nx.Graph()
for i in range(n - 1):
    g.add_edge(*map(int, input().split()))
nx.set_node_attributes(g, name="a", values=0)
nx.set_node_attributes(g, name="b", values=True)

for i in range(q):
    p, x = map(int, input().split())
    g.nodes[p]["a"] += x

d = deque([1])
g.nodes[1]["b"] = False
while len(d):
    p = d.popleft()
    for i in g.neighbors(p):
        if g.nodes[i]["b"]:
            g.nodes[i]["a"] += g.nodes[p]["a"]
            g.nodes[i]["b"] = False
            d.append(i)
for i in range(1, n + 1):
    print(g.nodes[i]["a"], end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(220000)

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

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

bit = [0 for _ in range(n)]

def dfs(k):
    for i in l[k]:
        if bit[i]==0:
            bit[i] = 1
            value[i] += value[k]
            dfs(i)
bit[0] = 1
dfs(0)
print(*value)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(220000)

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

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

bit = [0 for _ in range(n)]
def dfs(k):
    bit[k] = 1
    for i in l[k]:
        if bit[i]==0:
            value[i] += value[k]
            dfs(i)

dfs(0)
print(*value)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

#kが木の頂点、vがそこからきた頂点
bit = [0 for _ in range(n)]
def dfs(k):
    bit[k] = 1
    for i in l[k]:
        if bit[i]==0:
            value[i] += value[k]
            dfs(i)

dfs(0)
print(*value)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N, Q = MI()
    #木
    tree = [[]]*N
    visit = [True]*N
    for i in range(N-1):
        a,b = MI()
        if len(tree[a-1]) == 0:
            tree[a-1] = [b-1]
            tree[b-1] = [a-1]
        else:
            tree[a-1].append(b-1)
            tree[b-1].append(a-1)
    #カウンター保存用、初期化
    counter = [0]* N
    score = [0]* N
    dq = deque([0])
    visit[0] = False
    for i in range(Q):
        p, x = MI()
        counter[p-1] += x
    score[0] = counter[0]
    while dq:
        temp = dq.pop()
        for num in tree[temp]:
            if visit[num]:
                score[num] = score[temp]+counter[num]
                dq.append(num)
                visit[num] = False
    score = [str(i) for i in score]
    print(" ".join(score))
    return None

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

N,Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #頂点を0indexに
  G[a].append(b);G[b].append(a)
#query = {}
ans = [0 for _ in range(N)]
for i in range(Q):
  p,x = map(int,input().split())
  p-=1
  ans[p] += x

def dfs(v,par): #vが今いる頂点、parが親。
  for u in G[v]:
    if u != par:
      ans[u] += ans[v]
      dfs(u,v)
dfs(0,-1)
print(*ans)

Submission status: Time Limit Exceeded

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

N,Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #頂点を0indexに
  G[a].append(b);G[b].append(a)
query = {}
for i in range(Q):
  p,x = map(int,input().split())
  p-=1
  if p not in query:
    query[p] = x
  else:
    query[p] += x
ans = [0 for _ in range(N)]
def dfs(v,par): #vが今いる頂点、parが親。
  if v in query:
    ans[v] += query[v]
  for u in G[v]:
    if u != par:
      ans[u] += ans[v]
      dfs(u,v)
dfs(0,-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

N,Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #頂点を0indexに
  G[a].append(b);G[b].append(a)
query = {}
for i in range(Q):
  p,x = map(int,input().split())
  p-=1
  if p not in query:
    query[p] = x
  else:
    query[p] += x
ans = [0 for _ in range(N)]
def dfs(v,par): #vが今いる頂点、parが親。
  if v in query:
    ans[v] += query[v]
  for u in G[v]:
    if u != par:
      ans[u] += ans[v]
      dfs(u,v)
dfs(0,-1)
print(*ans)

Submission status: Time Limit Exceeded

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

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

nodes = [0] * n
edges = {i: set() for i in range(n)}

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


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

seen = set()

def dfs(index):
    seen.add(index)
    for i in edges[index] - seen:
        nodes[i] += nodes[index]
        dfs(i)

for i in range(n):
    if i in seen:
        pass
    dfs(i)

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

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 i in range(n-1): # 行列の作成
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

costs = [0]*n # 答えの格納

for i in range(q): # コスト初期値の入力
    p, x = map(int, input().split())
    costs[p-1]+=x

visited = [0]*n # 訪問スタンプ

def dfs(idx):
    visited[idx]=1
    for i in g[idx]:
        if visited[i]==1:
            continue
        costs[i]+=costs[idx] # 累積和をとる
        dfs(i) # 再帰処理
    return

dfs(0)
print(*costs)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d
import sys
sys.setrecursionlimit(2*2*10**5)

def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    
def input():
    return sys.stdin.readline()[:-1]

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


#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())

    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())

    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*2*10**5)

def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    

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


#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())

    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())

    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*2*10**5)

def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    

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


a=[]
b=[]

p=[]
x=[]

#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())
    a.append(a0)
    b.append(b0)
    
    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())
    p.append(p0)
    x.append(x0)
    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")

Submission status: Time Limit Exceeded

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


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

add = [0]*N
for _ in [0]*M:
    p, x = map(int, input().split())
    p -= 1
    add[p] += x
counter = [0]*N

def dfs(v, p, x):
    counter[v] = x
    for u in G[v]:
        if u == p:
            continue
        dfs(u, v, x+add[u])


dfs(0, -1, add[0])

print(*counter)

Submission status: Time Limit Exceeded

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

n, q = (int(xi) for xi in input().split())

r = [[] for xi in range(n+1)]

for xi in range(n-1):
    a0, b0 = (int(xi) for xi in input().split())
    r[b0].append(a0)
    r[a0].append(b0)


p = [0 for xi in range(n+1)]
for xi in range(q):
    p0, x0 = (int(xi) for xi in input().split())
    p[p0] += x0


h = r[1][:]
for xi in r[1]:
    r[xi].remove(1)

for _ in range(n*2):
    tgt = h[0]
    h.extend(r[tgt])

    for yi in r[tgt]:
        r[yi].remove(tgt)

    h.remove(h[0])

    if len(h)==0: break


h = r[1][:]
for yi in r[1]:
    p[yi] += p[1]

for _ in range(n*2):
    tgt = h[0]
    h.extend(r[tgt])

    for yi in r[tgt]:
        p[yi] += p[tgt]

    h.remove(h[0])

    if len(h)==0: break

print(*p[1:])

Submission status: Time Limit Exceeded

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

n, q = (int(xi) for xi in input().split())

r = [[] for xi in range(n+1)]

for xi in range(n-1):
    a0, b0 = (int(xi) for xi in input().split())
    r[b0].append(a0)
    r[a0].append(b0)


p = [0 for xi in range(n+1)]
for xi in range(q):
    p0, x0 = (int(xi) for xi in input().split())
    p[p0] += x0


h = r[1][:]
for xi in r[1]:
    r[xi].remove(1)

for xi in range(n*2):
    tgt = h[0]
    h.extend(r[tgt])

    for yi in r[tgt]:
        r[yi].remove(tgt)

    h.remove(h[0])

    if len(h)==0: break


h = r[1][:]
for yi in r[1]:
    p[yi] += p[1]

for xi in range(n*2):
    tgt = h[0]
    h.extend(r[tgt])

    for yi in r[tgt]:
        p[yi] += p[tgt]

    h.remove(h[0])

    if len(h)==0: break

print(*p[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(xi) for xi in input().split())



r = [[] for xi in range(n+1)]

for xi in range(n-1):
    a0, b0 = (int(xi) for xi in input().split())
    r[b0].append(a0)
    r[a0].append(b0)


p = [0 for xi in range(n+1)]
for xi in range(q):
    p0, x0 = (int(xi) for xi in input().split())
    p[p0] += x0


h = r[1][:]
for xi in r[1]:
    r[xi].remove(1)

for xi in range(n*2):
    tgt = h[0]
    h.extend(r[tgt])

    for yi in r[tgt]:
        r[yi].remove(tgt)

    h.remove(h[0])

    if len(h)==0: break


h = r[1][:]
for yi in r[1]:
    p[yi] += p[1]

for xi in range(n*2):
    tgt = h[0]
    h.extend(r[tgt])

    for yi in r[tgt]:
        p[yi] += p[tgt]

    h.remove(h[0])

    if len(h)==0: break

print(*p[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(xi) for xi in input().split())



r = [[] for xi in range(n+1)]

for xi in range(n-1):
    a0, b0 = (int(xi) for xi in input().split())
    r[b0].append(a0)
    r[a0].append(b0)


p = [0 for xi in range(n+1)]
for xi in range(q):
    p0, x0 = (int(xi) for xi in input().split())
    p[p0] += x0


h = r[1][:]
for xi in r[1]:
    r[xi].remove(1)

for xi in range(n*100000):
    tgt = h[0]
    h.extend(r[tgt])

    for yi in r[tgt]:
        r[yi].remove(tgt)

    h.remove(h[0])

    if len(h)==0: break


h = r[1][:]
for yi in r[1]:
    p[yi] += p[1]

for xi in range(n*100000):
    tgt = h[0]
    h.extend(r[tgt])

    for yi in r[tgt]:
        p[yi] += p[tgt]

    h.remove(h[0])

    if len(h)==0: break

print(*p[1:])

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
add = [0 for i in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    add[p] += x
flag = [False for i in range(n + 1)]
check = [1]
while check:
    test = check.pop(0)
    flag[test] = True
    num_list = graph[test]
    for i in num_list:
        if flag[i] == True:
            pass
        else:
            add[i] += add[test]
            check.append(i)
for i in range(n):
    print(add[i + 1], end = " ")
print()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
add = [0 for i in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    add[p] += x
flag = [False for i in range(n + 1)]
check = [1]
while check:
    test = check.pop(0)
    flag[test] = True
    num_list = graph[test]
    for i in num_list:
        if flag[i] == True:
            pass
        else:
            add[i] += add[test]
            check.append(i)
for i in range(n):
    print(add[i + 1], end = " ")
print()

Submission status: Time Limit Exceeded

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

def dfs(number_list, memo_number):
    for number in number_list:
        if number in check_list:
            continue
        point = ans[memo_number]
        check_list.append(number)

        ans[number] += point
        dfs(graph[number], number)
    

n, q = map(int, input().split())
li_ab = [list(map(int, input().split())) for _ in range(n-1)]
li_px = [list(map(int, input().split())) for _ in range(q)]

graph = [[] for _ in range(n+10)]
for a,b in li_ab:
    graph[a].append(b)
    graph[b].append(a)

ans = [0 for _ in range(n+1)]
for p,x in li_px:
    ans[p] += x

check_list = [1]
point = 0
dfs(graph[1], 1)
    
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, Q = map(int, readline().split())

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

    child = [[] for _ in range(N)]
    child[0] = path[0]
    used = [False] * N
    used[0] = True
    que = deque(child[0])
    while que:
        x = que.popleft()
        used[x] = True
        for a in path[x]:
            if used[a]:
                continue
            else:
                child[x].append(a)
                que.append(a)

    counter = [0]*N
    for _ in range(Q):
        p, x = map(int, readline().split())
        que.append(p-1)
        counter[p-1] += x
        while que:
            a = que.popleft()
            for b in child[a]:
                counter[b] += x
                que.append(b)
    print(' '.join(map(str, counter)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(3 * 10 ** 5)

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

v = [[] for i in range(N)]  #もともとの木構造
for i in range(N-1):
  a, b = map(int, input().split())
  #vのindexが頂点番号、各indexの要素が繋がっている要素を表す
  v[a-1].append(b-1) #頂点idが1から始まっているため0にずらす
  v[b-1].append(a-1)

f = [0] * N #足し算するもの
for i in range(Q):
  p, x = map(int, input().split())
  f[p-1] += x  #それぞれの頂点に足すべき項目をあらかじめ追加して整理

#print(v)
#print(f)

#再帰関数dfsの定義:終了条件はd[y]==0となったら
def dfs(x, d, s): # x:計算する頂点, d:計算了否配列(まだ1完了0), s:頂点xの値
  for y in v[x]:  #頂点xとつながる各頂点yの計算
    if d[y]:      #計算される頂点yが計算未了の場合
      s += f[y]   #頂点xの値sにf[y](頂点yの値)を足す
      ans[y] = s  #頂点yの値をsに確定
      d[y] = 0    #計算済に変更
      dfs(y,d,s)  #頂点yの下層についても再帰的に計算
      s -= f[y]   #頂点yの下層の計算が終わったのでsを頂点xの値に戻す

ans = [0] * N
d = [1] * N #全部未計算にセット
d[0] = 0 #0が"根" 0は計算済(※f[0]が答えだから)
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans) #*と配列でスペース区切りで表示

Submission status: Time Limit Exceeded

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

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

v = [[] for i in range(N)]  #もともとの木構造
for i in range(N-1):
  a, b = map(int, input().split())
  #vのindexが頂点番号、各indexの要素が繋がっている要素を表す
  v[a-1].append(b-1) #頂点idが1から始まっているため0にずらす
  v[b-1].append(a-1)

f = [0] * N #足し算するもの
for i in range(Q):
  p, x = map(int, input().split())
  f[p-1] += x  #それぞれの頂点に足すべき項目をあらかじめ追加して整理

#print(v)
#print(f)

#再帰関数dfsの定義:終了条件はd[y]==0となったら
def dfs(x, d, s): # x:計算する頂点, d:計算了否配列(まだ1完了0), s:頂点xの値
  for y in v[x]:  #頂点xとつながる各頂点yの計算
    if d[y]:      #計算される頂点yが計算未了の場合
      s += f[y]   #頂点xの値sにf[y](頂点yの値)を足す
      ans[y] = s  #頂点yの値をsに確定
      d[y] = 0    #計算済に変更
      dfs(y,d,s)  #頂点yの下層についても再帰的に計算
      s -= f[y]   #頂点yの下層の計算が終わったのでsを頂点xの値に戻す

ans = [0] * N
d = [1] * N #全部未計算にセット
d[0] = 0 #0が"根" 0は計算済(※f[0]が答えだから)
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans) #*と配列でスペース区切りで表示

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self):
        self.num = None
        self.parent = None
        self.children = list()
        self.added = 0
        self.count = None
    def __repr__(self):
        return f'Node({self.num})'
    def calc_count(self):
        if self.parent is None:
            self.count = self.added
            return
        elif self.parent.count is None:
            self.parent.calc_count()
        self.count = self.parent.count + self.added

(n,q),*abpx = [list(map(int, s.split())) for s in open(0)]

ab,px = abpx[:n-1],abpx[n-1:]

from collections import defaultdict,deque
d = defaultdict(Node)

oab = ab
resid = []
ab = []
parents = {1}

while oab:
    for a,b in oab:
        if a in parents:
            ab.append((a,b))
            parents.add(b)
        elif b in parents:
            ab.append((b,a))
            parents.add(a)
        else:
            resid.append((a,b))
    oab = resid

for a,b in ab:
#     d[a].num = a
#     d[b].num = b
    d[b].parent = d[a]
    d[a].children.append(d[b])

for p,x in px:
    d[p].added += x

dq = deque([d[1]])

while dq:
    cur = dq.popleft()
    if cur.children:
        dq.extend(cur.children)
    cur.calc_count()

print(*list(d[i].count for i in range(1,n+1)))