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())

edge = [[] for _ in range(n)]

counter = [0] * 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):
    a, b = map(int, input().split())
    counter[a-1] += b

parent = [0]
s_next = {0}

for i in parent:
    for v in edge[i]:
        # if v in parent:
        #     continue
        if v in s_next:
            continue
        s_next.add(v)
        parent.append(v)
        counter[v] += counter[i]
        
for i in range(n):
    print(counter[i], end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:

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

edge = [[] for _ in range(n)]

counter = [0] * 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):
    a, b = map(int, input().split())
    counter[a-1] += b

parent = [0]
visited = []

for i in parent:
    for v in edge[i]:
        if v in parent:
            continue
        parent.append(v)
        counter[v] += counter[i]
        
for i in range(n):
    print(counter[i], end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:

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

edge = [[] for _ in range(n)]

counter = [0] * 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):
    a, b = map(int, input().split())
    counter[a-1] += b

parent = [0]
visited = []
for i in parent:
    visited.append(i)
    for v in edge[i]:
        if v in visited:
            continue
        parent.append(v)
        counter[v] += counter[i]
        
for i in range(n):
    print(counter[i], end=" ")
print("")

Submission status: Time Limit Exceeded

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

def f(ab: list, parent: list, i: int = 0):
    if len(ab[i]) == 1 and i != 0:
        return
    for j in ab[i]:
        if j != parent[i]:
            parent[j] = i
            f(ab, parent, j)

def g(ab: list, parent: list, ans: list, i: int = 0):
    if len(ab[i]) == 1 and i != 0:
        return
    for j in ab[i]:
        if j != parent[i]:
            ans[j] += ans[i]
            g(ab, parent, ans, j)

def main():
    N, Q = map(int, input().split())
    ab = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    parent = [-1] * N
    f(ab, parent)
    ans = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
    g(ab, parent, ans)
    print(' '.join(list(map(str, ans))))
    

if __name__ == '__main__': main()

Submission status: Time Limit Exceeded

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

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

A = set() # 辺
for i in range(N-1):
    a,b = map(int, input().split())
    A.add((a,b))

P = [] # 足す操作
for i in range(Q):
    x,y = map(int, input().split())
    P.append((x,y))

V = [0]*N # 頂点のカウンター
for p in P:
    V[p[0]-1] += p[1] # P で指定されたノード・値で初期化

# 方針：親から子にカウンターの値を流していく。
# 根付き木なので、根から始めれば、ある辺（親から子）は一度処理するだけで良いはず。
parent = {1} # 親（最初は根）
while parent:
    children = set() # 子。根からの深さが同じの頂点（になるはず）
    for p in parent:
        tmp = set(a for a in A if p in a) # P を含む辺＝処理する辺
        child = set() # p を親に持つノードの index
        for a in tmp:
            child.add(a[1] if a[0] == p else a[0]) # 親と異なる値が子
        for c in child:
            V[c-1] += V[p-1] # 子のカウンターに、親のカウンターの値を足す
        A -= tmp # 処理済みの辺を除去
        children |= child # 子の集合の和を取る
    parent = children # 子の集合を次の親にする

print(*V)

Submission status: Time Limit Exceeded

Solution code:
# ABC 138 D 問題
# https://atcoder.jp/contests/abc138/tasks/abc138_d

def add_val(ans, point, value, query, route, checked):
    if point in query.keys():
        value += query[point]
    
    ans[point] += value
    checked.append(point)
    
    if point in route.keys():
        for next_point in route[point]:
            if next_point not in checked:
                add_val(ans, next_point, value, query, route, checked)

n, q = list(map(lambda x: int(x), input().split()))

r = {}

for i in range(n-1):
    s, e = list(map(lambda x: int(x), input().split()))
    if s-1 in r.keys():
        r[s-1].append(e-1)
    else:
        r[s-1] = [e-1]
    if e-1 in r.keys():
        r[e-1].append(s-1)
    else:
        r[e-1] = [s-1]
        
queries = {}

for i in range(q):
    p, val = list(map(lambda x: int(x), input().split()))
    if p-1 in queries.keys():
        queries[p-1] += val
    else:
        queries[p-1] = val

ans = [0] * n    
checked = []

add_val(ans, 0, 0, queries, r, checked)
    


ans_str = ''

for i in range(n):
    ans_str += str(ans[i])
    if i < n-1:
        ans_str += ' '

print(ans_str)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 7)

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

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

value = [0] * (n + 1)
for p, x in px:
    value[p] += x


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


dfs(1, 0, 0)

ans = value[1:]
print(*ans)

Submission status: Time Limit Exceeded

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

N, Q = [int(x) for x in input().split()]

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

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

next = [0]
for i in next:
    for v in edge[i]:
        s_next = set(next)
        if v in s_next:
            continue
        next.append(v)
        cost[v] += cost[i]

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

Submission status: Time Limit Exceeded

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

N, Q = [int(x) for x in input().split()]

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

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

next = [0]
for i in next:
    for v in edge[i]:
        if v in next:
            continue
        next.append(v)
        cost[v] += cost[i]

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

Submission status: Time Limit Exceeded

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

N, Q = [int(x) for x in input().split()]

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

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

next = [0]
for i in next:
    for v in edge[i] + edge2[i]:
        if v in next:
            continue
        next.append(v)
        cost[v] += cost[i]

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
parents = [[] for i in range(n)]
points = [0] * n

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

done = [0] * n
key = [1]

while (0 in done):
  pos = key.pop()
  done[pos-1] = 1
  for j in parents[pos-1]:
    if done[j-1] != 1:
      points[j-1] += points[pos-1]
      key.append(j)
  
print(*points)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N,Q = LI()
    Child = [[] for _ in range(N)]
    tree = [False]*N
    tree[0] = True
    cur_tree = []
    for _ in range(N-1):
        a,b = LI()
        cur_tree.append([a-1,b-1])

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    while cur_tree:
        nxt_tree = []
        for a,b in cur_tree:
            if tree[a]:
                Child[a].append(b)
                counter[b] += counter[a]
                tree[b] = True
            elif tree[b]:
                Child[b].append(a)
                counter[a] += counter[b]
                tree[a] = True
            else:
                nxt_tree.append([a,b])
        cur_tree = [x for x in nxt_tree]

    r = [counter[i] for i in range(N)]

    return(" ".join(map(str,r)))

if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N,Q = LI()
    Parent = [-1] * N
    tree = [False]*N
    tree[0] = True
    cur_tree = []
    for _ in range(N-1):
        a,b = LI()
        cur_tree.append([a-1,b-1])

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    while cur_tree:
        nxt_tree = []
        for a,b in cur_tree:
            if tree[a]:
                Parent[b] = a
                tree[b] = True
            elif tree[b]:
                Parent[a] = b
                tree[a] = True
            else:
                nxt_tree.append([a,b])
        cur_tree = [x for x in nxt_tree]

    r = []

    for i in range(N):
        ans = counter[i]
        p = Parent[i]
        while p != -1:
            ans += counter[p]
            p = Parent[p]
        r.append(ans)

    return(" ".join(map(str,r)))




if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

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

from collections import defaultdict

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

edge = [defaultdict(int) for i in range(N)]

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

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

def tree(root):
    for child in edge[root].keys():
        del edge[child][root]
        tree(child)

tree(0)

ans = [0] * N
def scoring(root):
    ans[root] += counters[root]
    for child in edge[root]:
        ans[child] += ans[root]
        scoring(child)

scoring(0)

for val in ans[:N-1]:
    print(val, end = " ")
print(ans[-1])

Submission status: Time Limit Exceeded

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

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

edge = [{} for i in range(N)]

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

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

def tree(root):
    for child in edge[root].keys():
        del edge[child][root]
        tree(child)

tree(0)

ans = [0] * N
def scoring(root):
    ans[root] += counters[root]
    for child in edge[root]:
        ans[child] += ans[root]
        scoring(child)

scoring(0)

for val in ans[:N-1]:
    print(val, end = " ")
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
import sys
sys.setrecursionlimit(200005)

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

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

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

queue = Queue()
queue.put([0,1])
while not queue.empty():
    parent, node = queue.get()
    for leaf in tree[node]:
        if leaf == parent:
            continue
        counter[leaf] += counter[node]
        queue.put([node, leaf])

for counter_i in counter[1:]:
    print(counter_i, end=" ")

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(200005)

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

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

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

que = [[0,1]]
while len(que) > 0:
    parent, node = que.pop(0)
    for leaf in tree[node]:
        if leaf == parent:
            continue
        counter[leaf] += counter[node]
        que.append([node, leaf])

for counter_i in counter[1:]:
    print(counter_i, end=" ")

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(200005)

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

ab = []
for i in range(n-1):
    ab.append([int(i) for i in input().split()])

px = []
for i in range(q):
    px.append([int(i) for i in input().split()])

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

counter = [0] * (n+1)

for p, x in px:
    counter[p] += x

def count(node, parent=0):
    for leaf in graph[node]:
        if leaf == parent:
            continue
        counter[leaf] += counter[node]
        count(leaf, node)

count(1)

for counter_i in counter[1:]:
    print(counter_i, end=" ")

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N,Q = map(int, input().split())
    tree = [[] for i in range(N)]
    tree_counter = [0] * N
    searched = [False]*N

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

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

    stack = [0]
    searched[0] = True
    while stack:
        idx = stack.pop(0)
        searched[idx] = True
        cnt = tree_counter[idx]
        for next_node in tree[idx]:
            if not searched[next_node]:
                stack.append(next_node)
                tree_counter[next_node] += cnt
            
    print(' '.join(list(map(str, tree_counter))))
    
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
#dc={i:[] for i in range(1,N)}
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lf=[0 for i in range(N)]#行ったかどうかのフラグ
lv=[0 for i in range(N)]
#*で初期化するとあまり良くない
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
#print("lv",lv)
lque=[0]#次に訪れる親を入れておく(キュー(順番通り))
lf[0]=1
#p=0
while len(lque)!=0:
#count=1
#while count<N:
    #for i in range(len(lc[p]))
    p=lque[0]
    for i in lc[p]:#among children
        #lv[lque[0]]+=
        #c=lc[p][i]
        if lf[i]==0:
             lv[i]+=lv[p]
             lf[i]+=1
             lque.append(i)
             #count+=1
    #p=lque[0]
    lque.remove(p)
for i in lv:
    print(i,end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
#pythonで再帰は遅い_pypyだと再帰に関しては更に遅い
N,Q=map(int,input().split())
#dc={i:[] for i in range(1,N)}
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lf=[0 for i in range(N)]#行ったかどうかのフラグ
lv=[0 for i in range(N)]
#*で初期化するとあまり良くない
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
#print("lv",lv)
lque=[0]#次に訪れる親を入れておく(キュー(順番通り))
lf[0]=1
#p=0
while len(lque)!=0:
#count=1
#while count<N:
    #for i in range(len(lc[p]))
    p=lque[0]
    for i in lc[p]:#among children
        #lv[lque[0]]+=
        #c=lc[p][i]
        if lf[i]==0:
             lv[i]+=lv[p]
             lf[i]+=1
             lque.append(i)
             #count+=1
    #p=lque[0]
    lque.remove(p)
for i in lv:
    print(i,end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200005)

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

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

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

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

dfs(0)
for i in ans:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
N,Q=map(int,input().split())
dg={i:[[],0] for i in range(1,N+1)}
for i in range(1,N):
    a,b=map(int,input().split())
    dg[a][0].append(b)
    dg[b][0].append(a)
#print(dg)
def habatan(p,me):
    if me!=1:
        dg[me][0].remove(p)
    for c in dg[me][0]:
        habatan(me,c)

habatan(0,1)#dg親消し
#print(dg)
#dv={i:0 for i in range(1,N+1)}
for i in range(Q):
    p,x=map(int,input().split())
    #dv[p]+=x
    dg[p][1]+=x
#dans={}
def habatan1(p,me):
    if me!=1:
        #dv[me]+=
        dg[me][1]+=dg[p][1]
    #for c in dg[me]:
    for c in dg[me][0]:
        habatan1(me,c)
habatan1(0,1)
for i in range(1,N+1):
    #print(dv[i],end=" ")
    print(dg[i][1],end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

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

visited = [False] * (n + 1)
visited[0] = True
visited[1] = True
while not all(visited):
    for a in range(1, n + 1):
        if not visited[a]:
            continue
        for b in es[a]:
            if not visited[b]:
                ps[b] += ps[a]
            visited[b] = True
print(*ps[1:])

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

input = sys.stdin.readline

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

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

levels = [-1] * (n + 1)
levels[1] = 0
while len(ls) > 0:
    a, b = ls.popleft()
    la = levels[a]
    lb = levels[b]
    if la >= 0:
        levels[b] = la + 1
        ps[b] += ps[a]
    elif lb >= 0:
        levels[a] = lb + 1
        ps[a] += ps[b]
    else:
        ls.append([a, b])

print(*ps[1:])

Submission status: Time Limit Exceeded

Solution code:
import collections

n, q = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(n - 1)]
ls.sort(key=lambda x: x[0])
ls = collections.deque(ls)

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

levels = [-1] * (n + 1)
levels[1] = 0
es = []
while len(ls) > 0:
    e = ls.popleft()
    l0 = levels[e[0]]
    l1 = levels[e[1]]
    if l0 >= 0:
        levels[e[1]] = l0 + 1
        es.append(e + [l0])
    elif l1 >= 0:
        levels[e[0]] = l1 + 1
        es.append(e[::-1] + [l1])
    else:
        ls.append(e)
es.sort(key=lambda x: x[2])

for a, b, _ in es:
    ps[b] += ps[a]
print(*ps[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
n,q = map(int,input().split())
d = defaultdict(list)
dp = defaultdict(int)
ep = [0] * n
for i in range(n-1):
    ta,tb = map(int,input().split())
    d[ta-1].append(tb-1)
    d[tb-1].append(ta-1)
for i in range(q):
    ta,tb = map(int,input().split())
    dp[ta-1] +=tb
ep[0]+=1
l = deque()
l.append(0)
while l:
    t = l.pop()
    for i in d[t]:
        if ep[i] == 0:
            dp[i] += dp[t]
            ep[i]+=1
            l.append(i)
ans = []
for i in dp:
    print(dp[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
n,q = map(int,input().split())
d = defaultdict(list)
dp = defaultdict(int)
ep = [0] * n
for i in range(n-1):
    ta,tb = map(int,input().split())
    d[ta-1].append(tb-1)
    d[tb-1].append(ta-1)
for i in range(q):
    ta,tb = map(int,input().split())
    dp[ta-1] +=tb
ep[0]+=1
l = deque()
l.append(0)
while l:
    t = l.pop()
    for i in d[t]:
        if ep[i] == 0:
            dp[i] += dp[t]
            ep[i]+=1
            l.append(i)
ans = []
for i in dp:
    ans.append(dp[i])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,q = map(int,input().split())
d = defaultdict(list)
dp = defaultdict(int)
ep = [0] * n
for i in range(n-1):
    ta,tb = map(int,input().split())
    d[ta-1].append(tb-1)
    d[tb-1].append(ta-1)
for i in range(q):
    ta,tb = map(int,input().split())
    dp[ta-1] +=tb
ep[0]+=1
l = []
l.append(0)
while l:
    t = l.pop()
    for i in d[t]:
        if ep[i] == 0:
            dp[i] += dp[t]
            ep[i]+=1
            l.append(i)
ans = []
for i in dp:
    ans.append(dp[i])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

E = []
for _ in range(N - 1):
    E.append(tuple(map(lambda x: int(x) - 1, input().split())))

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

visit = {0}
while len(visit) < N:
    for i, j in E:
        if i in visit and j not in visit:
            counter[j] += counter[i]
            visit.add(j)
        elif j in visit and i not in visit:
            counter[i] += counter[j]
            visit.add(i)

for i, c in enumerate(counter):
    if i < N - 1:
        print(c,end=' ')
    else:
        print(c)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

E = []
for _ in range(N - 1):
    E.append(tuple(map(lambda x: int(x) - 1, input().split())))

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

visit = {0}
while len(visit) < N:
    for i, j in E:
        if i in visit and j not in visit:
            counter[j] += counter[i]
            visit.add(j)
        elif j in visit and i not in visit:
            counter[i] += counter[j]
            visit.add(i)

for i, c in enumerate(counter):
    if i < N - 1:
        print(c,end=' ')
    else:
        print(c)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

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

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

queue = [[1, 0]]
while len(queue) > 0:
  q = queue.pop(0)
  if q[0] != 0:
    cnt[q[0]] += cnt[q[1]]
  for i in to[q[0]]:
    if i != q[1]:
      queue.append([i, q[0]])

for i in range(1, N + 1):
  print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

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

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

queue = [[0, -1]]
while len(queue) > 0:
  q = queue.pop(0)
  if q[0] != 0:
    cnt[q[0]] += cnt[q[1]]
  for i in to[q[0]]:
    if i != q[1]:
      queue.append([i, q[0]])

for c in cnt:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

queue = deque()
queue.append((0, -1))
while queue:
  q = queue.popleft()
  if q[0] != 0:
    cnt[q[0]] += cnt[q[1]]
  for i in to[q[0]]:
    if i != q[1]:
      queue.append((i, q[0]))

for i in range(N):
  print(cnt[i], end = "")
  if i == N - 1:
    print()
  else:
    print(" ", end = "")

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

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

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

queue = [[0, -1]]
while len(queue) > 0:
  q = queue.pop(0)
  if q[0] != 0:
    cnt[q[0]] += cnt[q[1]]
  for i in to[q[0]]:
    if i != q[1]:
      queue.append([i, q[0]])

for i in range(N):
  print(cnt[i], end = "")
  if i == N - 1:
    print()
  else:
    print(" ", end = "")

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

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

queue = [0]
parent = [0 for _ in range(N)]
while len(queue) > 0:
  q = queue.pop(0)
  for br in to[q]:
    to[br].remove(q)
    parent[br] = q
    queue.append(br)

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

queue = [0]
while len(queue) > 0:
  q = queue.pop(0)
  if q != 0:
    cnt[q] += cnt[parent[q]]
  for br in to[q]:
    queue.append(br)

for i in range(N):
  print(cnt[i], end = "")
  if i == N - 1:
    print()
  else:
    print(" ", end = "")

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

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

queue = [0]
parent = [[] for _ in range(N)]
while len(queue) > 0:
  q = queue.pop(0)
  for br in to[q]:
    to[br].remove(q)
    parent[br].append(q)
    queue.append(br)

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

queue = [0]
while len(queue) > 0:
  q = queue.pop(0)
  if q != 0:
    cnt[q] += cnt[parent[q][0]]
  for br in to[q]:
    queue.append(br)

for i in range(N):
  print(cnt[i], end = "")
  if i == N - 1:
    print()
  else:
    print(" ", end = "")

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

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

queue = [0]
branch = [[i] for i in range(N)]
parent = [[] for _ in range(N)]
while len(queue) > 0:
  q = queue.pop(0)
  for br in to[q]:
    branch[q].append(br)
    to[br].remove(q)
    parent[br].append(q)
    for p in parent[q]:
      parent[br].append(p)
    queue.append(br)

for i in range(1, N):
  for p in parent[i]:
    if not i in branch[p]:
      branch[p].append(i)

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

for i in range(N):
  print(cnt[i], end = "")
  if i == N - 1:
    print()
  else:
    print(" ", end = "")

Submission status: Time Limit Exceeded

Solution code:
# ABC138D - Ki
def dfs(r: int) -> None:
    stack = [(r, -1)]
    while stack:
        v, p = stack.pop(0)
        x = cnt[v]
        for u in T[v]:
            if u != p:
                cnt[u] += x
                stack.append((u, v))


def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, cnt
    N, Q, *A = map(int, open(0).read().split())
    E, P = A[: (N - 1) * 2], A[(N - 1) * 2 :]
    T = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(E)] * 2):
        T[v].append(u), T[u].append(v)
    cnt = [0] * (N + 1)
    for p, x in zip(*[iter(P)] * 2):
        cnt[p] += x  # increase vertex p by x
    dfs(1)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, q = rrd()

v = [[] for _i in range(n + 10)]

for i in range(n - 1):
    x, y = rrd()
    v[x].append(y)
    v[y].append(x)

add = [0] * (n + 10)

for i in range(q):
    p, x = rrd()
    add[p] += x


def dfs(now, fa):
    add[now] += add[fa]
    for i in v[now]:
        if i == fa:
            continue
        dfs(i, now)


dfs(1, 0)

stdout.write(" ".join(map(str,add[1:n+1])))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, q = rrd()

v = [[] for _i in range(n + 10)]

for i in range(n - 1):
    x, y = rrd()
    v[x].append(y)
    v[y].append(x)

add = [0] * (n + 10)

for i in range(q):
    p, x = rrd()
    add[p] += x


def dfs(now, fa):
    add[now] += add[fa]
    for i in v[now]:
        if i == fa:
            continue
        dfs(i, now)


dfs(1, 0)

for i in range(1, n + 1):
    print(add[i], end=' ')