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 #追加
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())

from collections import defaultdict
dic = defaultdict(list)


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


dic2 = defaultdict(int)

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

ansl = [0 for i in range(n)]
used = [-1 for i in range(n)]
used[0] = 1
def dfs(pos):
    for p in dic[pos]:
        if used[p] == -1:
            ansl[p] = ansl[pos] + dic2[pos]
            used[p] = 1
            dfs(p)

dfs(0)
for idx, a in enumerate(ansl):
    print(a + dic2[idx])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*(10**5)+1)
N, Q = map(int,input().split())
T = [[] for k in range(N)]
V = [0]*N
for _ in range(N-1):
    a, b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
for q in range(Q):
    p, x = map(int,input().split())
    V[p-1] += x

def dfs(mae,ima):
    for tsugi in T[ima]:
        if tsugi != mae:
            V[tsugi] += V[ima]
            dfs(ima,tsugi)
dfs(-1,0)
print(*V)

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 ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

parent = [None] * N
parent[0] = 0

import sys
sys.setrecursionlimit(200002)

# def dfs(src):
#     for dst in graph[src]:
#         if parent[dst] != None: continue
#         #
#         parent[dst] = src
#         dfs(dst)

# dfs(0)
# print("#", parent)

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi
        
memo = [None] * N

# def dp(arg):
#     if memo[arg] != None: return memo[arg]
#     #
#     # print("#", arg)
#     ret = score[arg]
#     if arg != parent[arg]: ret += dp(parent[arg])
#     memo[arg] = ret
#     return ret

ans = [None] * N

def set_score(src, score_tmp):
    score_tmp += score[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] != None: continue
        set_score(dst, score_tmp)
        
set_score(0, 0)        

# ans = []
# for i in range(N):
#     ans.append(dp(i))

# print("#", memo)

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

Submission status: Time Limit Exceeded

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

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

parent = [None] * N
parent[0] = 0

import sys
sys.setrecursionlimit(200002)

def dfs(src):
    for dst in graph[src]:
        if parent[dst] != None: continue
        parent[dst] = src
        dfs(dst)

dfs(0)
# print("#", parent)

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi
        
memo = [None] * N
def dp(arg):
    if memo[arg] != None: return memo[arg]
    #
    ret = score[arg]
    if arg != parent[arg]: ret += dp(parent[arg])
    memo[arg] = ret
    return ret

ans = []
for i in range(N):
    ans.append(dp(i))

# print("#", memo)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
PX = [tuple(map(int,input().split())) for i in range(Q)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
ps = [0] * N
for p,x in PX:
    ps[p-1] += x

ans = [0] * N
def dfs(v,p=-1, c=0):
    ans[v] = c + ps[v]
    for to in es[v]:
        if to==p: continue
        dfs(to, v, ans[v])
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

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

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline


n_nodes, q_query = map(int, input().split())

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

queries = []
for _ in range(q_query):
    p, x = map(int, input().split())
    queries.append([p - 1, x])

# print(n_nodes, q_query)
# print(edges, queries)

res = [0 for _ in range(n_nodes)]
for node, point in queries:
    res[node] += point


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            res[v_next] += res[v]
            dfs(v_next, v)


dfs(0, None)

print(*res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N, Q = map(int, input().split())
link = [[0]*(N+1) for _ in range(N+1)]
for n in range(N-1):
    a, b = map(int, input().split())
    link[a][b] = 1
    link[b][a] = 1
V = [0] * (N+1)
ans = [0] * (N+1)
for q in range(Q):
    p, x = map(int, input().split())
    V[p] += x

def dfs(i, parent, acc):
    V[i] += acc
    for j in range(1,N+1):
        if link[i][j] == 1 and parent!=j:
            dfs(j,i,V[i])
cur = 1
parent = 0
acc = 0

dfs(cur, parent , acc)
V = [str(v) for v in V]
print (" ".join(V[1:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
N, Q = map(int, input().split())
#link = [[0]*(N+1) for _ in range(N+1)]
link = [[] for _ in range(N+1)]
for n in range(N-1):
    a, b = map(int, input().split())
    # link[a][b] = 1
    # link[b][a] = 1
    link[a].append(b)
    link[b].append(a)
V = [0] * (N+1)
ans = [0] * (N+1)
for q in range(Q):
    p, x = map(int, input().split())
    V[p] += x

def dfs(i, parent, acc):
    V[i] += acc
    # for j in range(1,N+1):
    #     if link[i][j] == 1 and parent!=j:
    #         dfs(j,i,V[i])
    for j in link[i]:
        if j==parent:
            continue
        dfs(j,i,V[i])
cur = 1
parent = 0
acc = 0

dfs(cur, parent , acc)
V = [str(v) for v in V]
print (" ".join(V[1:]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
link = [[0]*(N+1) for _ in range(N+1)]
for n in range(N-1):
    a, b = map(int, input().split())
    link[a][b] = 1
    link[b][a] = 1
V = [0] * (N+1)
ans = [0] * (N+1)
for q in range(Q):
    p, x = map(int, input().split())
    V[p] += x

def dfs(i, parent, acc):
    V[i] += acc
    for j in range(1,N+1):
        if link[i][j] == 1 and parent!=j:
            dfs(j,i,V[i])
cur = 1
parent = 0
acc = 0

dfs(cur, parent , acc)
V = [str(v) for v in V]
print (" ".join(V[1:]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
link = [[0]*(N+1) for _ in range(N+1)]
for n in range(N-1):
    a, b = map(int, input().split())
    link[a][b] = 1
    link[b][a] = 1
V = [0] * (N+1)
ans = [0] * (N+1)
for q in range(Q):
    p, x = map(int, input().split())
    V[p] += x

def dfs(i, parent, acc):
    V[i] += acc
    for j in range(N+1):
        if link[i][j] == 1 and parent!=j:
            dfs(j,i,V[i])
acc = 0
dfs(1,0,acc)
V = [str(v) for v in V]
print (" ".join(V[1:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

def dfs(p, i, v):
    counter[i] += v
    for j in edges[i]:
        if j != p:
            dfs(i, j, counter[i])

dfs(-1, 0, 0)

print(' '.join(str(c) for c in counter))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()
n, k = list(map(int,input().split(' ')))
path = []
for i in range(n+1):
    path.append([])
for i in range(n-1):
    a, b = list(map(int,input().split(' ')))
    path[a].append(b)
    path[b].append(a)
val = [0] * (n+1)
for i in range(k):
    v, pt = list(map(int,input().split(' ')))
    val[v] += pt

used = {}
q = [1]
used[1] = True
while q:
    v = q.pop(0)
    for next_v in path[v]:
        if next_v not in used:
            used[next_v] = True
            val[next_v] += val[v]
            q.append(next_v)

print(' '.join([str(pt) for pt in val[1:]]))

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int,input().split(' ')))
path = []
for i in range(n+1):
    path.append([])
for i in range(n-1):
    a, b = list(map(int,input().split(' ')))
    path[a].append(b)
    path[b].append(a)
val = [0] * (n+1)
for i in range(k):
    v, pt = list(map(int,input().split(' ')))
    val[v] += pt

used = {}
q = [1]
used[1] = True
while q:
    v = q.pop(0)
    for next_v in path[v]:
        if next_v not in used:
            used[next_v] = True
            val[next_v] += val[v]
            q.append(next_v)

print(' '.join([str(pt) for pt in val[1:]]))

Submission status: Time Limit Exceeded

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

AB = [-1] * (N + 1)
counts = [0] * (N + 1)
AB[1] = 0
ABs = []
first_order = [1]
for n in range(N-1):
    a, b = [int(s) for s in input().split(' ')]
    counts[a] += 1
    counts[b] += 1
    if a == 1:
        AB[b] = a
        first_order.append(b)
        continue
    ABs.append((a,b))
order = []
next_ABs = []
while len(ABs) > 0:
    for a, b in ABs:
        if counts[a] == 1:
            AB[a] = b
            counts[a] -= 1
            counts[b] -= 1
            order.append(a)
            continue
        if counts[b] == 1:
            AB[b] = a
            counts[a] -= 1
            counts[b] -= 1
            order.append(b)
            continue
        next_ABs.append((a,b))
    ABs = next_ABs
    next_ABs = []

order = first_order + list(reversed(order))
PQ = [0] * (N + 1)
for q in range(Q):
    p, q = [int(s) for s in input().split(' ')]
    PQ[p] += q

ret = [0] * (N + 1)
for n in order:
    ret[n] = PQ[n]
    ret[n] += ret[AB[n]]

print(' '.join([str(r) for r in ret[1:]]))

Submission status: Time Limit Exceeded

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

n, q = map(int, 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)]

graph = [[] for _ in range(n + 1)]

for a, b in AB:
	graph[a].append(b)
	graph[b].append(a)

value = [0] * (n + 1)
for p, x in PX:
	value[p] += x

def dfs(v, parent, add):
	value[v] += add
	for x in graph[v]:
		if x == parent:
			continue
		dfs(x, v, value[v])

dfs(1, 0, 0)
print(*value[1:])

Submission status: Time Limit Exceeded

Solution code:
import os, sys, re, math

class Node:
    def __init__(self, index):
        self.index = index
        self.level = 1
        self.parent = None
        self.children = []
        self.count = 0

    #def __str__(self):
    #    return 'Index=%s, Level=%s, Children=%s' % (self.index, self.level, self.children)

    def setParent(self, parent):
        self.level = parent.level + 1
        self.parent = parent
        parent.setChildren([self.index])
        parent.setChildren(self.children)

    def setChildren(self, children):
        self.children += children
        if self.parent:
            self.parent.setChildren(children)


(N, Q) = [int(n) for n in input().split()]
branches = []
for i in range(N - 1):
    branches.append([int(n) for n in input().split()])
P = []
X = []
for i in range(Q):
    (p, x) = [int(n) for n in input().split()]
    P.append(p)
    X.append(x)

nodes = []
for i in range(N):
    nodes.append(Node(i + 1))

levelSet = [[1]]
level = 0
while branches:
    #print('level %s' % level)
    for l in levelSet[level]:
        levels = []
        picked = []
        for b in filter(lambda x:l in x, branches):
            #print(b)
            m = b[0] if b[1] == l else b[1]
            levels.append(m)
            nodes[m - 1].setParent(nodes[l - 1])
            picked.append(b)
        for p in picked:
            branches.remove(p)
        levelSet.append(levels)
    level += 1

for i in range(Q):
    node = nodes[P[i] - 1]
    node.count += X[i]
    for ci in node.children:
        child = nodes[ci - 1]
        child.count += X[i]

print(' '.join(['%s' % node.count for node in nodes]))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, 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)]

graph = [[] for _ in range(n + 1)]
# 各ノードと連結するノードを要素に持つ配列
# e.g., graph[1] -> ノード１と連結するノードを要素に持つ
for a, b in AB:
	graph[a].append(b)
	graph[b].append(a)

# 根に点数を入れる
value = [0] * (n + 1)
for p, x in PX:
	value[p] += x

# 根から値を流す
q = [(1, 0)]
while q:
	x, parent = q.pop() # (1, 0)
	value[x] += value[parent]
	# 連結する成分について繰り返す
	# このとき、親のノードに流さないように注意
	# ここでの操作は、自分の子のノードを加えること
	for y in graph[x]:
		if y == parent:
			continue
		q.append((y, x)) #(親,子)

res = ' '.join(map(str, value[1:]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())
graph = [[] for _ in range(n)]
cnt = [0] * n

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

def bfs(parent,current):
    if not graph[parent]:
        return
    if not (parent == 0 and current == 0):
        cnt[current] += cnt[parent]

    for child in graph[current]:
        bfs(current,child)

bfs(0,0)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  from collections import deque
  
  n,q=map(int,input().split())
  ab=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
  ans=[0]*(n+1)
  for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x
  
  l,parent=deque([1]),[0]*(n+1)
  while l:
    x=l.popleft()
    for i in ab[x]:
      if not i in parent or i in l:
        l.append(i)
        ans[i]+=ans[x]
        parent[i]=x
      
  print(*ans[1:])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,q=map(int,input().split())
ab=[[] for _ in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  ab[a].append(b)
  ab[b].append(a)
px=[tuple(map(int,input().split())) for _ in range(q)]

ans=[0]*(n+1)
for i in range(q):
  ans[px[i][0]]+=px[i][1]
l,m=deque([1]),[]
while l:
  x=l.popleft()
  m.append(x)
  for i in ab[x]:
    if not i in m or i in l:
      l.append(i)
      ans[i]+=ans[x]
      
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N

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

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

def propagate(node, parent):
    if parent is not None:
        counter[node] += counter[parent]
    for c in neighbor[node]:
        if c != parent:
            propagate(c, node)

propagate(0, None)
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [None] * N

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

def solve():
    stack = [(0, None)]
    while stack:
        (node, parent) = stack.pop()
        pcounter[node] = counter[node]
        if parent is not None:
            pcounter[node] += pcounter[parent]
        for c in neighbor[node]:
            if pcounter[c] is None:
                stack.append((c, node))

solve()
print(*pcounter, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [0] * N

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

def find(x, llist):
    while llist is not None:
        y, llist = llist
        if y == x:
            return True
    return False


stack = [(0, 0, None)]
while stack:
    (node, acc, ancestors) = stack.pop()
    counter[node] += acc
    acc = counter[node]
    ancestors = (node, ancestors)
    for c in neighbor[node]:
        if not find(c, ancestors):
            stack.append((c, acc, ancestors))

print(*counter, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [0] * N

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

def propagate(node, acc, ancestors):
    counter[node] += acc
    acc = counter[node]
    ancestors.add(node)
    for c in neighbor[node]:
        if c not in ancestors:
            propagate(c, acc, ancestors)

propagate(0, 0, set())
print(*counter, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
 
sys.setrecursionlimit(10 ** 6)
"""
def input():
    return sys.stdin.readline().strip()
"""
def main():
    N,Q = map(int,input().split())
    K = [[] for _ in range(N+1)]
    nums = [0 for _ in range(N+1)]

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

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

    def dfs(now,parent):
        for i in K[now]:
            if i != parent:
                nums[i] += nums[now]
                dfs(i,now)

    dfs(1,0)
    print(*nums[1:])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N,Q = map(int,input().split())
K = [[] for _ in range(N+1)]
nums = [0 for _ in range(N+1)]

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

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

def dfs(now,parent):
    for i in K[now]:
        if i != parent:
            nums[i] += nums[now]
            dfs(i,now)

dfs(1,0)
print(*nums[1:])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
D = {i: [] for i in range(N)}
E = {i: [] for i in range(N)}
par = [-1 for _ in range(N)]
par[0] = 5000000000
for _ in range(N - 1):
  a, b = map(int, input().split())
  D[a-1].append(b-1)
  D[b-1].append(a-1)
p = [0]
cnt = 1
pnt = 0
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    for j in D[p[i]]:
      if par[j] == -1:
        E[p[i]].append(j)
        par[j] = p[i]
        cnt += 1
        p.append(j)
  pnt = n
counter = [0 for _ in range(N)]
for _ in range(Q):
  p, x = map(int, input().split())
  counter[p-1] += x
p = [0]
cnt = 1
pnt = 0
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    for j in E[p[i]]:
      counter[j] += counter[p[i]]
      p.append(j)
      cnt += 1
  pnt = n
for i in range(N-1):
  print(counter[i], end = ' ')
print(counter[N-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)
N, Q = map(int, input().split())
A, B = [], []

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

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


def dfs(now, parent):
    for i in edges[now]:
        if i != parent:
            nums[i] += nums[now]
            dfs(i, now)


dfs(1, 0)
for n in nums[1:]:
    print(n)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

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

q = queue.Queue()
q.put(0)

while not q.empty():
  index = q.get()
  pindex = parent[index]
  for i in tree[index]:
    if i == pindex: continue
    counter[i] += counter[index]
    parent[i] = index
    q.put(i)
    
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
 
## BFS
 
#入力受け取り
N, Q = mi()
x = li2(N-1)
 
cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1
 
#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    #x[i][0] -= 1
    #x[i][1] -= 1
    adj[x[i][0]-1].append(x[i][1]-1)
    adj[x[i][1]-1].append(x[i][0]-1)
 
global ans
ans = [0]*N
 
def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)
 
dfs(0, 0)
 
for i in range(N):
    print(ans[i], '', end='')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS

#入力受け取り
N, Q = mi()
x = li2(N-1)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    #x[i][0] -= 1
    #x[i][1] -= 1
    adj[x[i][0]-1].append(x[i][1]-1)
    adj[x[i][1]-1].append(x[i][0]-1)

global ans
ans = [0]*N

def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)

dfs(0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS

#入力受け取り
N, Q = mi()
x = li2(N-1)

cnt = [0]*(N+1)
for i in range(Q):
    p0, p1 = mi()
    cnt[p0] += p1

#隣接リスト作成
adj = [[] for i in range(N+1)]
for i in range(N-1):
    #x[i][0] -= 1
    #x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

global ans
ans = [0]*(N+1)

def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)

dfs(1, 1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS

#入力受け取り
N, Q = mi()
x = li2(N-1)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

global ans
ans = [0]*N

def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)

dfs(0, 0)

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

Submission status: Time Limit Exceeded

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

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

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

def dfs(now, prev):
    for target in adj[now]:
        if target == prev:
            continue
        score[target] += score[now]
        dfs(target, now)

dfs(1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

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

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

searched = [False for _ in range(N+1)]
searched[1] = True
q = Queue()

def bfs(i, add_point):
    if i > N:
        return
    if searched[i]:
        return
    searched[i] = True
    score[i] += add_point
    q.put([i, score[i]])
    return
    
q.put([1, score[1]])
    
while not q.empty():
    i, p = q.get()
    for j in adj[i]:
        bfs(j, p)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
point = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
for i in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x
def dfs(s,parent):
    for i in graph[s]:
        if i == parent:
            continue
        point[i] += point[s]
        dfs(i,s)
dfs(0,-1)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
point = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x
def dfs(s,parent):
    for i in graph[s]:
        if i == parent:
            continue
        point[i] += point[s]
        dfs(i,s)
dfs(0,-1)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
point = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x
def dfs(s,parent):
    for i in graph[s]:
        if i == parent:
            continue
        point[i] += point[s]
        dfs(i,s)
dfs(0,-1)
print(*point)

Submission status: Time Limit Exceeded

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

N,Q = [int(i) for i in input().split()] #N個の頂点、Q回の操作
aaabbb = [[int(i) for i in input().split()] for j in range(N-1)] #木の辺
pppxxx = [[int(i) for i in input().split()] for j in range(Q)] #操作

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

for a,b in aaabbb:
    tree[a].append(b)
    tree[b].append(a)

#print(tree)

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

for p,x in pppxxx:
    counter[p] += x

#print(counter)

def dfs(pos,parent,add):
    counter[pos] += add
    for next_pos in tree[pos]:
        if not next_pos == parent:
            dfs(next_pos,pos,counter[pos])

dfs(1,0,0)

#print(counter)

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

Submission status: Time Limit Exceeded

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

N,Q = [int(i) for i in input().split()] #N個の頂点、Q回の操作
aaabbb = [[int(i) for i in input().split()] for j in range(N-1)] #木の辺
pppxxx = [[int(i) for i in input().split()] for j in range(Q)] #操作

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

for a,b in aaabbb: #aがbの親とは限らないのでこの表記はまずい
    if not b in tree[a]:
        tree[a].append(b)
    if not a in tree[b]:
        tree[b].append(a)

#print(tree)

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

for p,x in pppxxx:
    counter[p] += x

#print(counter)

visited = []

def dfs(pos):
    visited.append(pos)
    for next_pos in tree[pos]:
        if not next_pos in visited:
            counter[next_pos] += counter[pos]
            dfs(next_pos)

dfs(1)

#print(counter)

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