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())
glp = [[] for i in range(N+1)]
counter = [0]*N

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

for i, g in enumerate(glp):
    for gi in g:
        glp[i].extend(glp[gi])

for i in range(Q):
    p, x = map(int, input().split())
    for pi in glp[p]:
        counter[pi-1] += x
    counter[p-1] += x
    
print(" ".join(map(str,counter)))

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

N, Q = LI()
AB = []
PX = []
for i in range(N-1):
    AB.append(LI())

for i in range(Q):
    PX.append(LI())

"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？


"""

AB = sorted(AB, key=lambda x: x[1], reverse=True)

perr('AB')
perr(AB)
d = {}
for a, b in AB:
    # abの頂点若い方に足していく
    if a not in d.keys():
        d[a] = []
    if b not in d.keys():
        d[a].append(b)
    else:
        d[a].append(b)
        d[a].extend(d[b])

perr('d')
perr(d)

#  ans = [0 for _ in range(N)]
items_to_add = [0 for _ in range(N)]
for p, x in PX:
    items_to_add[p-1] += x
perr(items_to_add)

ans = {}
for idx, item in enumerate(items_to_add):
    if idx+1 not in ans.keys():
        ans[idx+1] = 0

    ans[idx+1] += item
    if idx+1 not in d.keys():
        continue
    for i in d[idx+1]:
        if i not in ans.keys():
            ans[i] = 0
        perr('i')
        perr(i)
        ans[i] += item

#  for p, x in PX:
#      perr('px')
#      perr([p, x])
#      ans[p-1] += x
#      if p not in d.keys():
#          continue
#      for i in d[p]:
#          perr('i')
#          perr(i)
#          ans[i-1] += x

perr('ans')
perr(ans)
for i in range(1, N+1):
    print(ans[i], end=' ')

Submission status: Time Limit Exceeded

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

for node in sorted(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(" ".join([str(s) for s in scores]))

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

for i in range(n-1):
  tmp2 = input().split()
  a[i] = int(tmp2[0])
  b[i] = int(tmp2[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
  while j < n-1:
    if flag[a[j]-1]==1 and flag[b[j]-1] == 0:
      flag[b[j]-1] = 1
      j = 0
      continue
    j = j +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:
from collections import deque
n,q=map(int,input().split())
lst=[set() for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    lst[a-1].add(b-1)
lq=[list(map(int,input().split())) for _ in range(q)]
ans=[0 for i in range(n)]
for i in lq:
    queue = deque([i[0]-1])
    while queue:
        x = queue.popleft()
        ans[x]+=i[1]
        for j in lst[x]:
            queue.append(j)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class Tree:
    def __init__(self, r):
        self.r = r
        self.count = 0
        self.children = []

    def append_child(self, c):
        self.children.append(c)

    def add_count(self, x):
        self.count += x
        for c in self.children:
            c.add_count(x)

    def __repr__(self):
        return "<{:d}>".format(self.r)


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

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

nodes = [Tree(r) for r in list(set(A + B))]
edges = list(zip(A, B))
edges.sort(key=lambda x: x[0])

for a, b in edges:
    nodes[a - 1].append_child(nodes[b - 1])

for p, x in zip(P, X):
    nodes[p - 1].add_count(x)

print(" ".join([str(n.count) for n in nodes]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(4100000)
    input = sys.stdin.readline
    
    def add_q(x):
        ans[x-1] += j
        l = tree[x]
        if l:
            for node in l:
                add_q(node)
            
    n,q = map(int,input().strip().split())
    edge = [tuple(map(int,input().strip().split())) for _ in range(n-1)]
    queri = [tuple(map(int,input().strip().split())) for _ in range(q)]
    tree = {}
    ans = [0]*n
    for i in range(n):
        tree[i+1] = []
    for i in edge:
        tree[i[0]].append(i[1])
    for i,j in queri:
        add_q(i)
    print(" ".join([str(i) for i in ans]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000)
n,q=map(int,input().split())
g=[[i] for i in range(n+1)]

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

c=[0]*(n+1)
def dfs(p,x):
    for i in g[p]:
        if r[i]:
            r[i]=0
            c[i]+=x
            dfs(i,x)

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


print(*c[1:])

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 = [None] * Q
for i in range(Q):
    px[i] = list(map(int, input().split()))
px = sorted(px, key=lambda x: (x[0], x[1]))

ans = [0] * N
ans[0] = sum([x for (p, x) in px if p == 1])
for i in range(N - 1):
    a, b = ab[i]
    ans[b-1] += ans[a-1] + sum([x for (p, x) in px if p == b])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
class Node:
  def __init__(self, n):
    self.number = n
    self.children = []
    self.value = 0
def get_descendants(nodes, dc, i):
  if dc[i] is not None:
    return dc[i]
  dc[i] = []
  dc[i].extend(nodes[i].children)
  for j in nodes[i].children:
    dc[i].extend(get_descendants(nodes, dc, j))
  return dc[i]
n, q = map(int, input().split())
nodes = [Node(i) for i in range(0, n + 1)]
nodes[0] = None
dc = [None for i in range(0, n + 1)]
for i in range(n - 1):
  a, b = map(int, input().split())
  nodes[a].children.append(b)
for _ in range(q):
  p, x = map(int, input().split())
  nodes[p].value += x
  for d in get_descendants(nodes, dc, p):
    nodes[d].value += x
print(' '.join(str(nodes[i].value) for i in range(1, n + 1)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
anslist = [0 for _ in range(N)]
treedic = [ [j+1] for  j in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    for k in treedic:
        if a in k:
            if b in k:
                break
            else:
                k.append(b)

#print(treedic)

for u in range(Q):
    p, q = map(int, input().split())
    for v in treedic[p-1]:
        anslist[v-1] += q

for w in anslist:
    print(w, end=' ')

Submission status: Time Limit Exceeded

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

ans = [0]*N

for i in range(Q):
    p, x = map(int, input().split())
    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)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
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 = {i for i in range(1, N+1)}
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)
    if a in nums:
        nums.remove(a)

q = [(0, n) for n in nums]

while q:
    x, n = heapq.heappop(q)
    
    if not visited[n]:
        visited[n] = True
        par, child = graph[n]
        
        if not par is None:
            graph[par][1].extend(child)
        
            heapq.heappush(q, (x+1, 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 = [int(x) for x in input().split() ]
count = [0 for x in range(n+1)]
tree = [[] for x in range(n+1)]
for i in range(1,n):
    arr = [int(x) for x in input().split()]
    tree[arr[0]].append(arr[1])
incre =[0 for x in range(n+1)]
number = set()
for i in range(q):
    arr = [int(x) for x in input().split()]
    incre[arr[0]] += arr[1]
    number.add(arr[0])
    
    

for x in number:
    temp= [x]
    visit = [0 for x in range(n+1)]
    visit[x] = 1
    count[temp[0]] += incre[x]
    while temp != []:
        visit[temp[0]] =1
        for y in tree[temp[0]]:
            count[y] += incre[x]
            if visit[y] == 0:
                temp.append(y)
        del temp[0]
        
for i in range(1,n+1):
    print(count[i], end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:

N,Q = map(int,input().split())
edges = []*N
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:
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
    for k, v in value_dict.items():
        if k == p:
            kk_list = [k]
            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:
N, Q = map(int,input().split())
G = [[] for i in range(N+ 1)]
CNT = [[] for i in range(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())
    CNT[p].append(x)
que=[1]
ANS = [0] * (N + 1)
while que:
    node = que.pop(0)
    _sum = sum(CNT[node])
    ANS[node] = _sum
    for child in G[node]:
        CNT[child].append(_sum)
        que.append(child)
for i in range(1, N + 1):
    print(ANS[i])

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    graph = defaultdict(list)
    scores = defaultdict(int)
    N, Q = l_inpl()
    for _ in range(N-1):
        a, b = l_inpl()
        graph[a].append(b)
    for _ in range(Q):
        p, x = l_inpl()
        scores[p] += x

    ans = [0] * N
    def dfs(graph, node_start, visited, scores, score):
        if node_start in visited:
            return visited
        visited.append(node_start)
        score += scores[node_start]
        ans[node_start-1] = score
        for node_end in graph[node_start]:
            dfs(graph, node_end, visited, scores, score)
        return visited

    dfs(graph, 1, [], scores, 0)
    for s in ans:
        print(s)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

import sys
sys.setrecursionlimit(100000)

# N <= 2*10^5
# Q <= 2*10^5
N, Q = [int(x) for x in stdin.readline().rstrip().split()]
#ab = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]
#px = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]

ans = [0] * (N+1)
child = []
for _ in range(N+1):
    child.append([])

def add(node, num):
    for x in child[node]:
        add(x, num)

    ans[node] += num

for a, b in [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]:
    child[a].append(b)

#print(child)

for p, x in [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]:
    add(p, x)

print(*ans[1:], sep=" ")

Submission status: Time Limit Exceeded

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


class Node:
    def __init__(self, index):
        self.index = index
        self.point = 0

    def updatePoints(self, point):
        self.point += point

nodes = [Node(i) for i in range(1, n + 1)]


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


def selectNode(p):
    selected = [p]
    parent = []
    for a, b in edges:
        if a == p:
            selected.append(b)
            parent.append(b)
    while parent != []:
        for pnode in parent:
            for a, b in edges:
                if pnode == a:
                    selected.append(b)
            parent.remove(pnode)

    return selected

for _ in range(q):
    p, x = map(int, input().split())
    node_index_list = selectNode(p)
    for idx, node in enumerate(nodes):
        if idx + 1 in node_index_list:
            node.updatePoints(x)

print(*(node.point for node in nodes))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(100000000)

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

# n = 2 * 10 ** 5
# k = 2 * 10 ** 5
# ls = [[i + 1, i + 2] for i in range(n - 1)]
# qs = [[i + 1, 10] for i in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

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

def dfs(x, v):
	global ans
	ans[x] = ws[x] + v
	if len(ds[x]) > 0:
		for nxt in ds[x]:
			dfs(nxt, ans[x])

dfs(0, 0)

#print(ws)
#print(ds)

for i in range(n):
	print(ans[i])

Submission status: Time Limit Exceeded

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

adj = {}
val = [0 for i in range(N+1)]
ans = [0 for i in range(N+1)]
check = [False for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    if a not in adj:
        adj[a] = []
    if b not in adj:
        adj[b] = []
    adj[a].append(b)
    adj[b].append(a)

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

queue = [(1,0)]

while len(queue):
    q, c = queue.pop()
    check[q]=True
    ans[q] = val[q] + c
    for nq in adj[q]:
        if check[nq] == False:
            queue.append((nq,ans[q]))

print(*ans[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)]
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)
  while len(dq) > 0:
    p = dq.popleft()
    nodes[p] += x
    for np in tree[p]:
      dq.append(np)

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
AB = [None] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    AB[i] = (a, b)
PX = [None] * (Q)
for i in range(Q):
    p, x = map(int, input().split())
    PX[i] = (p, x)
    
edges = AB[:]
vals = PX[:]

from collections import defaultdict
vals_dict = defaultdict(lambda: 0)
for v, n in vals:
    vals_dict[v] += n
#print(vals_dict)

graph = defaultdict(lambda: {})
for a, b in edges:
    graph[a][b] = vals_dict[b]
    graph[b][a] = vals_dict[a]
#print(graph)
    

from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, 1, N)
shortest = [s+vals_dict[1] for s in shortest]
#print(shortest)
ans = ' '.join(map(str, shortest[1:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
N,Q = map(int,input().split())
 
tree = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
 
adds = defaultdict(int)
for q in range(Q):
    p,x = map(int,input().split())
    adds[p] += x
 
def dig(i,tmp):
    tmp += adds[i]
    ans[i] = tmp
    for v in tree[i]: dig(v,tmp)
 
ans = defaultdict(int)
tmp = 0
dig(1,tmp)
 
for i in range(1,N+1):
    print(ans[i], end=' ')
print()

Submission status: Time Limit Exceeded

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

    graph = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        if a not in graph: graph[a] = [b]
        else: graph[a].append(b)
        # if b not in graph: graph[b] = [a]
        # else: graph[b].append(a)

    ops = dict()
    for i in range(Q):
        p, x = map(int, input().split())
        if p not in ops: ops[p] = x
        else: ops[p] += x

    # print(graph)
    # print(ops)
    vals = [0 for _ in range(N)]
    v = 0
    if 1 in ops: v = ops[1]
    cur = [[1, v]]

    while cur:
        temp = []
        for a, v in cur:
            vals[a-1] += v
            if a in graph:
                for b in graph[a]:
                    if b in ops:
                        temp.append([b, v+ops[b]])
                    else:
                        temp.append([b, v])
        cur = temp

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    num[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])
def unite(x,y):
  if (y<x):
    par[x]=y
  else:
    par[y]=x
def same(x,y):
  return find(x)==find(y)
def cnt(x,tmp):
  res = tmp + num[x]
  if par[x]==x:
    return res
  else:
    return cnt(par[x],res)


N,Q = IL()
ab = [IL() for i in range(N-1)]
px = [IL() for i in range(Q)]

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

init(N)

for a,b in ab:
  unite(a,b)

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

ans = []
for i in range(1,N+1):
  ans.append(cnt(i,0))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

# print(edge)
# print(counter)

visited = [False] * (N + 1)
ans = [0] * (N + 1)

def dfs(fro, p):
    visited[fro] = True
    now = counter[fro] + p
    for to in edge[fro]:
        if not visited[to]:
            dfs(to, now)
    ans[fro] = now
    return

dfs(1, 0)

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import collections
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]:
                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:
N, Q = map(int, input().split())
order_dict = {}
reversed_dict = {}
Q_dict = {}
have_relationlist = {}
ans = []
for i in range(N):
    if i != 0:
        a, b = map(int, input().split())
        if not a in order_dict:
            order_dict[a] = set()
        if not b in reversed_dict:
            reversed_dict[b] = set()
        order_dict[a].add(b)
        reversed_dict[b].add(a)
    ans.append(0)
    have_relationlist[i+1] = set()
    have_relationlist[i+1].add(i+1)

for b in reversed(range(2, N+1)):
    for a in reversed_dict[b]:
        if a in order_dict:
            have_relationlist[a] |= order_dict[a]
        have_relationlist[a] |= have_relationlist[b]

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

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

Submission status: Time Limit Exceeded

Solution code:

N, Q = list(map(int, input().split()))
tree = [dict() for i in range(N)]
for i in range(N):
	tree[i]["edge"] = []
	tree[i]["ope"] = 0
	tree[i]["score"] = 0
	tree[i]["parent"] = -1

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

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

que = []
que.append(0)
tree[0]["score"] = tree[0]["ope"]
for ss in range(N - 1):
	loc = que.pop()
	for edge in tree[loc]["edge"]:
		if tree[loc]["parent"] != edge:
			tree[edge]["score"] += tree[loc]["score"] + tree[edge]["ope"]
			que.append(edge)
			tree[edge]["parent"] = loc

for i in range(N - 1):
	print(tree[i]["score"], end = "")
	print(" ", end = "")
print(tree[N - 1]["score"])

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

N, Q = LI()
AB = []
PX = []
for i in range(N-1):
    AB.append(LI())

for i in range(Q):
    PX.append(LI())

"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？


"""

AB = sorted(AB, key=lambda x: x[1], reverse=True)

perr('AB')
perr(AB)
d = {}
for a, b in AB:
    # abの頂点若い方に足していく
    if a not in d.keys():
        d[a] = []
    if b not in d.keys():
        d[a].append(b)
    else:
        d[a].append(b)
        d[a].extend(d[b])

perr('d')
perr(d)

ans = [0 for _ in range(N)]
items_to_add = [0 for _ in range(N)]
for p, x in PX:
    items_to_add[p-1] += x
perr(items_to_add)

for idx, item in enumerate(items_to_add):
    ans[idx] += item
    if idx+1 not in d.keys():
        continue
    for i in d[idx+1]:
        perr('i')
        perr(i)
        ans[i-1] += item

#  for p, x in PX:
#      perr('px')
#      perr([p, x])
#      ans[p-1] += x
#      if p not in d.keys():
#          continue
#      for i in d[p]:
#          perr('i')
#          perr(i)
#          ans[i-1] += x

perr('ans')
perr(ans)
for a in ans:
    print(a, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    num[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])
def unite(x,y):
  if (y<x):
    par[x]=y
  else:
    par[y]=x
def same(x,y):
  return find(x)==find(y)
def cnt(x,tmp):
  res = tmp + num[x]
  if par[x]==x:
    return res
  else:
    return cnt(par[x],res)


N,Q = IL()
ab = [IL() for i in range(N-1)]
px = [IL() for i in range(Q)]

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

init(N)

for a,b in ab:
  unite(a,b)

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

ans = []
for i in range(1,N+1):
  ans.append(cnt(i,0))

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

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split(" "))
A = [[0,1,0]]
B = []
for i in range(N-1):
    A.append(list(map(int,input().split(" "))))
    A[i+1].append(0)
for j in range(Q):
    B.append(list(map(int,input().split(" "))))

for j in range(Q):
    tmp=[]
    for i in range(N):
        if A[i][1]==B[j][0] or A[i][0]==B[j][0] or A[i][0] in tmp:
            A[i][2]+=B[j][1]
            tmp.append(A[i][1])


for i in range(N):
    print(A[i][2],end=" ")

Submission status: Time Limit Exceeded

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


def main():
    n, q = map(int, input().split())
    e = [list(map(int, input().split())) for _ in range(n-1)]
    p = [list(map(int, input().split())) for _ in range(q)]

    e2 = [[] for _ in range(n)]
    for ee in e:
        a, b = ee
        e2[a-1].append(b-1)
        e2[b-1].append(a-1)

    counters = [0 for _ in range(n)]
    for pp in p:
        counters[pp[0]-1] += pp[1]

    used = set()

    def dfs(x, p_sum):
        used.add(x)
        counters[x] += p_sum
        for y in e2[x]:
            if y in used:
                continue
            dfs(y, counters[x])

    dfs(0, 0)
    print(*counters)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N,Q = map(int,input().split())
T = [[] for i in range(N+1)]
V = [0]*(N+1)
for _ in range(N-1):
    a,b = map(int,input().split())
    T[a].append(b)
for _ in range(Q):
    p,x = map(int,input().split())
    V[p]+=x
def f(v,p):
    global T,V
    for c in T[v]:
        if c==p:continue
        V[c]+=V[v]
        f(c,v)
f(1,0)
print(*V[1:])