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())
 
a = [0] * (n-1)
b = [0] * (n-1)
info = [[] for _ in range(n)]
 
for i in range(n-1):
    a[i],b[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1
    info[a[i]].append(b[i])
    info[b[i]].append(a[i])
 
p = [0] * q
x = [0] * q
 
 
for j in range(q):
    p[j],x[j] = map(int,input().split())
    p[j] -= 1
 
plus = [0] * n
 
for j in range(q):
    plus[p[j]] += x[j]
 
state = [0] * n
state[0] = 1
cur = [0]
 
child = [[] for _ in range(n)]
par = [0] * n
 
ranklist = [[1]]
 
#print(cur)
#print(info)
 
while cur != []:
    cur2 = []
    ranklist.append([])
    for obj in cur:
        for obj2 in info[obj]:
            if state[obj2] == 0:
                state[obj2] = 1
                #child[obj].append(obj2)
                par[obj2] = obj
                cur2.append(obj2)
                ranklist[-1].append(obj2)
    cur = cur2[:]
 
ans = [0] * n
ans[0] = plus[0]
 
for l in ranklist:
    for t in l:
        ans[t] = ans[par[t]] + plus[t]
 
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    N, Q = map(int, input().split())
    E = [[] for i in range(N+1)]
    counter = [0] * (N+1)

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

    for i in range(Q):
        # 頂点p を根とする部分木に含まれるカウンターにxを足す
        p, x = map(int, input().split())
        counter[p] += x

    queue = []

    parent = [1]
    def mktree(v, parent, E):
        children = E[v]
        children.remove(parent)
        for child in children:
            mktree(child, v, E)

    while parent:
        p = parent.pop()
        for child in E[p]:
            E[child].remove(p)
            parent.append(child)

    def get(v, children, counter):
        c = counter[v]
        for child in children[v]:
            counter[child] += c
            get(child, children, counter)
    """
    parent = [1]
    while parent:
        p = parent.pop()
        c = counter[p]
        for child in E[p]:
            counter[child] += c
            parent.append(child)
    """
    get(1, E, counter)
    print(" ".join(str(x) for x in counter[1:]))

main()

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    
    N,Q=MI()
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = MI_()
        edges[a].append(b)
        edges[b].append(a)
    counter = [0]*N
    for _ in range(Q):
        p,x = MI()
        counter[p-1]+=x

    serched = {0}
    def dfs(now_sum,node):
        now_sum += counter[node]

        ans[node] = now_sum
        for b in edges[node]:
            if b not in serched:
                serched.add(b)
                dfs(now_sum,b)
            

    ans = [0]*N
    dfs(0,0)
    print(*ans)


    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,q = map(int, input().split())
tree = [[int(i) for i in input().split()] for i in range(n-1)] 
px = [[int(i) for i in input().split()] for i in range(q)] 
A = [set() for i in range(n)]
B = [set() for i in range(n)]
C = [set() for i in range(n)]
flag = [False] * n

for i,a in enumerate(tree):
  A[a[1]-1].add(tree[i][0])
  B[a[0]-1].add(tree[i][1])

for i in range(n):
  C[i] = A[i] | B[i]

ans = [0] * n

for i in px:

  ans[i[0]-1] += i[1]
  
cr = deque()
cr.append(1)
flag[0] = True

while cr:
  c = cr.popleft()
  flag[c-1] = True
  for i in C[c-1]:
    if flag[i-1]:
      continue
    else:
      cr.append(i)
      ans[i-1] += ans[c-1]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)
A = [0] * (n+1)
B = [0] * (n+1)
P = [0] * (q+1)
X = [0] * (q+1)
to = [[] for i in range(n+1)]
cnt = [0] * (n+1)
for i in range(1,n):
    a,b = [int(j) for j in input().split()]
    to[a].append(b)
    to[b].append(a)
for i in range(1,q+1):
    P,X = [int(j) for j in input().split()]
    T[P] += X
NIL = -1

q =deque()
q.append((1,0,NIL))
while len(q)>0:
    p,x,prev = q.pop()
    x += T[p]
    cnt[p] = x
    for i in to[p]:
        if i != prev:
            q.append((i,x,p))
for i in range(1,n+1):
    print(cnt[i] , end =" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)
A = [0] * (n+1)
B = [0] * (n+1)
P = [0] * (q+1)
X = [0] * (q+1)
to = [[] for i in range(n+1)]
cnt = [0] * (n+1)
for i in range(1,n):
    A[i],B[i] = [int(j) for j in input().split()]
    to[A[i]].append(B[i])
    to[B[i]].append(A[i])
for i in range(1,q+1):
    P[i],X[i] = [int(j) for j in input().split()]
    T[P[i]] += X[i]
NIL = -1

q =deque()
q.append((1,0,NIL))
while len(q)>0:
    p,x,prev = q.pop()
    x += T[p]
    cnt[p] = x
    for i in to[p]:
        if i != prev:
            q.append((i,x,p))
for i in range(1,n+1):
    print(cnt[i] , end =" ")

Submission status: Time Limit Exceeded

Solution code:
n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)
A = [0] * (n+1)
B = [0] * (n+1)
P = [0] * (q+1)
X = [0] * (q+1)
for i in range(1,n):
    A[i],B[i] = [int(j) for j in input().split()]
for i in range(1,q+1):
    P[i],X[i] = [int(j) for j in input().split()]

NIL = -1

class node:
    def __init__(self):
        self.value = 0
        self.child = []
        self.parent = NIL

def childadd(T,x):
    for i in range(len(T[x].child)):
        T[T[x].child[i]].value += T[x].value
        if T[T[x].child[i]].child != []:
            childadd(T,T[x].child[i])

for i in range(1,n+1):
    T[i] = node()
T[1] = node()
T[1].parent = 0
for i in range(1,n):
    if T[A[i]].parent != NIL:
        T[A[i]].child.append(B[i])
        T[B[i]].parent = T[A[i]]
    else:
        T[B[i]].child.append(A[i])
        T[A[i]].parent = T[B[i]]

for i in range(1,q+1):
    T[P[i]].value += X[i]

childadd(T,1)

for i in range(1,n+1):
    print(T[i].value,end = " ")

Submission status: Time Limit Exceeded

Solution code:
def solve(n, q, a, b, p, x):
    E = [[] for i in range(n+1)]
    for a_i, b_i in zip(a, b):
        E[a_i].append(b_i)
        E[b_i].append(a_i)
    res = {i: 0 for i in range(1, n+1)}
    for j in range(q):
        res[p[j]] += x[j]
    used = [False] * (n+1)
    used[1] = True
    que = [1]
    while que:
        u = que.pop(0)
        for v in E[u]:
            if not used[v]:
                used[v] = True
                res[v] += res[u]
                que.append(v)
    return " ".join(map(str, [res[i] for i in range(1,n+1)]))

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

Submission status: Time Limit Exceeded

Solution code:
import collections

class Node():
  def __init__(self, num):
    self.num = num
    self.count = 0
    self.nexts = []
    self.checked = False
  def add_nexts(self, node):
    self.nexts.append(node)
  def counter(self, n):
    self.count += n
  def __repr__(self):
    return str(self.num)
  def __str__(self):
    return str(self.num)

N, Q = list(map(int, input().split()))
node_list = [Node(i) for i in range(0, N+1)]
for i in range(0, N-1): 
  a, b = list(map(int, input().split()))
  node_list[a].add_nexts(node_list[b])
  node_list[b].add_nexts(node_list[a])
for i in range(0, Q):
  p, x = list(map(int, input().split()))
  node_list[p].counter(x)
q = collections.deque()
q.append(node_list[1])
while q:
  node = q.pop()
  node.checked = True
  for nexts_node in node.nexts:
    if nexts_node.checked:
      continue
    nexts_node.counter(node.count)
    q.append(nexts_node)
print(*[node.count for node in node_list[1:]])

Submission status: Time Limit Exceeded

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

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

for i,j in AB:
  g[i].append(j)
  g[j].append(i)
 
def BTS(a, b):
  for i in g[a]:
    if i == b:
      continue
    C[i-1] += C[a-1]
    BTS(i,a)
    
BTS(1,-1)
 
print(*C)

Submission status: Time Limit Exceeded

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

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

for i,j in AB:
  g[i].append(j)
  g[j].append(i)
 
def BTS(a, b):
  for i in g[a]:
    if i == b:
      continue
    C[i-1] += C[a-1]
    BTS(i,a)
    
BTS(1,-1)
 
print(*C)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
ans = [0]*N

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

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

judge = [0]
queue = [0]
while queue:
    a = queue.pop()
    for i in G[a]:
        if i not in judge:
            judge.append(i)
            ans[i] += ans[a]
            if G[i]:
                queue.append(i)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(20000000)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = [[0, deque()] for _ in range(N)]

    for _ in range(N - 1):
        p, c = map(int, input().split())
        ans[p-1][1].append(c-1)
        ans[c-1][1].append(p-1)

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

    def add_value(node, parent):
        val = ans[node][0]
        children = ans[node][1]
        for child in children:
            if child == parent:
                continue
            ans[child][0] += val
            add_value(child, node)

    add_value(0, -1)

    print(' '.join([str(x[0]) for x in ans]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

ans = [0] * n


def f(par, node, count):
    count += counter[node]
    ans[node] = count
    for n in edges[node]:
        if n == par:
            continue
        f(node, n, count)


f(-1, 0, 0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

g = {i:[] for i in range(N+1)}
cnt = {i:0 for i in range(N+1)}
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

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

dfs(1, -1)

print(*list(cnt.values())[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = [0] * N
    con = deque([[] for i in range(N)])

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

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

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = deque([0] * N)
    con = [[] for i in range(N)]

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

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

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

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

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

dfs(1, -1)

print(*cnt[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

g = [[] for _ in range(N)]
cnt = [0 for _ in range(N)]
for i 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):
    p, x = map(int, input().split())
    p -= 1
    cnt[p] += x

dfs(0, -1)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = deque([0] * N)
    con = deque([[] for _ in range(N)])
    ops = []
    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

    for _ in range(Q):
        ops.append(tuple(map(int, input().split())))

    for op in ops:
        node = op[0] - 1
        pnt = op[1]
        ans[node] += pnt
    # for _ in range(Q):
    #     p, v = map(int, input().split())
    #     ans[p-1] += v

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v, p, c):
    cnt[v] += c
    for next_v in g[v]:
        if next_v == p:
            continue
        dfs(next_v, v, cnt[v])


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

g = [[] for _ in range(N)]
cnt = [0 for _ in range(N)]
for i 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):
    p, x = map(int, input().split())
    p -= 1
    cnt[p] += x

dfs(0, -1, 0)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:

import sys

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, c):
    cnt[v]+=c
    for next_v in g[v]:
        if next_v == p:
            continue
        dfs(next_v, v, cnt[v])

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

g = [[] for _ in range(N)]
cnt = [0 for _ in range(N)]
for i 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):
    p, x = map(int, input().split())
    p -= 1
    cnt[p]+=x


dfs(0, -1, 0)

print(*cnt)

Submission status: Time Limit Exceeded

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


def main():
    N, Q = map(int, input().split())
    ans = deque([0] * N)
    con = deque([[] for _ in range(N)])

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

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

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


N, Q = map(int, input().split())
ans = deque([0] * N)
con = deque([[] for _ in range(N)])

for _ in range(N - 1):
    p, c = map(int, input().split())
    con[p-1].append(c-1)
    con[c-1].append(p-1)

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

stacks = deque()
stacks.append((0, -1))

while stacks:
    stack = stacks.pop()
    node, parent = stack[0], stack[1]

    children = con[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stacks.append((child, node))

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = deque([0] * N)
    con = deque([[] for _ in range(N)])

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

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

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = deque([0] * N)
    con = deque([[] for _ in range(N)])

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

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

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        if children:
            for child in children:
                if child == parent:
                    continue
                ans[child] += ans[node]
                stacks.append((child, node))

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = deque([0] * N)
    con = deque([[] for _ in range(N)])

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

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

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        if children:
            for child in children:
                if child == parent:
                    continue
                ans[child] += ans[node]
                stacks.append((child, node))

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

#print(N, Q, ab, px)
class Tree:
    def __init__(self):
        # n番目のノードの値
        self.value = [0 for _ in range(N+1)]
        # n番目の, 親から含めたノードの値
        self.total_value = [0 for _ in range(N+1)]
        # n番目のノードの一つ下の辺リスト
        self.edge = [[] for _ in range(N+1)]

    def build(self, a, b):
        #print("Tree build ", a, " ", b)
        self.edge[a].append(b)
        self.edge[b].append(a)


    def add(self, p, x):
        # 木の値を更新していく
        self.value[p] += x

    # 値を親から子に向かって更新する
    def reflesh(self):
        stack = deque()
        stack.append((1, 0))
        while stack:
            st = stack.pop()
            node, parent = st[0], st[1]
            children = self.edge[node]
            for child in children:
                if child == parent:
                    continue
                #print("c n", child, node)
                self.value[child] += self.value[node]
                stack.append((child, node))


tree = Tree()
for ab_ in ab:
    tree.build(*ab_)

for px_ in px:
    tree.add(*px_)

tree.reflesh()
#print(" ".join([str(tree.value[x]) for x in range(1,N+1)]))
print(" ".join([str(tree.value[x]) for x in range(1,N+1)]))
#for i in range(1,N+1):
    #print(tree.edge[i], end=",")
#    print(tree.value[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(20000000)
N, Q = [int(i) for i in input().split()]
tree = {i:[] for i in range(1,N+1)}
cost_ls = {i:0 for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def plus(node, _from):
    #cost_ls[node] += num
    for child in tree[node]:
        if child == _from:
            continue
        cost_ls[child] += cost_ls[node]
        plus(child, node)

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

plus(1, 0)

print(' '.join(str(cost_ls[i]) for i in range(1,N+1)))

Submission status: Time Limit Exceeded

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

def plus(node, _from):
    #cost_ls[node] += num
    for child in tree[node]:
        if child == _from:
            continue
        cost_ls[child] += cost_ls[node]
        plus(child, node)

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

plus(1, 0)

print(' '.join(str(cost_ls[i]) for i in range(1,N+1)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy

num, sousa_num = map(int, input().split())

ki = defaultdict(list)

prev = [1]

for i in range(num-1):
  a, b = map(int, input().split())
  if a in prev:
    ki[a].append(b)
    prev.append(b)
  else:
    ki[b].append(a)
    prev.append(a)

c = [0 for i in range(num+1)]



for i in range(sousa_num):
  a, b = map(int, input().split())
  c[a] += b


q = [1]

while True:
  a = []
  for x in q:
    a += ki[x]
    for y in ki[x]:
      c[y] += c[x]
  
  if len(a) == 0:
    break
  else:
    q = copy.copy(a)

print(" ".join(map(str, c[1:])))

Submission status: Time Limit Exceeded

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

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

counts = [0] * (n+1)
adjs = {a: [] for a in range(1,n+1)}

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

costs = [[int(x) for x in input().split()] for i in range(q)]

for cost in costs:
    counts[cost[0]] += cost[1]

visited = set()
queue = deque()
queue.append(1)

while len(queue) > 0:
    a = queue.popleft()
    visited.add(a)
    for b in adjs[a]:
        if b in visited:
            continue
        counts[b] += counts[a]
        queue.append(b)

print(' '.join(list(map(lambda x: str(x), counts[1:]))))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
from collections import defaultdict
g = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

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

visited = defaultdict(bool)
stack = []
visited[1] = True
stack.append(1)
while len(stack) != 0:
    v = stack.pop()
    W = w[v]
    ans[v] += W
    for c in g[v]:
        if not visited[c]:
            visited[c] = True
            stack.append(c)
            ans[c] += ans[v]

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import queue
n,q = map(int,input().split())
l = [0 for i in range(n)]
l2 = [[] for i in range(n)]
l3 = [0 for i in range(n)]
l3[0] = 1
for i in range(n-1):
    a,b = map(int,input().split())
    l2[b-1].append(a-1)
    l2[a-1].append(b-1)
for i in range(q):
    c,d = map(int,input().split())
    l[c-1] += d
ans = [0 for i in range(n)]
ans[0] = l[0]
q1 = queue.Queue()
q1.put(0)
while not q1.empty():
    k = q1.get()
    q2 = l2[k]
    for i in range(len(q2)):
        k1 = q2[i]
        if l3[k1] == 0:
            ans[k1] = ans[k] + l[k1]
            q1.put(k1)
            l3[k1] = 1
for x in ans:
    print(x,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import queue
n,q = map(int,input().split())
l = [0 for i in range(n)]
l2 = [queue.Queue() for i in range(n)]
l3 = [0 for i in range(n)]
l3[0] = 1
for i in range(n-1):
    a,b = map(int,input().split())
    l2[b-1].put(a-1)
    l2[a-1].put(b-1)
for i in range(q):
    c,d = map(int,input().split())
    l[c-1] += d
ans = [0 for i in range(n)]
ans[0] = l[0]
q1 = queue.Queue()
q1.put(0)
while not q1.empty():
    k = q1.get()
    q2 = l2[k]
    while not q2.empty():
        k1 = q2.get()
        if l3[k1] == 0:
            ans[k1] = ans[k] + l[k1]
            q1.put(k1)
            l3[k1] = 1
for x in ans:
    print(x,end=" ")

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1,N+1)}

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


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)

propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1,N+1)))

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1,N+1)}

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


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)

propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1,N+1)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding utf-8 -*-
from collections import defaultdict

MOD = 10 ** 9 + 7
N, Q = map(int, input().split())

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

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

cur_node = set()
cur_node.add(1)
pre_node = set()
while len(cur_node) != 0:
    next_node = set()
    for ni in cur_node:
        for nj in tree[ni]:
            if nj in pre_node:
                continue
            counter[nj] += counter[ni]
            next_node.add(nj)
    pre_node = cur_node
    cur_node = next_node

print(' '.join((str(counter[i]) for i in range(1, N + 1))))