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())
G = [[] for _ in range(N)]
memo = [[i] for i in range(N)]
flg = [False]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)

ans = [0]*N
add = [0]*N

for i in range(Q):
    p, x = map(int, input().split())
    if not flg[p-1]:
        flg[p-1] = True
        ans[p-1] += x
        queue = [p-1]
        while queue:
            par = queue.pop(0)
            if G[par]:
                for i in G[par]:
                    ans[i] += x
                    queue.append(i)
                    memo[p-1].append(i)
    else:
        add[p-1] += x

ct = 0
for i in flg:
    if i:
        for j in memo[ct]:
            ans[j] += add[ct]
    ct += 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import collections as C
n, q = map(int,input().split())

g = C.Counter([])
p = C.Counter([])
for i in range(n-1):
	a,b = map(int,input().split())
	if a not in g.keys():
		g[a] = [b]
	elif a in g.keys():
		g[a] = g[a] + [b]

for i in range(q):
	a,b = map(int,input().split())
	if a not in p.keys():
		p[a] = b
	elif a in p.keys():
		p[a] = p[a] + b

ans = [0 for _ in range(n)]
que = [0]
i = 1
while i > 0:

	if i in p.keys():
		ans[i-1] += p[i]
	if i in g.keys():
		for j in g[i]:
			ans[j-1] = ans[i-1]
			que.append(j)
	i = que.pop()


for i in ans:
	print(i, end=" ")

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
connect = [[] for _ in range(n)]
count = [0] * n
for i in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].append(b-1)

operate = []
for _ in range(q):
    operate.append(tuple(map(int, input().split())))


effect = [[] for _ in range(n)]
for i in range(n):
    j = i
    while j != n:
        effect[i] += connect[j]
        j += 1

for p, x in operate:
    count[p-1] += x
    effectlist = effect[p-1]
    for k in effectlist:
        count[k] += x
    
for c in count:
    print(c, end = ' ')

Submission status: Time Limit Exceeded

Solution code:


import sys
sys.setrecursionlimit(500000)

def acinput():
    return list(map(int, input().split(" ")))


def search(n):
    global P,res,visited

    for l in L[n]:
        res[l]=res[n]+P[l]
        search(l)

N,Q=acinput()

L=[[]for i in range(N+1)]

for i in range(N-1):

    tmp=acinput()
    L[tmp[0]].append(tmp[1])

P=[0]*(N+1)
for i in range(Q):
    tmp=acinput()
    P[tmp[0]]+=tmp[1]

res=[0]*(N+1)
res[1]=P[1]
search(1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

N,Q = map(int,input().split())
ab_list = [tuple(map(int,input().split())) for _ in range(N-1)]
px_list = [tuple(map(int,input().split())) for _ in range(Q)]

px_dict = {}
for p, x in px_list:
    if p in px_dict:
        px_dict[p] += x
    else:
        px_dict[p] = x

ab_dict = {}
for a,b in ab_list:
    if a in ab_dict:
        ab_dict[a].append(b)
    else:
        ab_dict[a] = [b]

scores = [0 for _ in range(N+1)] # 1子おおい

def add_cnt(v, score):
    # pxdictから持ってきてスコアを足す
    if v in px_dict:
        score += px_dict[v]
    # スコアを足さないこともある
    
    #今いる頂点に現在のスコアをめも
    scores[v] = score
    
    # 繋がっている頂点に今のスコアを投げる
    if v in ab_dict:
        for b in ab_dict[v]:
            add_cnt(b,score)

add_cnt(1,0)

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = (map(int, input().split()))
# 0番目は使わない
node = [[] for i in range(N + 1)]
parent = [[] for i in range(N + 1)]
for i in range(N - 1):
	a, b = (map(int, input().split()))
	node[a].append(b)
	node[b].append(a)
# print(node)

t = [i for i in range(N, 0, -1)]
while len(t) != 1:
	i = t.pop(0)
	# print(len(node[i]))
	if len(node[i]) == 1:
		# print("len = 1")
		parent[node[i][0]].append(i)
		for a in parent[i]:
			parent[node[i][0]].append(a)
		node[node[i][0]].remove(i)
	else:
		t.insert(-1, i)
	# print(t)
		
# print(parent)
ctr = [0 for i in range(N + 1)]
for i in range(Q):
	p, x = (map(int, input().split()))
	ctr[p] += x
	for j in parent[p]:
		ctr[j] += x
		
# print(ctr)
init = 1
for i in ctr:
	if init != 1:
		print(i, end = " ")
	else:
		init = 0

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, q = map(int, input().split())
nodes = [
  {
    'counter': 0
  }
  for _ in range(n)
]

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

roots = []
indices = [0]
while len(edges):
  next_indices = []
  roots.extend(indices)
  for index in indices:
    children = edges.pop(index)
    nodes[index]['children'] = [
      node
      for node in children
      if node not in roots
    ]
    next_indices.extend(nodes[index]['children'])
  indices = next_indices

def count(nodes: dict, p: int, x: int) -> None:
  nodes[p]['counter'] += x
  children = nodes[p]['children']
  if children:
    for child in children:
      count(nodes, child, x)

for _ in range(q):
  p, x = map(int, input().split())
  count(nodes, p-1, x)
  
print(' '.join(map(lambda x: str(x['counter']), nodes)))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)

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

def func(p, now):
    global res
    res[p-1]+=px[p-1]+now
    for i in ab[p-1]:
        func(i, res[p-1])


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

res=[0]*n

func(1, 0)

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

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)
    graph[b].append(a)
checked = set()
check_list = [1]
new_graph = {i + 1:[] for i in range(n)}
while check_list:
    check = check_list.pop(0)
    for i in graph[check]:
        if i not in checked:
            new_graph[check].append(i)
            check_list.append(i)
    checked |= {check}
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 new_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:
n, q = (int(i) for i in input().split())
tree = dict()
for i in range(n-1):
    p, c = (int(j) for j in input().split())
    child = tree.get(p-1, [])
    tree[p-1] = child + [c-1]
cnt = [0]*n
for i in range(q):
    p, x = (int(j) for j in input().split())
    cnt[p-1] = cnt[p-1] + x
q = list([0])
while len(q) > 0:
    idx = q.pop(0)
    child = tree.get(idx, [])
    for c in child:
        cnt[c] = cnt[c] + cnt[idx]
    q = q + child
print(' '.join([str(c) for c in cnt]))

Submission status: Time Limit Exceeded

Solution code:
# クエリはまとめてしまえ
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
ki = [[] for i in range(n)]

def union(a, b):
  # aの子供
  ki[a].append(b)

for i in range(n-1):
  a, b = map(int, input().split())
  union(a-1, b-1)

table = {}
for _ in range(q):
  p, x = map(int, input().split())
  if p-1 not in table:
    table[p-1] = x
  else:
    table[p-1] += x
ans = [0 for _ in range(n)]


def f(k, v, b):
  if len(ki[k])>0:
    # 自分自身
    if b == False:
      ans[k] += v
    for x in ki[k]:
      ans[x] += v
    for x in ki[k]:
      # 再起するときのマーク
      f(x, v, True)
  else:
    if b == False:
      ans[k] += v
for k, v in table.items():
  f(k, v, False)

print(" ".join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
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)]

neigh = {}

for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])

sortKey = sorted(neigh.keys(), reverse=True)

for i in range(len(sortKey)) :
    for j in range(i + i, len(sortKey)) :
        if sortKey[i] in neigh[sortKey[j]] :
            neigh[sortKey[j]] += neigh[sortKey[i]]

ans = [0] * n
#print(neigh)
#print(neigh)

for i in range(q) :
    if px[i][0] in neigh :
        for e in neigh[px[i][0]] :
            ans[e - 1] += px[i][1]
    ans[px[i][0] - 1] += px[i][1]

print(*ans)

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
link = [[] for _ in range(N)]
a = [0] * (N-1)
b = [0] * (N-1)
for i in range(N-1):
    a[i], b[i] = map(int, input().split())

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

for i in range(N-1):
    link[a[i]-1].append([b[i]-1, cost[i]])

nums = [0] * N
def dfs(v, c):
    for nv in link[v]:
        nums[nv[0]] += c + cost[nv[0]]
        dfs(nv[0], c + cost[nv[0]])
    return

nums[0] = cost[0]
dfs(0, cost[0])

print(*nums)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
    N, Q = map(int, input().split())

    # tree = [[] for _ in range(N)]
    tree = defaultdict(list)

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

    for i in range(N-1,-1,-1):
        if tree[i]:
            for j in tree[i]:
                if tree[j]:
                    for k in tree[j]:
                        tree[i].append(k)
    
    ans = [0] * N

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

    for i,j in score.items():
        ans[int(i)] += j
        for k in tree[int(i)]:
            ans[k] += j

    print(*ans)


main()

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 stdin.readline().split()]
            tree[a].append(b)
        return tree

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

    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 stdin.readline().split()]
        walk(p, x)

    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())
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)] 
calc_tree = []

for i in range(n):
  tmp = [i+1]
  for j in range(n-1):
    if tree[j][0] in tmp:
      tmp.append(tree[j][1])
  calc_tree.append(tmp)
#print(calc_tree)
ans = [0] * n
  
for i in range(q):
  order = px[i][0] -1
  for j in calc_tree[order]:
    ans[j-1] += px[i][1]
    
for i in ans:
  print(i,end=' ')

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ed = dict([(i+1,set()) for i in range(n)]) #[[] for i in range(n)]
cd = dict([(i+1,set()) for i in range(n)]) #[[] for i in range(n)]
r = {i+1 for i in range(n)} #[i+1 for i in range(n)]
cnt = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    ed[a].add(b)
    ed[b].add(a)

st = [1]
while len(st) != 0:
    v = st.pop()
    cd[v] = (ed[v] & r)
    for item in list({i+1 for i in range(n)} - set(r)):
        cd[item] = cd[item] | cd[v]
    r.remove(v)
    st += cd[v]

for i in range(q):
    p, x = map(int, input().split())       
    cnt[p-1] += x
    for item in cd[p]:
        cnt[item-1] += x
        
ans = ""
for c in cnt:
    ans += (str(c) + " ")

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

n , q = map(int, input().split())
lab = []
points = [0]*n
for i in range(n-1):
    lab.append(list(map(int, input().split())))
lpx = []
for i in range(q):
    lpx.append(list(map(int, input().split())))

for i in lpx:
    childs = Queue()
    inc = []
    parent = i[0]
    childs.put(parent)
    while childs.qsize() > 0:
        a = childs.get()
        inc.append(a)
        for k in lab:
            if k[0] == a:
                childs.put(k[1])
    setinc = set(inc)

    for j in list(setinc):
        points[j-1] += i[1]
print(' '.join(map(str, points)))

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)]
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 = set([0])
while stuck:
  x = stuck.pop()
  A = graph[x]
  flag = True
  ki = []
  for a in A:
    if log[a]==0:
      stuck += [a]
      for l in ls:
        G[l] += [a]
      ki+=[a]
      log[a]=1
      flag = False
  for k in ki:
    ls.add(k)
  if flag:
    ls.remove(x)
for k in G.keys():
  x = set(G[k])
  G[k]=x
for i in range(Q):
  p, x = map(int,input().split())
  p = p-1
  for l in G[p]:
    ans[l] += x
  ans[p] += x
A = map(str, ans)
print(' '.join(A))

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(x) for x in input().split()]
ab_list = [[int(x) for x in input().split()] for _ in range(N-1)]
px_list = [[int(x) for x in input().split()] for _ in range(Q)]
to = [[] for _ in range(N+1)]
for a, b in ab_list:
    to[b].append(a)
subtree = [[i] for i in range(N+1)]
for j in range(N, 0, -1):
    for u in to[j]:
        subtree[u].extend(subtree[j])
ans = [0] * N
for p, x in px_list:
    for u in subtree[p]:
        ans[u-1] += x
print(' '.join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, Q = map(int, input().split())
ans = np.zeros((N+1), dtype=np.int)
graph = {i:[None, []] for i in range(1, N+1)}
nums = [False] * (N)
visited = [False] * (N+1)

for i in range(N-1):
    a, b = map(int, input().split())
    graph[b][0] = a
    graph[a][1].append(b)
    nums[a-1] = True
        
q = [idx+1 for idx, _ in enumerate(nums) if not _]

while q:
    n = q.pop(0)
    visited[n] = True

    par, child = graph[n]
    if not par is None and not visited[par]:
        graph[par][1].extend(child)
        q.append(par)
        
for i in range(Q):
    p, x = map(int, input().split())
    ans[p] += x
    ans[graph[p][1]] += x
    
for n in ans[1:]:
    print(n, '', end='')

Submission status: Time Limit Exceeded

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

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

ans = [0] * n


for i in range(q):
    p, x = map(int,input().split())
    if (p == 1):
        for j in range(n):
            ans[j] += x
    else:
        br = {p}
        for j in range(p-1,n-1):
            if(ab[j][0] in br):
                br.add(ab[j][1])

        for k in br:
            ans[k-1] += x

[print(i,end=" ") for i in ans]
print()

Submission status: Time Limit Exceeded

Solution code:
import collections as C
n, q = map(int,input().split())

g = C.Counter([])
p = C.Counter([])
for i in range(n-1):
	a,b = map(int,input().split())
	if a not in g.keys():
		g[a] = [b]
	elif a in g.keys():
		g[a] = g[a] + [b]

for i in range(q):
	a,b = map(int,input().split())
	if a not in p.keys():
		p[a] = b
	elif a in p.keys():
		p[a] = p[a] + b

ans = [0 for _ in range(n)]
que = [0]
i = 1
while i > 0:

	if i in p.keys():
		ans[i-1] += p[i]
	if i in g.keys():
		for j in g[i]:
			ans[j-1] = ans[i-1]
			que.append(j)
	i = que.pop()


for i in ans:
	print(i, end=" ")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,Q = inputMap()
	ki = [[] for _ in range(N)]
	kiki = []
	ans = [0 for _ in range(N)]

	for i in range(N-1):
		a,b = inputMap()
		ki[a-1].append(b-1)

	ki2 = ki[::-1]
	for i,val in enumerate(ki2):
		if len(val) == 0:
			kiki.append([])
			continue
		addd = val
		for vol in val:
			tmp = ki[vol]
			addd.extend(tmp)
		kiki.append(addd)

	kiki = kiki[::-1]
	for i in range(Q):
		p,x = inputMap()
		if p == 1:
			for i in range(N):
				ans[i] += x
		else:
			ans[p-1] += x
			for vol in kiki[p-1]:
				ans[vol] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)

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

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

plus = [0] * (n + 1)

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

def calc(num, path, plus, parent):
  for i in path[num]:
    if i == parent:
      continue

    plus[i] += plus[num]
    calc(i, path, plus, num)

calc(1, path, plus, 0)

print(" ".join([str(i) for i in plus[1:]]))

Submission status: Time Limit Exceeded

Solution code:
x,y = map(int,input().split())
set_list=[list(map(int,input().split())) for i in range(x-1)]
point_li=[list(map(int,input().split())) for i in range(y)]
ans_li=[0 for i in range(x)]

def setPoint(n, point):
    rlist=[]
    while True:
        
        for tt in range(x-1):
            if set_list[tt][0]==n:
                ans_li[set_list[tt][1]-1]+=point
                rlist.append(set_list[tt][1])
        if len(rlist)==0:
            break
        n=rlist[0]
        rlist.pop(0)
for i in range(y):
    point=point_li[i][1]
    start=point_li[i][0]
    r=setPoint(start,point)
    ans_li[start-1]+=point
[print(ans_li[i] , end =" ") for i in range(x)]

Submission status: Time Limit Exceeded

Solution code:
N ,Q = map(int,input().split())
tree = []
counters = []
nodes = [0 for i in range(N)]
tree_list = [[] for i in range(N+1)]
for i in range(N-1):
  tree.append(list(map(int,input().split())))
tree = sorted(tree)
for i in range(Q):
  counters.append(list(map(int,input().split())))
for h in tree:
  tree_list[h[0]].append(h[1])

for i in range(len(tree_list)-1,0,-1):
  for j in tree_list[i]:
    tree_list[i].extend(tree_list[j])
  
for p,x in counters:
  nodes[p-1] += x
  for i in tree_list[p]:
    nodes[i-1] += x

for i in nodes:
  print(i,end=' ')

Submission status: Time Limit Exceeded

Solution code:
tmp1 = input().split()
n = int(tmp1[0])
q = int(tmp1[1])
a = [0]*(n-1)
b = [0]*(n-1)
p = [0]*q
x = [0]*q
ans = [0]*n
flag = [0]*n
box = []
for i in range(n-1):
  tmp2 = list(map(int, input().split()))
  box.append(tmp2)
  
#print(box)
box.sort()
#print(box)
for i in range(n-1):
  a[i] = int(box[i][0])
  b[i] = int(box[i][1])
  
for i in range(q):
  tmp3 = input().split()
  p[i] = int(tmp3[0])
  x[i] = int(tmp3[1])
#print(a, b, p, x)

for i in range(q):
  for j in range(n):
    flag[j] = 0
  #どこの頂点が該当するか
  flag[p[i]-1] = 1 #その枝は該当
  j = 0
  for j in range(n-1):
    if flag[a[j]-1]==1 and flag[b[j]-1] == 0:
      flag[b[j]-1] = 1
  #print(flag, x[i])
  for j in range(n):
    if flag[j] == 1:
      ans[j] = ans[j] + x[i]
for i in range(n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
Ki_p = [0 for i in range(N+1)]
Ki_c = [[] for i in range(N+1)]
Ki_co = [0 for i in range(N+1)]

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

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

ans = [0 for i in range(N+1)]
vc = [1]
for i in range(N):
    vi = vc.pop(0)
    ans[vi] = Ki_co[vi] + ans[Ki_p[vi]]
    vc += Ki_c[vi]

print(' '.join(map(str,ans[1:N+1])))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(700000)

def setD(d, N):
    for i in range(N):
        d[i] = setsub(d, i)
            
def setsub(d, i):
    tmp = deque()
    for x in d[i]:
        tmp.append(x)
        if d[x] != 0:
            tmp += setsub(d, x)
    return tmp

N, Q = map(int, input().split())
d = defaultdict(deque)

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

setD(d, N)

ans = [0 for i in range(N)]

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


for i in range(N):
    ans[i] = str(ans[i])
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(a) for a in input().split()]

class Tree:
    def __init__(self):
        self.childs = []
        self.counter = 0

trees = [Tree() for _ in range(N+1)]

a = []
b = []

for _ in range(N-1):
    aa, bb = [int(a) for a in input().split()]
    a.append(aa)
    b.append(bb)
    if aa == 1:
        trees[1].childs.append(bb)
    if bb == 1:
        trees[1].childs.append(aa)



def append_child(tree, parent_id):
    for child in tree.childs:
        for j in range(N-1):
            if a[j] == child:
                if b[j] != parent_id:
                    trees[child].childs.append(b[j])
            if b[j] == child:
                if a[j] != parent_id:
                    trees[child].childs.append(a[j])
        append_child(trees[child], child)

append_child(trees[1], 1)


def count_up(tree, qq):
    tree.counter += qq
    for child in tree.childs:
        count_up(trees[child], qq)

for _ in range(Q):
    pp, qq = [int(a) for a in input().split()]
    count_up(trees[pp], qq)

print(" ".join([str(tree.counter) for tree in trees[1:]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def get_descendants(childrens, dc, i):
  if dc[i] is not None:
    return dc[i]
  if childrens[i] is None:
    return []
  dc[i] = []
  dc[i].extend(childrens[i])
  for j in childrens[i]:
    dc[i].extend(get_descendants(childrens, dc, j))
  return dc[i]
n, q = map(int, input().split())
values = [0] * (n + 1)
childrens = [None] * (n + 1)
dc = [None for i in range(0, n + 1)]
for i in range(n - 1):
  a, b = map(int, input().split())
  if childrens[a] is None:
    childrens[a] = []
  childrens[a].append(b)
for _ in range(q):
  p, x = map(int, input().split())
  values[p] += x
  for d in get_descendants(childrens, dc, p):
    values[d] += x
print(*[values[i] for i in range(1, n + 1)])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = map(int, input().split())
nodes = [0]*(N+1)
tree = [set() for _ in range(N+1)]
subtree = [set() for _ in range(N+1)]

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

def add(p, x):
  dq = deque()
  dq.append(p)
  subtree[p] = {p}
  while len(dq) > 0:
    tp = dq.popleft()
    nodes[tp] += x
    for np in tree[tp]:
      dq.append(np)
      subtree[p].add(np)

for i in range(Q):
  p, x = map(int, input().split())
  if subtree[p]:
    for j in subtree[p]:
      nodes[j] += x
  else:
    add(p, x)
print(" ".join([str(i) for i in nodes[1:]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

N, Q = map(int, input().split())
children = [[i] for i in range(N)]  # 各頂点の持つ部分木の頂点の集合
edges = [list(map(int, input().split())) for _ in range(N-1)][::-1]
counts = np.zeros(N, dtype=np.int32)

for a, b in edges:
    children[a-1] += children[b-1]

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

for count in counts:
    print(count, end=' ')

Submission status: Time Limit Exceeded

Solution code:
np = input().split()
N = int(np[0])
Q = int(np[1])


class Node:

    def __init__(self, number_id):
        self.number_id = number_id  # int
        self.connection_list = []  # つながりのあるidのリスト
        self.parent_id = None
        self.children_list = []
        self.add_number = 0

    def add_add_number(self, add_n):
        self.add_number += add_n

    def add_connection(self, connect_id):
        self.connection_list.append(connect_id)

    def set_tree(self, parent_id, add_n):
        self.parent_id = parent_id
        self.add_number += add_n
        for child_d in self.connection_list:
            if child_d != parent_id:
                self.children_list.append(child_d)
        self.connection_list = []
        return self.children_list


# 読み込んでグラフを作成
# ノード間のつながりができてから，親と子を決定する
node_list = [Node(i+1) for i in range(N)]
for _ in range(N-1):
    ab = input().split()
    a = int(ab[0])
    b = int(ab[1])
    a_node = node_list[a-1]
    b_node = node_list[b-1]
    a_node.add_connection(b)
    b_node.add_connection(a)

# ノードごとに足される数を保存する
for _ in range(Q):
    px = input().split()
    p = int(px[0])
    x = int(px[1])
    p_node = node_list[p-1]
    p_node.add_add_number(x)
# のーど1からノードにあるadd numberを足していく
# node 1 から親子関係を決定する
node_one = node_list[0]
children_dictionary = {}  # key:parent id, value: children list
key_list = [1]
child_l = node_one.set_tree(0, 0)
children_dictionary[1] = child_l
counter = 0
while len(children_dictionary) != 0:
    # key = sorted(children_dictionary.keys())[0]
    key = key_list.pop(0)
    parent_add_n = node_list[key-1].add_number
    children_l = children_dictionary.pop(key)
    for child in children_l:
        counter += 1
        if counter > N:
            exit()
        new_children = node_list[child-1].set_tree(key, parent_add_n)
        children_dictionary[child] = new_children
        key_list.append(child)

# 出力
for node in node_list:
    print(node.add_number, end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


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

ab = [list(map(int,input().split())) for i in range(N-1)]
ab = sorted(ab, reverse=True)
pq = [list(map(int,input().split())) for i in range(Q)]
tree = {}
ans = [0]*N

for pair in ab:
    if pair[0] not in tree:
        tree[pair[0]] = [pair[1]]
    else:
        tree[pair[0]].append(pair[1])
    if pair[1] in tree:
        for i in range(len(tree[pair[1]])):
            tree[pair[0]].append(tree[pair[1]][i])

for pair in pq:
    ans[pair[0]-1] += pair[1]

    if pair[0] in tree:
        for i in tree[pair[0]]:
            ans[i-1] += pair[1]

for i in ans:
    print(i, end=' ')

print()

Submission status: Time Limit Exceeded

Solution code:

NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])

tree_dict = {
    N: {
        'count': 0,
        'has_trees': []
    }
}

def f(p,x):
    tree_dict[p]['count'] += x
    for num in tree_dict[p]['has_trees']:
        f(num,x)

candidate_list = []

#Make tree dict
for _ in range(N-1):
    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])
    candidate_list.append((a,b))

candidate_list.reverse()

for candidate in candidate_list:

    a = candidate[0]
    b = candidate[1]
    if b not in tree_dict.keys():
        tree_dict[b] = {
                'count': 0,
                'has_trees': []
            }

    if a not in tree_dict.keys():
        tree_dict[a] = {
                'count': 0,
                'has_trees': tree_dict[b]['has_trees'] + [b]
            }
    else:
        tree_dict[a]['has_trees'] += tree_dict[b]['has_trees'] + [b]

for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    tree_dict[p]['count'] += x
    for num in tree_dict[p]['has_trees']:
        tree_dict[num]['count'] += x

out_put_list = []
for each_dict in tree_dict.values():
    out_put_list.append(str(each_dict['count']))
print(' '.join(out_put_list))

Submission status: Time Limit Exceeded

Solution code:
class Node():
    def __init__(self):
        self.next = []
        self.counter = 0
        self.parent = None
        self.child_num = 1

    def add(self, x):
        if len(self.next) != 0:
            for sn in self.next:
                sn.add(x)
        self.counter += x

n, q = map(int, input().split(' '))
nodes = [Node() for _ in range(0, n)]
ab = []
for _ in range(0, n-1):
    a, b = map(int, input().split(' '))
    ab.append((a, b))

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

# 構築
for a, b in ab:
    nodes[a-1].next = nodes[b - 1]
    nodes[b-1].parent = nodes[a-1]
    nodes[b-1].counter += nodes[a-1].counter

# for node in nodes[::-1]:
#     if node.parent is not None:
#         node.parent.child_num += node.child_num
#     node.counter *= node.child_num
#

count = 0
for node in nodes:
    count += 1
    print(node.counter, end='')
    if count != n:
        print(' ', end='')

print()