Problem:


Score : 400 points

Problem Statement

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

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

Now, the following Q operations will be performed:

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

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

Constraints

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

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

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

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

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

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

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

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20



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


Sample output:
100 110 111 110

Submission status: Time Limit Exceeded

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

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

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


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


dfs(0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q = map(int,input().split())
tree = {i : [] for i in range(n)}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  tree[b].append(a)
score = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  score[p-1] += x
  
def dfs(parent,node,s):
  for n in tree[node]:
    if n == parent:
      continue
    score[n] += score[node]
    dfs(node,n,s)

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

Submission status: Time Limit Exceeded

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

n,q = map(int,input().split())
tree = {i : [] for i in range(n)}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  tree[b].append(a)
score = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  score[p-1] += x
  
def dfs(parent,node,s):
  for n in tree[node]:
    if n == parent:
      continue
    score[n] += score[node]
    dfs(node,n,s)

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

Submission status: Time Limit Exceeded

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

n,q = map(int,input().split())
tree = {i : [] for i in range(n)}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  tree[b].append(a)
score = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  score[p-1] += x
  
def dfs(parent,node,s):
  s += score[node]
  score[node] = s
  for n in tree[node]:
    if n == parent:
      continue
    dfs(node,n,s)

dfs(-1,0,0)
  
print(' '.join(map(str,score)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import deque


class TreeNode:
    def __init__(self, tree_id: int):
        self.parent = None
        self.id = tree_id
        self.val = 0

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

tree_list = [TreeNode(i) for i in range(n)]

connect = {}
for i in range(n-1):
    (a,b) = [int(i) - 1 for i in input().rstrip().split(" ")]
    if a not in connect:
        connect[a] = {}
    if b not in connect:
        connect[b] = {}

    connect[a][b] = True
    connect[b][a] = True

for i in range(q):
    (t,x) = [int(i) for i in input().rstrip().split(" ")]
    tree_list[t-1].val += x

q = deque([tree_list[0]])

while q:
    current = q.pop()
    for i in connect[current.id]:
        if current.parent is not None:
            if i == current.parent.id:
                continue
        tree_list[i].parent = current
        tree_list[i].val += current.val
        q.append(tree_list[i])

print(" ".join([str(i.val) for i in tree_list]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from queue import Queue


class TreeNode:
    def __init__(self, tree_id: int):
        self.parent = None
        self.id = tree_id
        self.val = 0

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

tree_list = [TreeNode(i) for i in range(n)]

connect = {}
for i in range(n-1):
    (a,b) = [int(i) - 1 for i in input().rstrip().split(" ")]
    if a not in connect:
        connect[a] = {}
    if b not in connect:
        connect[b] = {}

    connect[a][b] = True
    connect[b][a] = True

for i in range(q):
    (t,x) = [int(i) for i in input().rstrip().split(" ")]
    tree_list[t-1].val += x

q = Queue()
q.put(tree_list[0])

while not q.empty():
    current = q.get()
    for i in connect[current.id]:
        if current.parent is not None:
            if i == current.parent.id:
                continue
        tree_list[i].parent = current
        tree_list[i].val += current.val
        q.put(tree_list[i])

print(" ".join([str(i.val) for i in tree_list]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from queue import Queue


class TreeNode:
    def __init__(self, tree_id: int):
        self.parent = None
        self.id = tree_id
        self.val = 0

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

tree_list = [TreeNode(i) for i in range(n)]

connect = {}
for i in range(n-1):
    (a,b) = [int(i) - 1 for i in input().rstrip().split(" ")]
    if a not in connect:
        connect[a] = {}
    if b not in connect:
        connect[b] = {}

    connect[a][b] = True
    connect[b][a] = True

for i in range(q):
    (t,x) = [int(i) for i in input().rstrip().split(" ")]
    tree_list[t-1].val += x

q = [tree_list[0]]

while not len(q) == 0:
    current = q.pop()
    for i in connect[current.id]:
        if current.parent is not None:
            if i == current.parent.id:
                continue
        tree_list[i].parent = current
        tree_list[i].val += current.val
        q.append(tree_list[i])

print(" ".join([str(i.val) for i in tree_list]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from queue import Queue


class TreeNode:
    def __init__(self, tree_id: int):
        self.parent = None
        self.items = []
        self.id = tree_id
        self.val = 0

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

tree_list = [TreeNode(i) for i in range(n)]

connect = {}
for i in range(n-1):
    (a,b) = [int(i) - 1 for i in input().rstrip().split(" ")]
    if a not in connect:
        connect[a] = {}
    if b not in connect:
        connect[b] = {}

    connect[a][b] = True
    connect[b][a] = True

for i in range(q):
    (t,x) = [int(i) for i in input().rstrip().split(" ")]
    tree_list[t-1].val += x

q = [tree_list[0]]

while not len(q) == 0:
    current = q.pop()
    for i in connect[current.id]:
        if current.parent is not None:
            if i == current.parent.id:
                continue
        tree_list[i].parent = current
        current.items.append(tree_list[i])
        tree_list[i].val += current.val
        q.append(tree_list[i])

print(" ".join([str(i.val) for i in tree_list]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from queue import Queue


class TreeNode:
    def __init__(self, tree_id: int):
        self.parent = None
        self.items = []
        self.id = tree_id
        self.val = 0

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

tree_list = [TreeNode(i) for i in range(n)]

connect = {}
for i in range(n-1):
    (a,b) = [int(i) - 1 for i in input().rstrip().split(" ")]
    if a not in connect:
        connect[a] = {}
    if b not in connect:
        connect[b] = {}

    connect[a][b] = True
    connect[b][a] = True

for i in range(q):
    (t,x) = [int(i) for i in input().rstrip().split(" ")]
    tree_list[t-1].val += x

q = Queue()
q.put(tree_list[0])

while not q.empty():
    current = q.get()
    for i in connect[current.id]:
        if current.parent is not None:
            if i == current.parent.id:
                continue
        tree_list[i].parent = current
        current.items.append(tree_list[i])
        tree_list[i].val += current.val
        q.put(tree_list[i])

print(" ".join([str(i.val) for i in tree_list]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    ai, bi = map(int, input().split())
    g[ai - 1].append(bi - 1)
    g[bi - 1].append(ai - 1)

ans = [0] * n
for _ in range(q):
    pi, xi = map(int, input().split())
    ans[pi - 1] += xi


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


dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
sys.setrecursionlimit(200010)

def input():
    return sys.stdin.readline()[:-1]

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

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

    def dfs(visited,distance,graph,ima):
        for e in graph[ima]:
            if visited[e] == 0:
                visited[e] = 1
                distance[e] += distance[ima]
                dfs(visited,distance,graph,e)
    V[0] = 1
    dfs(V,D,G,0)

    print(*D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

g2 = [set() for _ in range(N+1)]
p = [0]*(N+1)
vs = set()
stack = [1]
dfs_vs = []
vs.add(1)
while stack:
    v = stack.pop()
    dfs_vs.append(v)
    for u in G[v]:
        if u in vs:
            continue
        g2[v].add(u)
        p[u] = v
        stack.append(u)
        vs.add(u)

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

#print(d)
#print(p)

for v in dfs_vs:
    d[v] += d[p[v]]

print(*d[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
PX = [tuple(map(int,input().split())) for i in range(Q)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
ex = [0] * N
for p,x in PX:
    ex[p-1] += x

ans = [None] * N
def dfs(v=0,c=0,p=-1):
    c += ex[v]
    ans[v] = c
    for to in es[v]:
        if to==p: continue
        dfs(to,c,v)

dfs()
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
n,q=map(int,input().split())
l=[[] for i in range(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)
px=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  px[p-1]+=x
ans=[0]*n
def dsf(index,u):
  ans[index]=ans[u]+px[index]
  for i in l[index]:
    if i==u:continue
    dsf(i,index)
dsf(0,-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
n,q=map(int,input().split())
l=[[] for i in range(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)
ans=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
def dsf(index,u):
  for i in l[index]:
    if i==u:continue
    ans[i]+=ans[index]
    dsf(i,index)
dsf(0,-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
n,q=map(int,input().split())
l=[[] for i in range(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)
ans=[0 for i in range(n)]
for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
def dsf(index,u):
  for i in l[index]:
    if i==u:continue
    ans[i]+=ans[index]
    dsf(i,index)
dsf(0,-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
n,q=map(int,input().split())
l=[[] for i in range(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)
ans=[0 for i in range(n)]
for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
def dsf(index,u):
  for i in l[index]:
    if i==u:continue
    ans[i]+=ans[index]
    dsf(i,index)
dsf(0,-1)
print(' '.join(str(j) for j in ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

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

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

dfs(0)
print(*point)

Submission status: Time Limit Exceeded

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

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

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

dfs(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q=map(int,input().split())
c=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  c[a].append(b)
  c[b].append(a)
px=[0]*n
for I in range(q):
    p,x=map(int,input().split())
    px[p-1]+=x 
ans=[0]*n
def dfs(g,h=-1):
  ans[g]=ans[h]+px[g]
  for i in c[g]:
    if i==h:continue
    dfs(i,g)
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q=map(int,input().split())
c=[[] for _ in range(n)]
ab=[list(map(int,input().split())) for _ in range(n-1)]
PX=[list(map(int,input().split())) for _ in range(q)]
for a,b in ab:
  a-=1
  b-=1
  c[a].append(b)
  c[b].append(a)
px=[0]*n
for p,x in PX:
    px[p-1]+=x 
ans=[0]*n
def dfs(g,h=-1):
  ans[g]=ans[h]+px[g]
  for i in c[g]:
    if i==h:
      continue
    dfs(i,g)
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q=map(int,input().split())
c=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  c[a].append(b)
  c[b].append(a)
px=[0]*n
for I in range(q):
    p,x=map(int,input().split())
    px[p-1]+=x 
ans=[0]*n
def dfs(g,h=-1):
  ans[g]=ans[h]+px[g]
  for i in c[g]:
    if i==h:
      continue
    dfs(i,g)
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
p=[0 for i in range(n+1)]
edge=[[] for i in range(n+1)]
que=deque([])
que.append(1)
visited=[False for i in range(n+1)]
visited[0]=True
for i,j in ab:
  edge[i].append(j)
  edge[j].append(i)
for i in range(q):
  a,b=map(int,input().split())
  p[a]+=b

while que:
  v=que.pop()
  visited[v]=True
  for nv in edge[v]:
    if visited[nv]==True:
      continue
    p[nv]+=p[v]
    que.append(nv)
p.pop(0)
print(*p)

Submission status: Time Limit Exceeded

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

n,q = map(int,input().split())
pointTree = [0 for i in range(n)]
tree = [[] for i in range(n)]
p = [0 for i in range(n)]


def solve(now,prev):
    for node in tree[now]:
        if node == prev:
            continue
        pointTree[node] += pointTree[now]
        solve(node,now)


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):
    tp,x = map(int,input().split())
    pointTree[tp-1] += x
    
solve(0,-1)
s = ''
for i in range(n):
    s += str(pointTree[i])+' '
print(s[:-1])

Submission status: Time Limit Exceeded

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

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

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

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

# DFS
def DFS(n):
    if n == 0:
        return
    oya = o[n]
    ans[n] = point[n] + ans[oya]
    while len(tree[n]) > 0:
        k = tree[n].pop()
        if k != oya and k != 0:
            o[k] = n
            return DFS(k)
    return DFS(oya)

# main
DFS(1)

# output
print(" ".join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
ab = [[int(i) for i in input().split()] for j in range(N-1)]
px = [[int(i) for i in input().split()] for j in range(Q)]

#tree
tree = []
for _ in range(N+1):
    tree.append([[],[]])
tree[1][1] = 0
for i in range(N-1):
    tree[ab[i][0]][0].append(ab[i][1])
    tree[ab[i][1]][0].append(ab[i][0])

#table
point = []
for _ in range(N+1):
    point.append([0,0])
for i in range(Q):
    point[px[i][0]][0] += px[i][1]

# DFS
def DFS(n):
    if n == 0:
        return
    oya = tree[n][1]
    point[n][1] = point[n][0] + point[oya][1]
    while len(tree[n][0]) > 0:
        k = tree[n][0].pop()
        if k != oya:
            tree[k][1] = n
            return DFS(k)
    return DFS(oya)

# main
DFS(1)

# output
for i in range(1,N+1):
    print(point[i][1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,q=map(int,input().split())
A=[[] for i in range(n)] #繋がっている頂点
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  A[a].append(b)
  A[b].append(a)
B=[0]*n #コスト
for i in range(q):
  p,q=map(int,input().split())
  p=p-1
  B[p]=B[p]+q
#BFSの時間じゃああああ!!!!!!
C=deque([0])
D=[] #visited枠
while len(C)>0:
  c=C[0]
  C.popleft()
  D.append(c)
  for i in range(len(A[c])):
    if A[c][i] not in D:
      C.append(A[c][i])
      B[A[c][i]]+=B[c]
for i in range(n):
  print(B[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    from collections import defaultdict
    MOD = 10**9+7

    N,Q = LMIIS()
    edge = defaultdict(list)
    E = defaultdict(list)

    X = [0]*N
    counts = [0]*N
    for _ in range(N-1):
        a,b=LMIIS()

        E[a-1].append(b-1)
        E[b-1].append(a-1)

    visited = [False]*N
    origins = [0]
    ancestors = defaultdict(list)


    for _ in range(Q):
        p,x = LMIIS()
        X[p-1] += x

    def f(o):
        visited[o] = True
        counts[o] += X[o]
        for d in E[o]:
            if visited[d] != True:
                # ancestors[d] = O
                counts[d] += counts[o]
                f(d)
    
    f(0)
            

    
    for i in counts:
        write(str(i))
        write(' ')

            





    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    from collections import defaultdict
    MOD = 10**9+7

    N,Q = LMIIS()
    edge = defaultdict(list)
    E = defaultdict(list)
    P = []
    X = []
    counts = [0]*N
    for _ in range(N-1):
        a,b=LMIIS()

        E[a-1].append(b-1)
        E[b-1].append(a-1)

    visited = [False]*N
    origins = [0]
    while len(origins) > 0:
        o = origins.pop(0)
        visited[o] = True
        for d in E[o]:
            if visited[d] != True:
                edge[o].append(d)
                origins.append(d)
    
    for _ in range(Q):
        p,x = LMIIS()
        P.append(p-1)
        X.append(x)

    for j in range(Q):
        origins = [P[j]]
        while len(origins) > 0:
            o = origins.pop()
            counts[o] += X[j]
            origins += edge[o]
            

    for i in counts:
        write(str(i))
        write(' ')

            





    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(v,p):
    for u in edges[v]:
        if u == p:
            continue
        lst[u] += lst[v]
        dfs(u,v)

n,q = LI()
edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

lst = [0]*n
for i in range(q):
    p,x = LI()
    lst[p-1] += x

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

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

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

visited[0]=1
dfs(0)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N


def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

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

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

visited[0]=1
dfs(0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
cnt = [0]*N
visited = [0]*N


def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

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

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

visited[0]=1
dfs(0)

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

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc138/submissions/7971841

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

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

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

st = [0]
par = [-1] * n
while st:
    v = st.pop()
    for u in g[v]:
        if u == par[v]: continue
        par[u] = v
        ctr[u] += ctr[v]
        st.append(u)
print(*ctr)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

queue = deque([[0,count[0]]])
already = [0]
while queue:
    x,q = queue.pop()
    already.append(x)
    for i in ki[x]:
        if not i in already:
            count[i] += q
            queue.append([i,count[i]])
        


print(*count)

Submission status: Time Limit Exceeded

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

ans = [0] * N
def dfs(v,p=-1):
    ans[v] = ans[p] + ps[v]
    for to in es[v]:
        if to==p: continue
        dfs(to,v)
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
PX = [tuple(map(int,input().split())) for i in range(Q)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
ps = [0] * N
for p,x in PX:
    ps[p-1] += x

ans = [0] * N
def dfs(v,p=-1):
    ans[v] = ans[p] + ps[v]
    for to in es[v]:
        if to==p: continue
        dfs(to,v)
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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


treeList = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  treeList[a].append(b) # a<bとは限らないため、双方向にする
  treeList[b].append(a)


data3 = getSomeInputListInt(q)

ans = np.zeros(n)

for i in range(len(data3)):
    ans[data3[i][0]-1] += data3[i][1]


def treeTrace(crnt, prnt):
    for chld in treeList[crnt]:
        if prnt == chld:
            continue
        ans[chld] += ans[crnt]

        treeTrace(chld, crnt)

treeTrace(0, -1)

for s in ans:
    print(int(s), end =" ")

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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


treeList = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  treeList[a].append(b) # a<bとは限らないため、双方向にする
  treeList[b].append(a)


data3 = getSomeInputListInt(q)

ans = np.zeros(n)

for i in range(len(data3)):
    ans[data3[i][0]-1] += data3[i][1]


def treeTrace(crnt, prnt):
    for i in range(len(treeList[crnt])):
        if prnt == treeList[crnt][i]:
            continue
        ans[treeList[crnt][i]] += ans[crnt]

        treeTrace(treeList[crnt][i], crnt)

treeTrace(0, -1)

for s in ans:
    print(int(s), end =" ")