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:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    nodes[a-1].append(b-1)

ans = [0] * N
for i in range(Q):
    p, x = MAP()
    ans[p-1] += x

def dfs(u, prev, cnt):
    ans[u] += cnt
    for v in nodes[u]:
        if v != prev:
            dfs(v, u, ans[u])
dfs(0, -1, 0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

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

C = [0] * N

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

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


dfs(0, 0)

print(" ".join([str(x) for x in ANS]))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
d = {}
ans = [0]*(n+1)
for i in range(n-1):
    sta,gol = map(int,input().split())
    if gol not in d:
        d[gol] = set() 
    d[gol].add(sta)

for i in range(q):
    sta,val = map(int,input().split())
    ans[sta]+=val
    

for i in range(n):
    gol = i+1
    if gol in d:
        tmpset = d[gol]
        for t in tmpset:
            ans[gol]+=ans[t]
    

anss = ""
for i in range(n):
    anss = anss+str(ans[i+1])+" "
print(anss)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
graph = {i + 1:[] for i in range(n)}
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
count = {i + 1:0 for i in range(n)}
for i in range(q):
    p, x = map(int, input().split())
    count[p] += x
add_list = [1]
while add_list:
    add = add_list.pop(0)
    for i in graph[add]:
        add_list.append(i)
        count[i] += count[add]
for i in range(n):
    print(count[i + 1], end = " ")
print()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, q =  list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(n-1)]
y = [list(map(int, input().split())) for i in range(q)]

res = np.zeros(n)
for i in range(q):
    res[y[i][0]-1] += y[i][1]
    for j in range(n-1):
        if x[j][0] >= y[i][0]:
            res[x[j][1]-1] += y[i][1]
for i in range(n):
    if i == n-1:
        print(int(res[i]), end="")
    else:
        print(int(res[i]), end =" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

# 木
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

## クエリを覚えておく
scores = [0]*N
for i in range(Q):
    p,x = map(int, input().split())
    scores[p-1] += x 

# 和をとっていく
ans = [0]*N
ans[0] = scores[0]
used = [False] * N

def dfs(G, v):
   # vを訪問済みにする
   used[v] = True
   #グラフ中の次のVについて
   for next_v in G[v]:
       # すでに見られていたら無視
       if used[next_v]: continue
       # 見られていない場合、再帰的に探索
       # 親のスコアも足していく
       ans[next_v] = ans[v] + scores[next_v]
       dfs(G, next_v)

dfs(G,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
a = []
b = []
hens = []
for i in range (n-1):
  t_a, t_b = map(int, input().split())
  a.append(t_a-1)
  b.append(t_b-1)
  hens.append([t_a-1, t_b-1])
p = []
x = []
for i in range (q):
  t_p, t_x = map(int, input().split())
  p.append(t_p-1)
  x.append(t_x)
c = [0 for i in range(n)]
tree = [[None, [], False] for i in range(n)]
tree[0][2] = True

while(len(hens) >= 1):
  for hen in hens[:]:
    if tree[hen[0]][2] == True:
      tree[hen[0]][1].append(hen[1])
      tree[hen[1]][0] = hen[0]
      tree[hen[1]][2] = True
    elif tree[hen[1]][2] == True:
      tree[hen[1]][1].append(hen[0])
      tree[hen[0]][0] = hen[1]
      tree[hen[0]][2] = True
    hens.remove(hen)

ret = [0 for i in range(n)]

def calc(p, x):
  global ret
  if len(tree[p][1]) == 0:
    ret[p] += x
  else:
    for child in tree[p][1]:
      calc(child, x)
    ret[p] += x

ans = [0 for i in range(n)]
for i in range(q):
  ret = [0 for i in range(n)]
  calc(p[i], x[i])
  ans = [x+y for x,y in zip(ans, ret)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,Q = inpl()

lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1,b-1
    lines[a].add(b)

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

ans = [0]*N

q = queue.LifoQueue()
q.put([0,0])

while not q.empty():
    x,cnt = q.get()
    cnt += adds[x]
    ans[x] += cnt
    for t in lines[x]:
        q.put([t,cnt])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
 
val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,input().split())
    val[a-1] += b 
visited = [True for i in range(N)]
def dps(i):
    visited[i] = False
    if i == N :
        return 1
    else :
        for j in graph[i]:
            if visited[j]:
                val[j] += val[i]
                dps(j)
dps(0)
for i in val:
  print(i,end = " ")

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
visit = [False]*N
ans = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x


def dfs(v):
    if not visit[v]:
        visit[v] = True
        for nxt in E[v]:
            ans[nxt] += ans[v]
            dfs(nxt)


dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
graph = {i:[] for i in range(N)}
G = {i:[] for i in range(N)}
ans = [0 for i in range(N)]
c = [0 for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  graph[a-1] += [b-1]
  graph[b-1] += [a-1]
stuck = [0]
log = [0 for i in range(N)]
log[0]=1
ls = [0]
while stuck:
  x = stuck.pop()
  A = graph[x]
  flag = True
  ki = []
  for a in A:
    if log[a]==0:
      stuck+=[a]
      ki+=[a]
      log[a]=1
      flag = False
  for l in ls:
    G[l] += ki
  ls += ki
  if flag:
    ls.remove(x)
for i in range(Q):
  p, x = map(int,input().split())
  p = p-1
  c[p]+=x

for k in G.keys():
  for x in G[k]:
    ans[x]+=c[k]
  ans[k]+=c[k]
A = map(str,ans)
print(' '.join(A))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
value = [0]*(N+1)
tree = [[i] for i in range(N+1)]
for i in range(N-1):
  a, b = map(int, input().split())
  for rel in tree:
    if a in rel:
      rel.append(b)
for i in range(Q):
  a, b = map(int, input().split())
  for arg in tree[a]:
    value[arg] += b
print(' '.join(map(str, value[1:])))

Submission status: Time Limit Exceeded

Solution code:
n, q =  map(int, raw_input().split())
graph = dict()
operation = [0 for i in range(q)]
for i in range(n-1):
    a, b = map(int, raw_input().split())
    if a in graph.keys():
        graph[a].add(b)
    else:
        graph[a] = set([b])
    if b in graph.keys():
        graph[b].add(a)
    else:
        graph[b] = set([a])

for i in range(q):
    operation[i] = [int(j) for j in raw_input().split()]

values = [0 for i in range(n)]

vertex_list = dict()
for i in range(1, n+1):
    vertex_list[i] = set([-1])

def obtain_list(graphx, vertex, check, root):
    check[vertex-1] = True
    vertex_list[root].add(vertex)
    for v in graph[vertex]:
        if check[v - 1] == True:
            continue
        obtain_list(graphx, v, check, root)



# def dfs(graphx, vertex, check, value):
    # check[vertex-1] = True
    # values[vertex-1] += value
    # for v in graph[vertex]:
    #     if check[v - 1] == True:
    #         continue
    #     dfs(graphx, v, check, value)


# for i in range(q):
    # check_list = [False for j in range(n)]
    # ver = operation[i][0]
    # for v in graph[ver]:
    #     if v < ver:
    #         check_list[v-1] = True
    # dfs(graph, operation[i][0], check_list, operation[i][1])

for i in range(1, n+1):
    check_list = [False for j in range(n)]
    for v in graph[i]:
        if v < i:
            check_list[v-1] = True
    obtain_list(graph, i, check_list, i)


for i in range(q):
    p = operation[i][0]
    x = operation[i][1]
    for y in vertex_list[p]:
        if y != -1:
            values[y-1] += x

mapped_values = map(str, values)

result = ""
for i in range(n):
    result += mapped_values[i]
    if i < n - 1:
        result += " "

print(result)

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
visit = [False]*N
ans = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x


def dfs(v, road):
    if not visit[v]:
        visit[v] = True
        for nxt in E[v]:
            ans[nxt] += ans[v]
            dfs(nxt, road[:])


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,Q = list(map(int, input().split(" ")))
v_list = np.zeros(N+1, dtype=np.int)
dic_tree = {}
for i in range(N):
    dic_tree[i+1] = [] 

for i in range(N-1):
    a, b = list(map(int, input().split(" ")))
    dic_tree[a].append(b)
        
for i in range(Q):
    p, x = list(map(int, input().split(" ")))
    
    # v_list[dic_tree[p]] += x # Too Heavy...
    v_list[p] += x

for i in range(N):
    v_list[dic_tree[i+1]] += v_list[i+1]
    if i > 0:
        print(" ", end='') 
    print(v_list[i+1], end='')

Submission status: Time Limit Exceeded

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
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()))

n,q = LI()
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    g[a-1].append(b-1)
for i in range(n):
    g[i].append(i)
ans = [0]*n
que = deque()
for _ in range(q):
    p,x = LI()
    que.append(p-1)
    check = [True]*n
    while que:
        v = que.popleft()
        for i in g[v]:
            if check[i]:
                check[i] = False
                que.append(i)
                ans[i] += x
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
[n,q]=[int(x) for x in input().split()]
ab=[[int(x) for x in input().split()] for _ in range(n-1)]
px=[[int(x) for x in input().split()] for _ in range(q)]
 
bubungi=[[x] for x in range(1,n+1)]
ab.sort()
for node in ab[::-1]:
    bubungi[node[0]-1]=bubungi[node[0]-1]+bubungi[node[1]-1]
 
scores=[0,]*n
for q in px:
    for i in bubungi[q[0]-1]:
        scores[i-1]+=q[1]
 
print(*scores)

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q
for i in range(N-1):
  a[i],b[i] = list(map(int, input().split()))
for i in range(Q):
  p[i],x[i] = list(map(int, input().split()))

node_value = [0]*N

# ----------------------------------
table = [[]]*N
temp = []
for i in range(1,N+1):
    for j in range(N-1):
        if i == a[j]:
            temp.append(b[j])
    table[i-1] = temp
    temp = []
# ----------------------------------

def func(p, x):
    global table
    global node_value
    node_value[p-1] = node_value[p-1] + x

    leaflist =  table[p-1]
    if leaflist != []:
        for leaf in leaflist:
            func(leaf, x)

# ----------------------------------
# summation
for i in range(Q):
    func(p[i], x[i])
# ----------------------------------
    
for node in node_value:
  print(node, end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N,Q=map(int,input().split())
l=[ tuple( map(int,input().split()) ) for i in range(N-1) ]
p=[ tuple( map(int,input().split()) ) for i in range(Q) ]
d=defaultdict(list)
for vert,childs in l:
    d[vert].append(childs)


d_2=defaultdict(int)
for i in range(1,N+1):
    d_2[i]=0

for p,x in p:
    d_2[p]+=x

for n in d_2.keys():
    for m in d[n]:
        d_2[m]+=d_2[n]

ans=d_2.values()
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
edges = [input().split() for _ in range(N-1)]
operations = [input().split() for _ in range(Q)]

tree = {}
result = [0]*N
numbers = []

for o in operations:
    result[int(o[0])-1] += int(o[1])

for e in edges:
    parent = int(e[0])
    sun = int(e[1])

    if sun in numbers:
        result[parent-1] += result[sun-1]
        numbers.append(parent)
    else:
        result[sun-1] += result[parent-1]
        numbers.append(sun)

print(' '.join(map(str, result)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
# 木構造を作る
N,Q  = map(int, input().split())

G = [[] for i in range(N)]
for i in range(N-1):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))



## クエリを持っておく
scores = [0]*N
for i in range(Q):
    p,x = map(int, input().split())
    scores[p-1] += x 

# print(scores)

ans = [0]*N
# DFSするよ
ans[0] = scores[0]
import sys
sys.setrecursionlimit(100000)
used = [False] * N
def dfs(G, v):
   # vを訪問済みにする
   used[v] = True
   #グラフ中の次のVについて
   for next_v in G[v]:
       # すでに見られていたら無視
       if used[next_v]: continue
       # 見られていない場合、再帰的に探索
       ### なにかやりたい処理を書く
       ans[next_v] = ans[v] + scores[next_v]
       dfs(G, next_v)

dfs(G,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(1000000)


def main():
    def read_tree(n):
        tree = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            a, b = [int(x) for x in input().split()]
            tree[a].append(b)
        return tree

    def accumulate(tree, cnt):
        def walk(p, c):
            cnt[p] += c
            for n in tree[p]:
                walk(n, cnt[p])

        walk(1, 0)

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

    tree = read_tree(n)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = [int(x) for x in input().split()]
        cnt[p] += x
    
    accumulate(tree, cnt)

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


main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
edges = [input().split() for _ in range(N-1)]
operations = [input().split() for _ in range(Q)]

tree = {}
result = [0]*N
numbers = []

for o in operations:
    result[int(o[0])-1] += int(o[1])

for e in edges:
    parent = int(e[0])
    sun = int(e[1])

    if sun in numbers:
        result[parent-1] += result[sun-1]
        numbers.append(parent)
    else:
        result[sun-1] += result[parent-1]
        numbers.append(sun)
        
print(' '.join(map(str, result)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

n, q = map(int, input().split())
edge = defaultdict(list)

for i in range(n - 1):
    ai, bi = map(int, input().split())
    edge[ai].append(bi)
    edge[bi].append(ai)

count = defaultdict(int)
for i in range(q):
    pp, xx = map(int, input().split())
    count[pp] += xx


def traverse():
    dq = deque()
    dq.append(1)
    counter = defaultdict(int)
    visited = set()
    while True:
        if len(dq) == 0:
            break
        p = dq.popleft()
        visited.add(p)
        counter[p] += count[p]
        for c in edge[p]:
            if c in visited:
                continue
            counter[c] += counter[p]
            dq.append(c)
    return counter


if __name__ == '__main__':
    counter = traverse()
    print(' '.join([str(counter[i + 1]) for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = [int(i) for i in input().split()]
a1 = {}
a2 = {}
for _ in range(n - 1):
    x, y = [int(i) - 1 for i in input().split()]
    if x in a1:
        a1[x].append(y)
    else:
        a1[x] = [y]
    if y in a2:
        a2[y].append(x)
    else:
        a2[y] = [x]
root = [-1] * n

def c(ind=0, ro=0):
    global root
    if root[ind] != -1:
        return 0
    root[ind] = ro
    if ind in a1:
        for i in a1[ind]:
            if i!=0:
                c(i, ind)
    if ind in a2:
        for i in a2[ind]:
            if i!=0:
                c(i, ind)


c()
p = [0] * n
for _ in range(q):
    x, y = [int(i) for i in input().split()]
    p[x - 1] += y
r = []
for i in range(n):
    j = i
    k = 0
    while True:
        k += p[j]
        if j == 0 and root[j]==0:
            break
        j = root[j]
    r.append(str(k))
print(" ".join(r))

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(i) for i in input().split())
ab = [[int(i) for i in input().split()] for _ in range(n-1)]
child_dict = {}
for i in range(n-2,-1,-1):
    cur = child_dict.get(ab[i][0],set({}))
    cur.add(ab[i][1])
    child_dict[ab[i][0]] = cur

for i, j in child_dict.items():
    for k in range(1,n+1):
        if k in child_dict.keys() and i in child_dict[k]:
            child_dict[k] = child_dict[k].union(j)


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

p = [0] * n

for j in range(q):
    rootidx = px[j][0]
    p[rootidx - 1] += px[j][1]
    if rootidx in child_dict.keys():
        for k in child_dict[rootidx]:
            p[k-1] += px[j][1]

print(*p)

Submission status: Time Limit Exceeded

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

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

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


def dfs(p):
    for c in AB[p]:
        X[c] += X[p]
        dfs(c)


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

Submission status: Time Limit Exceeded

Solution code:
# Setup
import sys
import collections
sys.setrecursionlimit(4100000)

def input():
    return sys.stdin.readline().rstrip()

n,q = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(n-1)]
p = [[int(i) for i in input().split()] for _ in range(q)]

childs = collections.defaultdict(list)

for A,B in a:
    childs[A].append(B)

counter = collections.defaultdict(int)
affections = collections.defaultdict(list)

for A,B in p:
    counter[A] += B
    if affections.get(A):
        continue
    current = A
    aff = []
    tosee = [current]
    while len(tosee) != 0:
        temp = tosee.pop()
        aff.append(temp)
        for z in childs[temp]:
            if affections.get(z):
                aff += affections[z]
            else:
                tosee.append(z)
    affections[A] = aff
counts = collections.defaultdict(int)
for i in range(1,n+1):
    for z in affections[i]:
        counts[z] += counter[i]

ans = ""
for i in range(1,n+1):
    ans += str(counts[i]) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,Q = list(map(int, input().split(" ")))
v_list = np.zeros(N+1, dtype=np.int)
dic_tree = {}
for i in range(N):
    dic_tree[i+1] = [] 

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

# make tree
for k in reversed(range(N)):
    if len(dic_tree) == 0:
        continue
    
    #for node in dic_tree[k+1]:
    #    if len(dic_tree[node]) != 0:
    #        dic_tree[k+1].extend(dic_tree[node])
        
for i in range(Q):
    p, x = list(map(int, input().split(" ")))
    
    # v_list[dic_tree[p]] += x # Too Heavy...
    v_list[p] += x

for i in range(N):
    v_list[dic_tree[i+1]] += v_list[i+1]
    
print(" ".join(map(str, v_list[1:])))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
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)]

chil = [[] for _ in range(N+1)]
count = [0]*(N+1)

for ab in AB:
    chil[ab[0]].append(ab[1])
    chil[ab[1]].append(ab[0])

def cleanse(fromN, toN):
    chil[toN].remove(fromN)
    if len(chil[toN])==0:
        return
    for node in chil[toN]:
        cleanse(toN, node)

for node in chil[1]:
    cleanse(1, node)

for px in PX:
    count[px[0]] += px[1]

for parent in range(1, N+1):
    for child in chil[parent]:
        count[child] += count[parent]

print(*count[1:])

Submission status: Time Limit Exceeded

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

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

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


def dfs(p):
    for c in AB[p]:
        X[c] += X[p]
        dfs(c)


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

Submission status: Time Limit Exceeded

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

cost=[0]*(N+1)

for b in B:
	cost[b[0]]+=b[1]

for a in A:
	cost[a[1]] += cost[a[0]]
print(*cost[1:])

Submission status: Time Limit Exceeded

Solution code:
class TreeObj:
    def __init__(self):
        self.value = 0
        self.childs = []

    def getValue(self):
        return self.value

    def setValue(self, v):
        self.value = v

    def getChilds(self):
        return self.childs

    def addChild(self, node):
        self.childs.append(node)


def appender(tree, v):
    tree.setValue(tree.getValue()+v)
    for child in tree.getChilds():
        appender(child, v)


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

    root = TreeObj()  # 1
    trees = {1: root}   # 1
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        if (a not in trees):
            trees[a] = TreeObj()

        tree = trees[a]
        if (b not in tree.getChilds()):
            trees[b] = child = TreeObj()
            tree.getChilds().append(child)

        tree = None

    for _ in range(Q):
        p, x = list(map(int, input().split()))
        tree = trees[p]
        appender(tree, x)

    tmp = [str(trees[key].getValue()) for key in trees.keys()]
    print(' '.join(tmp))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

d = deque()
def f(tree, counter, arr, n):
  global d
  if not arr:
    return
  for pp in arr if type(arr) == list else arr.popleft():
    if isinstance(tree[pp], list):
      if tree[pp]:
        d.append(tree[pp])
    counter[pp] += n
  if d:
    return f(tree, counter, d, n)

def main():
  N, Q = na()

  tree = [[] for _ in range(N+1)]
  for _ in range(N-1):
    a, b = na()
    tree[a] += [b]

  counter = [0] * (N+1)
  for _ in range(Q):
    p, x = na()
    f(tree, counter, tree[p], x)
    counter[p] += x
  print(*counter[1:])

if __name__ == "__main__":
  import sys
  sys.setrecursionlimit(10000000)

  stdin = sys.stdin
  na = lambda: map(int, stdin.readline().split())
  main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

# 各ノードのリンクを記録
link_dict = dict()
keys = []
for i in range(n-1):
  a,b = map(int, input().split())
  if a in keys:
    link_dict[str(a-1)].add(b)
  else:
    keys.append(a)
    link_dict[str(a-1)] = {b}
  
# 各ノードの部分木の全てのノードをリストアップ
link_set = [set() for i in range(n-1)]
for i in sorted(keys, reverse=True):
  link_set[int(i) - 1] = set(link_dict[str(i-1)])
  if int(i) < n - 1:
    for j in link_dict[str(int(i) - 1)]:
      if j < n - 1:
        link_set[i - 1] = link_set[i - 1] | link_set[j - 1]

# カウンターの計算を実施
counters = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  counters[p - 1] += x
  
children_counters = [0] * n
for i in range(0, n-1):
  for node in link_set[i]:
    children_counters[node - 1] += counters[i]
str_counters = [str(counters[i] + children_counters[i]) for i in range(n)]
print(' '.join(str_counters))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

A = defaultdict(lambda: [])
B = defaultdict(lambda: [])
_px = defaultdict(int)


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

# A = [0 for i in range(N)]
# B = [0 for i in range()]
# A = [{}]
# B = {}

ans = [0 for i in range(N)]
_a = [0 for i in range(N+1)]
PX = []

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

for q in range(Q):
    p, x = map(int, input().split())
    PX.append([p, x])
    _px[p] += x

# print(_px)
# print(A)
# print(B)
# print(PX)
counter = 0
_px = dict(_px)
# print(_px)
def find(x, plus):
    global counter
    for j in x:
        counter += 1
        ans[j-1] += plus
        if _a[j]:
            find(A[j], plus)

# for i in range(1, N):
#     counter += 1
#     ans[i-1] += _px[i]
#     find(A[i], _px[i])

for key, value in _px.items():
    counter += 1
    ans[key-1] += value
    find(A[key], value)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

def input():
    return sys.stdin.readline().rstrip()
 
class Node():
    def __init__(self, val):
        self.val = val
        self.counter = 0
        self.child = []
 
if __name__ == '__main__':
 
    def inorder(node, val):
        if node is None:
            return
        node.counter += val
        for child in node.child:
            inorder(child,val)
 
    n,q = [int(i) for i in input().split()]
    a = [[int(i) for i in input().split()] for _ in range(n-1)]
    p = [[int(i) for i in input().split()] for _ in range(q)]
    nodes = {}
    for i in range(1,n+1):
        temp = Node(i)
        nodes[i] = temp
    for A,B in a:
        nodes[A].child.append(nodes[B])
    for P,X in p:
        inorder(nodes[P],X)
    ans = ""
    for i in range(1,n+1):
        ans += str(nodes[i].counter) + " "
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict

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

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

q = deque()
ans = [0] * (N+1)
ans[1] = P[1]

for t in T[1]:
    q.append([1, t])
while q:
    a, b = q.popleft()
    ans[b] += ans[a] + P[b]
    for t in T[b]:
        q.append([b, t])

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = {}
ans = [0 for i in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  if a in c:
    l = c[a]
  else:
    l = [a]
  l.append(b)
  c[a] = l

for i in reversed(range(n)):
  if i+1 in c:
    ci = c[i+1]
    cj = []
    for j in ci:
      cj_ = c[j]
      cj.extend(cj_)
    cj = list(set(cj))
    c[i+1] = cj
  else:
    c[i+1] = [i+1]

for i in range(q):
  p, x = map(int, input().split())
  for j in c[p]:
    ans[j-1] += x
for i in range(n):   
  print(ans[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
edge = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

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

ans = [0] * n
def dfs(v,p,value): #p: parent of v
    value += cost[v]
    ans[v] = value
    for c in edge[v]:
        if c == p: continue
        dfs(c,v,value)
# def dfs(cur, c, root):
    # # print(cur, c, root)
    # ans[cur] = c
    # for nex in edge[cur]:
        # if nex != root:
            # dfs(nex, c + cost[nex], cur)

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

Submission status: Time Limit Exceeded

Solution code:
N,Q=list(map(int,input().split()))
a=[]
b=[]
for i in range(N-1):
	m,n=list(map(int,input().split()))
	a.append(m)
	b.append(n)
p=[]
x=[]
for i in range(Q):
	m,n=list(map(int,input().split()))
	p.append(m)
	x.append(n)

qs=[0]*N
for i in range(Q):
	qs[p[i]-1]+=x[i]


for i in range(1,N):
	qs[i]+=qs[a[b.index(i+1)]-1]

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