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:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

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

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)

    f(weights[0], 0)
    for a in ans:
        print(a, end=' ')
    print()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


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 = deque()
que.append(0)
tree[0]["score"] = tree[0]["ope"]
while len(que) > 0:
	loc = que.popleft()
	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 sys

sys.setrecursionlimit(33333)

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

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

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


visited = [False]*n


def dfs(v, p_cnt):
    if visited[v]:
        return
    visited[v] = True
    cnt[v] += p_cnt
    for nv in tree[v]:
        dfs(nv, cnt[v])


dfs(0, 0)
print(' '.join(map(str, cnt)))

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 dfs(graph, node_start, visited, scores, score, ans):
    if node_start in visited:
        return visited
    visited.append(node_start)
    score += scores[node_start]
    ans.append([node_start, score])
    for node_end in graph[node_start]:
        dfs(graph, node_end, visited, scores, score, ans)
    return visited, ans

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 = dfs(graph, 1, [], scores, 0, [])
    ans.sort()
    for _, s in ans:
        print(s)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

roots = [None] * N
roots[0] = 0

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

V = [0] * N

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

FLAGS = [False] * N
FLAGS[0] = True

def get_value(pos):
    if FLAGS[pos]:
        return V[pos]
    else:
        V[pos] += get_value(roots[pos])
        FLAGS[pos] = True
        return V[pos]

for i in range(N):
    print(get_value(i), end=' ')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)


## input
N,Q = map(int, sys.stdin.readline().rstrip().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, sys.stdin.readline().rstrip().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, sys.stdin.readline().rstrip().split())
  cnt[p-1] += x

## solve
@lru_cache(maxsize=1000)
def dfs(p,q):
  if p in route[q]:
    route[q].remove(p)
  for r in route[q]:
    cnt[r] += cnt[q]
    dfs(q,r)

dfs(-1,0)
for c in cnt[:-1]:
  print(c,end=" ")
print(cnt[-1])

Submission status: Time Limit Exceeded

Solution code:
# ★頂点1からdfsを始めればよいので、 自分の親はどれで子はどれなのか分からなくてもできる！

# 再帰関数の呼び出し回数が多くなる時はこれが必要！！無いとruntime errorになる。
import sys
sys.setrecursionlimit(200000+10)

# 木の深さ優先探索
def add_edge(u, v):
	G[u].append(v)
	G[v].append(u)

def dfs(vertex):
	global counters
	global visited

	visited[vertex] = True


	for v in G[vertex]:
		if visited[v]: 
			#探索済み
			pass
		else:
			# 子のに自分の値を足す
			counters[v] += counters[vertex]
			dfs(v)


n, n_query =  list(map(int, input().split() ))

edges = [list(map(int, input().split())) for _ in range(n-1)]
visited = [False] * n
counters = [0] * n

G = [[] for _ in range(n)] #グラフの隣接リスト表現
for edge in edges:
	add_edge(edge[0]-1, edge[1]-1)

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

dfs(0)

for i in range(n):
	print(counters[i], end=" ")

Submission status: Time Limit Exceeded

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

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

ans = [0] * n
def dfs(cur, c, parent):
    c += cost[cur]
    ans[cur] = c
    for next in edge[cur]:
        if next != parent:
            dfs(next, c, cur)

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
edge_from = [[] for _ in range(N)]
cnt = [0]*N
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge_from[a].append(b)
#print(edge_from)
def count(v, x):
    q = [v]
    while q != []:
        w = q.pop()
        cnt[w] += x
        q += [x for x in edge_from[w]]
            
for i in range(Q):
    p, x = map(int,input().split())
    count(p-1, x)
for i in range(N):
    print(cnt[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, q = map(int, input().split())
child_dict = defaultdict(list)
value_dict = defaultdict(lambda: 0)
for _ in range(n - 1):
    a, b = map(int, input().split())
    child_dict[a].append(b)
import copy
for _ in range(q):
    c, d = map(int, input().split())
    value_dict[c] += d
    child = child_dict[c]
    while len(child) > 0:
        k = []
        for i in child:
            value_dict[i] += d
            k.extend(child_dict[i])
        child = copy.deepcopy(k)
ans = [value_dict[i] for i in range(1 ,n+1)]
print(*ans)

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 dfs(graph, node_start, visited, scores, score, ans):
    if node_start in visited:
        return visited
    visited.append(node_start)
    score += scores[node_start]
    ans.append([node_start, score])
    for node_end in graph[node_start]:
        dfs(graph, node_end, visited, scores, score, ans)
    return visited, ans

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 = dfs(graph, 1, [], scores, 0, [])
    ans.sort()
    for _, s in ans:
        print(s)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def solve(N, Q, ABs, PXs):
    values = {i: 0 for i in range(N + 1)}
    ans = [-1 for i in range(N + 1)]
    vertexes = {}
    for a, b in ABs:
        vertexes.setdefault(a, []).append(b)
        vertexes.setdefault(b, []).append(a)

    for p, x in PXs:
        values[p] += x

    queue = []
    queue.append((1, 0))
    while queue:
        index, parent_value = queue.pop()
        value = parent_value + values[index]
        ans[index] = value
        for child in vertexes[index]:
            if ans[child] == -1:
                queue.append((child, value))
    return " ".join([str(a) for a in ans[1:]])


assert (solve(4, 3, [(1, 2), (2, 3), (2, 4)], [(2, 10), (1, 100), (3, 1)]) == "100 110 111 110")
assert (solve(6 , 2 , [(1, 2), (1, 3), (2, 4), (3, 6), (2, 5)] , [(1, 10), (1, 10)]) == "20 20 20 20 20 20")

if __name__ == "__main__":
    N, Q = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    PXs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, Q, ABs, PXs))

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(4100000)

class Node():
    def __init__(self, val):
        self.val = val
        self.counter = 0
        self.child = []

if __name__ == '__main__':
    def inorder(node, val, toadd, combs):
        if combs.get(node.val):
            toadd.append(combs[node.val])
            return
        if node is None:
            return
        toadd.append(node)
        for child in node.child:
            inorder(child,val, toadd, combs)

    n,q = [int(i) for i in input().split()]
    a = [[int(i) for i in input().split()] for _ in range(n-1)]
    p = [[int(i) for i in input().split()] for _ in range(q)]
    nodes = {}
    for i in range(1,n+1):
        temp = Node(i)
        nodes[i] = temp
    for A,B in a:
        nodes[A].child.append(nodes[B])
    combs = {}
    for P,X in p:
        toadd = []
        combs[P] = inorder(nodes[P],X, toadd, combs)
        for node in toadd:
            node.counter += X
    ans = ""
    for i in range(1,n+1):
        ans += str(nodes[i].counter) + " "
    print(ans)

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())
  a, b = a-1, b-1
  g[a].append(b)
#print(g)

from collections import deque

c = [0]*n
for j in range(q):
  x, p = map(int, input().split())
  x = x-1
  queue = deque()
  queue.append(x)
  c[x] += p
  while queue:
    y = queue.popleft()
    for y_ in g[y]:
      c[y_] += p
      queue.append(y_)

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

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
    
pq = [0 for _ in range(N)]
for _ in range(Q) :
    p, q = map(int, input().split())
    pq[p-1]  += q
    
visited = [False] * N
visited[0] = True

ret = [0] * N
def bfs(cur, score) :
    ret[cur] = score + pq[cur]
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            bfs(nex, ret[cur])

bfs(0, 0)
    
print(*ret)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().split())
nodes = [[[], 0] for _ in range(n)]

def add(idx, val):
    global nodes
    addnodes = [idx]
    while len(addnodes) > 0:
        n = addnodes.pop()
        nodes[n][1] += val
        for i in nodes[n][0]:
            addnodes.append(i)


for _ in range(n-1):
    a, b = map(int, input().split())
    nodes[a-1][0].append(b-1)
for _ in range(q):
    p, q = map(int, input().split())
    add(p-1, q)
op = str(nodes[0][1])
for n in range(1, len(nodes)):
    op += " {}".format(nodes[n][1])
print(op)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000000)


class Graph:

  def __init__(self, N):
    self.V = {}
    self.E = {}

    for i in range(N):
      self.V[i + 1] = 0
      self.E[i + 1] = {}

  def add_edge(self, u, v, w):
    self.E[u][v] = w


def calc(N, G):
  result = [0] * N

  def walk(u, current_value):
    current_value = G.V[u] + current_value
    result[u - 1] = current_value
    for v in G.E[u]:
      walk(v, current_value)

  walk(1, 0)

  return result


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

G = Graph(N)

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

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

result = calc(N, G)

for v in result:
  print(v, end=' ')

print()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
edges = [set() for i in range(n)]
for _ in range(n-1):
    a, b= map(int,input().split())
    edges[a-1].add(b-1)
cnt = [0] * n

for _ in range(q):
    p, x = map(int, input().split())
    l = [p-1]
    while len(l) != 0:
        a = l.pop()
        cnt[a] += x
        for i in edges[a]:
            l.append(i)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def update(node,value):
  if node-1<0 or len(l)<=node-1:
    return 0
  vl[node-1]+=value

  if len(l[node-1])==0:
    return 0

  for x in l[node-1]:
    update(x,value)

n,q=LI()

l=[[] for _ in range(n)]
vl=[0 for _ in range(n)]

for _ in range(n-1):
  a,b=LI()
  l[a-1].append(b)

for _ in range(q):
  a,b=LI()
  update(a,b)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
N, Q = map(int, input().split())

class Node:
    def __init__(self, index):
        self.index = index
        self.paths = []
        self.count = 0

    def append(self, next_node):
        self.paths.append(next_node)

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

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


def rec(index, counter):
    node = nodes[index]
    node.count += counter
    for path in node.paths:
        rec(path, node.count)

rec(0, 0)

for node in nodes:
    print(node.count, end=" ")

Submission status: Time Limit Exceeded

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

def sol():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]

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

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

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

    def calc(now, parent):
        if parent != -1:
            ans[now] += ans[parent]
        for to in edge[now]:
            if to != parent:
                calc(to, now)
        return

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


sol()

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
node_rel={}
for l in node_lst:
    src, dst = l[0], l[1]
    if src not in node_rel.keys():
        node_rel[src]=[dst]
    else:
        node_rel[src].append(dst)
    for k, v in node_rel.items():
        if src in v:
            node_rel[k].append(dst)
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
    if p in node_rel.keys():
        for e in node_rel[p]:
            cnt_lst[e-1]+=x
print(" ".join([str(c) for c in cnt_lst]))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**5)

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

points = [0] * n
for i in range(q):
    p,x = words(int)
    points[p-1] += x

ans = [0] * n
def digTree(edges, points, cur, sum_p):
    #print("debug: ", cur, sum_p)
    sum_pp = sum_p +  points[cur]
    ans[cur] = sum_pp
    for child in edges[cur]:
        digTree(edges, points, child, sum_pp)

digTree(edges, points, 0, 0)
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

query = [[] for _ in range(N)]
ans = [[0] for _ in range(N)]

for p,x in px:
    query[p-1].append(x)
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(b-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    for q in query[v]:
        val += q
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
        
    
    
dfs(0,0)
print(*ans)

Submission status: Time Limit Exceeded

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

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

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

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)

        return 0

    f(weights[0], 0)
    return ' '.join(map(str, ans))


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

n, q = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

cost = [0] * n

for i in range(q):
    p, x = [int(item) for item in input().split()]
    p -= 1
    cost[p] += x

ans = [-1] * n
ans.append(0)

def dfs(frm, n):
    if ans[n] != -1:
        return
    ans[n] = ans[frm] + cost[n]
    for to in edge[n]:
        dfs(n, to)

dfs(-1, 0)
print(" ".join([str(item) for item in ans[:-1]]))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab=sorted(ab, key=lambda x:x[0])
pq=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for i in range(m):
	p,q=pq[i][0],pq[i][1]
	res[p-1]+=q
for i in range(n-1):
	a,b=ab[i][0],ab[i][1]
	res[b-1]+=res[a-1]
ans=[]
for i in range(n):
	ans.append(str(res[i]))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

ans = [0] * (N + 1)
queue = deque()
queue.append(1)
visited = [0] * (N + 1)
visited[1] = 1
while queue:
    v = queue.pop()
    if v == 1:
        ans[v] = point[v]
    for u in adj[v]:
        if visited[u] == 0:
            queue.append(u)
            visited[u] = 1
            ans[u] = ans[v] + point[u]

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

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
    
visited = [False] * N
visited[0] = True
parent = [[] for _ in range(N)]

def bfs(cur, par) :
    parent[cur] = [cur] + par
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            bfs(nex, parent[cur])

bfs(0, [])

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

ret = []
for i in range(N) :
    s = 0
    for j in parent[i] :
        s += pq[j]

    ret.append(s)
    
print(*ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import sys
sys.setrecursionlimit(10 ** 6)
N, Q = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  
res = [0] * (N + 1)
for _ in range(Q):
  p, x = map(int, input().split())
  res[p] += x
visited = [0] * (N + 1)
def dfs(n):
  global visited
  global res
  visited[n] = 1
  for o in e[n]:
    if visited[o] == 0:
      res[o] += res[n]
      dfs(o)
dfs(1)
sen = ""
for i in range(1, N + 1):
  sen += str(res[i])
  if i != N:
    sen += " "
print(sen)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
N, Q = map(int, input().split(" "))
cnt = [0] * N
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

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


def dfs(n, prev):
    global cnt
    for e in edge[n]:
        if e == prev:
            continue
        cnt[e] += cnt[n]
        dfs(e, n)


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)



## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
def dfs(p,q):
  if p in route[q]:
    route[q].remove(p)
  for r in route[q]:
    cnt[r] += cnt[q]
    dfs(q,r)

dfs(-1,0)
for c in cnt[:-1]:
  print(c,end=" ")
print(cnt[-1])

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)
    T[b].append(a)
for _ in range(Q):
    p,x = map(int,input().split())
    V[p]+=x
def f(v,p,s):
    global T,V
    V[v] = s
    for c in T[v]:
        if c==p:continue
        f(c,v,s+V[c])
f(1,0,V[1])
print(*V[1:])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def update(node,value):
  if node-1<0 or len(l)<=node-1:
    return 0
  vl[node-1]+=value
  if len(l[node-1])==0:
    return 0
  for x in l[node-1]:
    update(x,value)

n,q=LI()

l=[[] for _ in range(n)]
vl=[0 for _ in range(n)]

for _ in range(n-1):
  a,b=LI()
  l[a-1].append(b)

for _ in range(q):
  a,b=LI()
  update(a,b)

# print(l)
# print(vl)
print(' '.join([str(x) for x in vl]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(250000)

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

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

d = [[i] for i in range(N + 1)]
seen = set()


def dfs(v, parents):
    seen.add(v)
    for p in parents:
        d[p].append(v)
    for next_v in nl[v]:
        if next_v not in seen:
            dfs(next_v, parents + [v])


dfs(1, [])
c = [0 for _ in range(N + 1)]
for p, x in [tuple(map(int, input().split())) for _ in range(Q)]:
    for v in d[p]:
        c[v] += x
print(' '.join([str(ans) for ans in c[1:]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


N, Q = list(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)]


class Tree():
    def __init__(self, v):
        self.parent = None
        self.v = v
        self.x = 0
        self.memo = None

    def add(self, x):
        self.x += x

    def calc(self):
        if self.v == 1:
            return self.x
        if self.memo is not None:
            return self.memo

        tmp = self.parent.calc()
        self.memo = tmp + self.x
        return self.memo



trees = {i: Tree(i) for i in range(1, N + 1)}

for a,b in ab:
    trees[b].parent = trees[a]

for p,x in px:
    trees[p].add(x)


print(" ".join(map(str,[trees[i].calc() for i in range(1,N+1)])))

Submission status: Time Limit Exceeded

Solution code:
import collections


def solve(N, Q, ABs, PXs):
    # print(N, ",", Q, ",", ABs, ",", PXs)
    vertexes = {}
    values = {i: 0 for i in range(N + 1)}
    for a, b in ABs:
        vertexes.setdefault(a, []).append(b)
        vertexes.setdefault(b, []).append(a)
    for p, x in PXs:
        values[p] += x

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

    queue = collections.deque()
    queue.append((1, 0))
    while queue:
        index, parent_value = queue.popleft()
        value = parent_value + values[index]
        ans[index] = value
        for child in vertexes[index]:
            if ans[child] == -1:
                queue.append((child, value))
    return " ".join([str(a) for a in ans[1:]])


# assert (solve(4, 3, [(1, 2), (2, 3), (2, 4)], [(2, 10), (1, 100), (3, 1)]) == "100 110 111 110")
# assert (solve(6 , 2 , [(1, 2), (1, 3), (2, 4), (3, 6), (2, 5)] , [(1, 10), (1, 10)]) == "20 20 20 20 20 20")

if __name__ == "__main__":
    N, Q = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    PXs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, Q, ABs, PXs))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)



## input
N,Q = map(int, sys.stdin.readline().rstrip().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, sys.stdin.readline().rstrip().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, sys.stdin.readline().rstrip().split())
  cnt[p-1] += x

## solve
def dfs(p,q):
  if p in route[q]:
    route[q].remove(p)
  for r in route[q]:
    cnt[r] += cnt[q]
    dfs(q,r)

dfs(-1,0)
for c in cnt[:-1]:
  print(c,end=" ")
print(cnt[-1])