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())
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)
def dfs(i):
    stack = []
    visited[i] = True
    stack.append(i)
    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]

dfs(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:

N,Q = map(int,input().split())
edges = []
for n in range(N-1):
	a,b = map(int,input().split())
	edges.append((a-1,b-1))
edges.sort()
#print(edges)

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

cur = 0
for a,b in edges:
	#print('    ({},{})'.format(a,b))
	while cur<a:
		print('{} '.format(counters[cur]),end='')
		cur += 1
		#print('    up!')
	counters[b] += counters[a]
# remaining nodes
while cur<N:
	print('{} '.format(counters[cur]),end='')
	cur += 1

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict
from bisect import bisect_left


class Solution:
    def main(self):
        path = defaultdict(list)
        N, Q = map(int, input().split())
        freq = [0] * N
        for i in range(N-1):
            ai, bi = map(int, input().split())
            path[ai-1].append(bi-1)
            # path[bi-1].append(ai-1)

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

        stack = [(0, 0)]
        seen = set()
        res = [0] * N
        while stack:
            node, cum = stack.pop(0)
            # seen.add(node)
            val = freq[node] + cum
            res[node] = val
            for other in path[node]:
                # if other not in seen:
                stack.append((other, val))
        print(' '.join(map(str, res)))

if __name__ == '__main__':
    Solution().main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(i) for i in input().split(" ")]
a=[]
b=[]
s=[0]*(N)
for i in range(N-1):
    A,B = [int(i) for i in input().split(" ")]
    a.append(A)
    b.append(B)

for i in range(Q):
    P,X = [int(i) for i in input().split(" ")]
    if P in a:
        for l in range(N):
            if l >= P-1:
                s[l]+= X
    else:
        s[P-1]+=X

for l in range(len(s)):
    if l != len(s)-1:
        print(s[l],end=" ")
    else:
        print(s[l])

Submission status: Time Limit Exceeded

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

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

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

# 隣接リスト
l = [[] for _ in range(n+1)]
for pi in p:
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
p = [0] * (n+1)

import sys
sys.setrecursionlimit(100000)


def dfs(n, v, par):
    p[n] = v
    for chl in l[n]:
        if chl == par:
            continue  # parent
        dfs(chl, v+x[chl], n)
    return

dfs(1, x[1], 0)
print(*p[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

G = dict()
for i in range(1, N + 1):
    G[i] = dict()

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

parents = [0] * (N + 1)
values = [0] * (N + 1)
values_sum = [-1] * (N + 1)

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

# solve
values_sum[1] = values[1]

queue = deque([1])
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if G[p][q] == 1:
            if values_sum[q] == -1:
                values_sum[q] = values_sum[p] + values[q]
                G[q][p] = 0
                queue.append(q)

print(*values_sum[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] +=xi
sp = [0 for i in range(n)]

def f(v,vp,p):
    su = p + px[v]
    sp[v] = su
    for di in d[v]:
        if not di == vp:
            f(di,v,su)
f(0,0,0)
for i in range(n):
    print(sp[i])

Submission status: Time Limit Exceeded

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

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

    if a not in tree_dict:
        tree_dict[a] = [b]
    else:
        tree_dict[a].append(b)

value_dict = {k:0 for k in list(set(ab_list))}

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

    kk_list = [p]
    while(1):
        if len(kk_list) == 0:
            break
        k = kk_list[0]
        value_dict[k] += x
        if k in tree_dict:
            kk_list += tree_dict[k]
        kk_list.pop(0)

print(' '.join([str(v) for k, v in value_dict.items()]))

Submission status: Time Limit Exceeded

Solution code:
import copy
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
l2=[list(map(int,input().split())) for i in range(q)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[0 for i in range(n)]
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
ct=1
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
  ct+=1
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(_) for _ in input().split())  
arr = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
output = [0 for i in range(n)]

for i in range(n-1):
  a, b = (int(_) for _ in input().split()) 
  arr[a-1][b-1] = 1
  for x in range(a-1):
    if arr[x][a-1] == 1:
      arr[x][b-1] = 1

for i in range(q):
  p, q = (int(_) for _ in input().split()) 
  for i, x in enumerate(arr[p-1]):
    if x == 1:
      output[i] += q
    
print(' '.join([str(x) for x in output]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():

    N, Q = [int(x) for x in input().split()]
    counter = {key:0 for key in range(1, N+1)}
    parent_dict = dict()
    child_data = defaultdict(list)
    child_data[1] = [1]

    # 要は木構造っぽいものを作りたいが、再起関数だと処理時間で死んだ
    # なので、親一覧 + 自分のリストを作成する
    for _ in range(N - 1):
        a, b = [int(x) for x in input().split()]
        parent_dict[b] = a
        child_data[b].append(b)
        temp = b
        while temp in parent_dict:
            temp = parent_dict[temp]
            child_data[temp].append(b)
    
    # print(parent_dict)
    # print(child_data)

    # 親一覧 + 自分のリストから答えを出す   
    for _ in range(Q):
        p, x = [int(x) for x in input().split()]
        for key in child_data[p]:
            counter[key] += x

    print(" ".join([str(val) for key, val in sorted(counter.items())]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
ab = [None] * (N - 1)
for i in range(N - 1):
    ab[i] = list(map(int, input().split()))
ab = sorted(ab, key=lambda x: (x[0], x[1]))

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

ans = [0] * N
ans[0] = px_n[0]
for i in range(N - 1):
    a, b = ab[i]
    ans[b-1] += ans[a-1] + px_n[b-1]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
x = list([0] * n for i in range(n))
for _ in range(n-1):
  a,b  = map(int,input().split())
  a -= 1
  b -= 1
  x[a][b] += 1
  x[b][a] += 1
  for i in range(b-1):
    if x[a][i] == 1:
      x[i][b] += 1
shio = [0] *n
for j in range(q):
  a,b =map(int,input().split())
  a -= 1
  shio[a] += b
  for k in range(a,n):
    if x[a][k] == 1:
      shio[k] += b
for i in range(n):
  print(shio[i])

Submission status: Time Limit Exceeded

Solution code:
import copy
n, q = map(int, input().split())
ab = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]

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

count = [0 for _ in range(n)]

def dfs(v, x):
  count[v] += x
  ad = copy.deepcopy(ad_list)
  while len(ad[v]) != 0:
    ad_v = ad[v].pop()
    dfs(ad_v, x)
    if len(ad[v]) == 0:
      break

for p, x in px:
  dfs(p-1, x)

print(*count)

Submission status: Time Limit Exceeded

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

ans=[0]*N
ab=[]

for _ in range(N-1):
    a,b=map(int,input().split())
    ab.append([a-1,b-1])
ab.sort()
    
for _ in range(Q):
    p,x=map(int,input().split())
    todo=[p-1]
    for item in ab:
        if item[0] in todo:
            ans[item[1]]=ans[item[1]]+x
            todo.append(item[1])
    ans[p-1]=ans[p-1]+x
#    print(ans) 

print(str(''.join(str(j)+' ' for j in ans)[:-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n, q = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append(b)
    d[b].append(a)
d2 = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    d2[p] += x

ans = [0] * n

def dfs(cur, pre, point):
    point += d2[cur]
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join([str(item) for item in ans]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
G = [[] for i in range(N+ 1)]
ANS = [0] * (N + 1)
for _ in range(N - 1):
    a , b = map(int,input().split())
    G[a].append(b)
for _ in range(Q):
    p, x =map(int,input().split())
    ANS[p] += x
que=[1]
while que:
    node = que.pop(0)
    ans = ANS[node]
    for child in G[node]:
        ANS[child] += ans
        que.append(child)
for i in range(1, N + 1):
    print(ANS[i])

Submission status: Time Limit Exceeded

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

    tree = [[] for _ in range(N)]
    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

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

    print(*ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N,Q= list(map(int, input().split()))
li1=[list(map(int,input().split())) for _ in range(N-1)]
li2=[list(map(int,input().split())) for _ in range(Q)]
lis=[[i] for i in range(N)]
ans=[0 for _ in range(N)]
li1=sorted(li1,reverse=True)
for i in li1:
    for j in lis[i[1]-1]:
        lis[i[0]-1].append(j)
for i in li2:
    for j in lis[i[0]-1]:
            ans[j]+=i[1]
for i in ans:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
link = dict()
counter = list([0]*n)
for i in range(n-1):
  a, b = map(int, input().split())
  link[b-1] = a-1
        
for i in range(q):
  p,pp = map(int, input().split())
  counter[p-1] += pp
ans = ""
for i in range(n):
    isChild = True
    now = i
    count = counter[now]
    while True:
        if now in link:
            count += counter[link[now]]
            now = link[now]
        else:
            break
    
    if i != n-1:
        ans += str(count) + " "
    else: ans += str(count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
l=[[1]]
ans=[0]*n
ba=sorted([list(map(int,input().split()))[::-1] for i in range(n-1)])
for j in range(n-1):
  a=ba[j][1]
  l.append(l[a-1]+[j+2])
for k in range(q):
  p,x=map(int,input().split())
  for t in range(n):
    if p in l[t]:
      ans[t]+=x
print(*ans,sep=" ")

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)
        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
child_l = node_one.set_tree(0, 0)
children_dictionary[1] = child_l
while len(children_dictionary) != 0:
    key = sorted(children_dictionary.keys())[0]
    parent_add_n = node_list[key-1].add_number
    children_l = children_dictionary.pop(key)
    for child in children_l:
        new_children = node_list[child-1].set_tree(key, parent_add_n)
        children_dictionary[child] = new_children

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
res = []
tree = []
level = []
childs = []
parent = []
for i in range(210000):
    res.append(0)
    tree.append([])
    level.append(-1)
    childs.append([])
    parent.append(-1)


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

def make_level(index, lev):
    l = 0
    level[index] = lev
    for next in tree[index]:
        # 逆走はしない
        if level[next] != -1:
            continue
        # 子供に親を設定
        parent[next] = index
        curparent = index
        add_parent(index, next)

        make_level(next, lev + 1)


def add_parent(index, childindex):
    if index != -1:
        #print("add {0}, {1}".format(index, childindex))
        childs[index].append((childindex))
        add_parent(parent[index], childindex)


make_level(1, 0)
#print(level[0:10])
#print(parent[0:10])
#print(childs[0:10])

for loop in range(q):
    p, x = map(int, input().split())
    res[p] += x
    for childindex in childs[p]:
        res[childindex] += x

res = list(map(str, res))
print(" ".join(res[1:n+1]))

Submission status: Time Limit Exceeded

Solution code:
import copy
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
l2=[list(map(int,input().split())) for i in range(q)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[0 for i in range(n)]
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
oya=0
L2=[]
L3=[]
ct=1
while len(L2)!=3*n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
  ct+=1
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))

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

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi)
    graph[bi - 1].append(ai)

# print("#", graph)

cnttab = [0] * N
for j, (pj, xj) in enumerate(px):
    cnttab[pj - 1] += xj

# print("#", cnttab)

ans = [None] * N
ans[0] = cnttab[0]
from collections import deque
q = deque([(1, None, ans[0])])
while len(q) > 0:
    src, prev, score = q.popleft()
    for dst in graph[src - 1]:
        if dst == prev: continue
        ans[dst - 1] = score + cnttab[dst - 1]
        q.append((dst, src, ans[dst - 1]))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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


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

# print(A)
# print(B)
# print(PX)

def find(x, plus):
    for j in x:
        ans[j-1] += plus
        if _a[j]:
            find(A[j], plus)

for px in PX:
    ans[px[0]-1] += px[1]
    find(A[px[0]], px[1])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
child = [[] for _ in range(n)]
now = [0]
while now != []:
  last = now
  l = len(last)
  now = []
  for i in range(l):
    child[last[i]] = peer[last[i]]
    now += peer[last[i]]
    p = peer[last[i]]
    ll = len(p)
    for ii in range(ll):
      peer[p[ii]].remove(last[i])
mom = ['?' for _ in range(n)]
for i in range(n):
  for x in child[i]:
    mom[x] = i
cnt = [0 for _ in range(n)]
for _ in range(q):
  p,x = map(int,input().split())
  p -= 1
  cnt[p] += x
#print(peer)
#print(child)
#print(mom)
#print(cnt)
ans = cnt
now = [0]
while now != []:
  last = now
  l = len(last)
  now = []
  for i in range(l):
    now += child[last[i]]
    try:
      ans[last[i]] += ans[mom[last[i]]]
    except:
      pass
print(' '.join(list(map(str,ans))))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8


def main():
    N, Q = map(int, input().split())
    A = []
    B = []
    P = []
    X = []
    countList = [0]*N
    # print(N, Q)
    treeParent = [-1] * N
    treeParent[0] = 0
    treeChild = [[] for i in range(N)]

    for i in range(N-1):
        Ai, Bi = map(int, input().split())
        A.append(Ai)
        B.append(Bi)

    while -1 in treeParent:
        for i in range(N-1):
            ai = A[i]
            bi = B[i]
            if treeParent[ai-1] >= 0:
                treeParent[bi-1] = ai
                treeChild[ai-1].append(bi)
            elif treeParent[bi-1] >= 0:
                treeParent[ai-1] = bi
                treeChild[bi-1].append(ai)

    # print(treeParent)
    # print(treeChild)

    for i in range(Q):
        pi, xi = map(int, input().split())
        P.append(pi)
        X.append(xi)
        countList = addCount(pi, xi, treeParent, treeChild, countList)

    for ci in countList:
        print(ci, end=" ")

    print()


def addCount(pi, xi, treeParent, treeChild, countList):
    index = pi
    countList[index - 1] += xi
    nextlist = treeChild[index - 1]
    if not len(nextlist) > 0:
        return countList
    else:
        for child in nextlist:
            countList = addCount(child, xi, treeParent, treeChild, countList)
    return countList


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict
from bisect import bisect_left


class Solution:
    def main(self):
        path = defaultdict(list)
        N, Q = map(int, input().split())
        freq = [0] * N
        for i in range(N-1):
            ai, bi = map(int, input().split())
            path[ai-1].append(bi-1)
            path[bi-1].append(ai-1)

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

        stack = [(0, 0)]
        seen = set()
        res = [0] * N
        while stack:
            node, cum = stack.pop(0)
            seen.add(node)
            val = freq[node] + cum
            res[node] = val
            for other in path[node]:
                if other not in seen:
                    stack.append((other, val))
        print(' '.join(map(str, res)))

if __name__ == '__main__':
    Solution().main()

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
d = {}
score = [0 for _ in range(N)]

# 辞書の初期化
for i in range(1,N+1):
  d[i] = {i}

# 連結情報を取得する
for i in range(1,N):
  a,b = map(int,input().split())
  d[a].add(b)
  for i in range(1,N+1):
    if a in d[i]:
      d[i].add(b)
  
# スコア加算処理
for i in range(1,Q+1):
  p,x = map(int,input().split())
  for elm in d[p]:
    score[elm-1] += x
  
print(*score)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
par=[-1 for i in range(n+1)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す
p=[-1 for i in range(n+1)]
p[1]=0
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    x,y=a,b
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
        x,y=y,x
    par[a]+=par[b]
    par[b]=a
    p[b]=x
    
    return True
ll=[]
for i in range(n-1):
    a=[int(j) for j in input().split()]
    ll.append(a)
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

l=[0 for i in range(n+1)]
for i in range(q):
    r=[int(j) for j in input().split()]
    l[r[0]]+=r[1]

def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)

#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0
par = [-1]*(n+1)
wei = [0]*(n+1)

for i in range(n+1):
    unite(p[i],i,l[i])

print(*wei[1:])

Submission status: Time Limit Exceeded

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

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

    if a not in tree_dict:
        tree_dict[a] = [b]
    else:
        tree_dict[a].append(b)

value_dict = {k:0 for k in list(set(ab_list))}

p_list = []
x_list = []
for i in range(Q):
    p, x = map(int, input().split())
    p_list.append(p)
    x_list.append(x)

for p, x in zip(p_list, x_list):
    f = 0
    kk_list = [p]
    while(1):
        if len(kk_list) == 0:
            f = 1
            break
        k = kk_list[0]
        value_dict[k] += x
        if k in tree_dict:
            kk_list += tree_dict[k]
        kk_list.pop(0)
        if f == 1:
            break

print(' '.join([str(v) for k, v in value_dict.items()]))

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)

# global counter
tree = [0] + [None] * n

def count_tree(num, tree, path, parent):
  l = [num] # self

  for i in path[num]:
    if i == parent:
      continue

    l += count_tree(i, tree, path, num)

  tree[num] = l
  return l

count_tree(1, tree, path, 0)

result = [0] * n

sum = 0
for _ in range(q):
  p, x = map(int, input().split())
  for i in tree[p]:
    result[i - 1] += x

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

G = dict()
for i in range(1, N + 1):
    G[i] = dict()

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

parents = [0] * (N + 1)
values = [0] * (N + 1)
values_sum = [-1] * (N + 1)

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

# solve
values_sum[1] = values[1]

queue = deque([1])
cnt = 0
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if G[p][q] == 1 and values_sum[q] == -1:
            values_sum[q] = values_sum[p] + values[q]
            queue.append(q)
            cnt += 1
    if cnt > 2 * N:
        print(0)

print(*values_sum[1:])

Submission status: Time Limit Exceeded

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

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:
    if affections.get(A):
        for i in affections.get(A):
            counter[i] += B
    else:
        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
        for i in affections[A]:
            counter[i] += B
ans = ""
for i in range(1,n+1):
    ans += str(counter[i]) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input=sys.stdin.readline
    n,q=map(int,input().split())

    edge=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1;v-=1
        edge[u].append(v)

    res=[0]*n

    def solve(p,x):
        que=[p]
        while que:
            p=que.pop()
            res[p]+=x
            for e in edge[p]:
                que.append(e)
        return
    
    px={}
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        px[p]=px.get(p,0)+x

    for p,x in px.items():
        solve(p,x)

    print(*res)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

tree = [[i] for i in range(N+1)]
tree_parent = [[] for i in range(N+1)]
points = [0] * N

for i in range(1, N):
  a, b = map(int, input().split())
  tree[a].append(b)
  tree_parent[b].append(a)  
  for parent in tree_parent[a]:
    tree[parent].append(b)
    
for i in range(Q):
  p, x = map(int, input().split())
  for node in tree[p]:
    points[node-1] += x
    
for point in points:
  print(point, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000000)

class tree:
    def __init__(self):
        self.baby_list=[]
        self.counter=0
    
    def add_value(self, value):
        self.counter += value
        for i in self.baby_list:
            hoge[i].add_value(value)

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


hoge={}

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

for i in range(Q):
    root, value = list(map(int, input().split() ))
    hoge[root].add_value(value)

output = []
for t in hoge:
    output.append(hoge[t].counter)

output = list(map(str, output))
print(" ".join(output))

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

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi)
    graph[bi - 1].append(ai)

# print("#", graph)

cnttab = [0] * N
for j, (pj, xj) in enumerate(px):
    cnttab[pj - 1] += xj

# print("#", cnttab)

ans = [None] * N
ans[0] = cnttab[0]
from collections import deque
q = deque([(1, None, ans[0])])
while len(q) > 0:
    src, prev, score = q.popleft()
    for dst in graph[src - 1]:
        if dst == prev: continue
        ans[dst - 1] = score + cnttab[dst - 1]
        q.append((dst, src, ans[dst - 1]))

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