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())
 
AB = []
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
AB = sorted(AB, key=lambda x: (x[1], x[0]))
 
root = 0
q = [root]
parent = [-1] * N
while q:
    x = q.pop(0)
    p = parent[x]
    for y in graph[x]:
        if y == p:
            continue
        parent[y] = x
        q.append(y)

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

for a, b in AB:
    if a != parent[b]:
        tmp = a
        a = b
        b = tmp
    C[b] = C[b] + C[a]

print(*C)

Submission status: Time Limit Exceeded

Solution code:
import sys
import io
#sys.stdin = io.StringIO(input_string)
sys.setrecursionlimit(10 ** 6)
def _input():
    return sys.stdin.readline()[:-1]
    
def resolve():
	from collections import deque
	
	n, q = map(int, input().split())
	adj = [[] for i in range(n+1)]
	for i in range(n-1):
		a, b = map(int, input().split())
		adj[a-1].append(b-1)
		adj[b-1].append(a-1)
	ans = [0 for i in range(n)]
	for i in range(q):
		p, x = map(int, input().split())
		p -= 1
		ans[p] += x
#	print(f"{adj=}\n{ans=}")

	def dfs(now, prv):
		for next in adj[now]:
#			print(f"{now=}, {next=}")
			if next == prv:
				continue
			ans[next] += ans[now]
			dfs(next, now)

	dfs(0, 0)
	print(*ans)

resolve()

Submission status: Time Limit Exceeded

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

AB = []
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
AB = sorted(AB, key=lambda x: (x[1], x[0]))

root = 0
q = [root]
append_q = q.append
parent = [-1] * N
while q:
    x = q.pop(0)
    p = parent[x]
    for y in graph[x]:
        if y == p:
            continue
        parent[y] = x
        append_q(y)

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

for a, b in AB:
    if a != parent[b]:
        tmp = a
        a = b
        b = tmp
    C[b] += C[a]

print(*C)

Submission status: Time Limit Exceeded

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

AB = []
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
AB = sorted(AB, key=lambda x: (x[1], x[0]))

root = 0
q = [root]
parent = [-1] * N
while q:
    x = q.pop(0)
    p = parent[x]
    for y in graph[x]:
        if y == p:
            continue
        parent[y] = x
        q.append(y)

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

for a, b in AB:
    if a != parent[b]:
        tmp = a
        a = b
        b = tmp
    C[b] += C[a]

print(*C)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
parent = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    parent[a].append(b)
    parent[b].append(a)
import queue
check = [0] * n

ans = [0] * n

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

a = ''
qq = queue.Queue()
qq.put(0)
check[0] = 1
while not qq.empty():
    now = qq.get()
    for j, son in enumerate(parent[now]):
        if check[son] == 1:
            continue
        ans[son] += ans[now]
        check[son] = 1
        qq.put(son)
for i in range(n):
    a += str(ans[i]) + ' '
print(a)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
root = [[] for _ in range(N + 10)]
counter = [0 for _ in range(N + 10)]
for _ in range(N - 1):
  a, b = map(int, input().split())
  root[a].append(b)
  root[b].append(a)
for _ in range(Q):
  p, x = map(int, input().split())
  counter[p] += x
queue = [1]
while queue:
  vertex = queue.pop(0)
  for v in root[vertex]:
    counter[v] += counter[vertex]
    queue.append(v)
    root[v].remove(vertex)
for i in range(1, N):
  print('{} '.format(counter[i]), end='')
print(counter[N])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
children = [[] for _ in range(n)]
x = [0 for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  children[a-1].append(b-1)
  children[b-1].append(a-1)
for _ in range(q):
  xi = [int(i) for i in input().split()]
  x[xi[0]-1] += xi[1]

# bfs
import queue
q = queue.Queue()
q.put([0,0]) # node name and score of parent
#closed = [0 for i in range(n)]
#closed[0] = -1
scores = [-1 for i in range(n)]
while not q.empty():
  current = q.get()
  c = children[current[0]]
# traverse each node, and add the value of parent's
  score = x[current[0]] + current[1]
  scores[current[0]] = score
  for child in c:
# do not open already opened ones
    if scores[child] == -1:
      q.put([child, score])
      scores[child] = 0
  
print(*scores)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
children = [[] for _ in range(n)]
x = [0 for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  children[a-1].append(b-1)
  children[b-1].append(a-1)
for _ in range(q):
  xi = [int(i) for i in input().split()]
  x[xi[0]-1] += xi[1]

# bfs
import queue
q = queue.Queue()
q.put([0,0]) # node name and score of parent
closed = [0 for i in range(n)]
closed[0] = -1
scores = [0 for i in range(n)]
while not q.empty():
  current = q.get()
  c = children[current[0]]
# traverse each node, and add the value of parent's
  score = x[current[0]] + current[1]
  scores[current[0]] = score
  for child in c:
# do not open already opened ones
    if closed[child] != -1:
      q.put([child, score])
      closed[child] = -1
  
print(*scores)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
children = [[] for _ in range(n)]
x = [0 for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  children[a-1].append(b-1)
  children[b-1].append(a-1)
for _ in range(q):
  xi = [int(i) for i in input().split()]
  x[xi[0]-1] += xi[1]

# bfs
import queue
q = queue.Queue()
q.put([0,0]) # node name and score of parent
closed = [0]
scores = [0 for i in range(n)]
while not q.empty():
  current = q.get()
  c = children[current[0]]
# traverse each node, and add the value of parent's
  score = x[current[0]] + current[1]
  scores[current[0]] = score
  for child in c:
# do not open already opened ones
    if child not in closed:
      q.put([child, score])
      closed.append(child)
  
print(*scores)

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10**7)
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)]

branch = [[] for _ in range(N)]
for i in range(N-1):
    branch[ab[i][0]-1].append(ab[i][1]-1)
    branch[ab[i][1]-1].append(ab[i][0]-1)

counters = [0 for _ in range(N)]
for i in range(Q):
    counters[px[i][0]-1] += px[i][1]
results = [0 for _ in range(N)]

seen = [False for _ in range(N)]
from collections import deque
seen[0] = True
todo = deque([0])
results[0] = counters[0]

while len(todo)>0:
    checking = todo.pop()
    candidates = branch[checking]
    for candidate in candidates:
        if seen[candidate] == False:
            todo.append(candidate)
            seen[candidate] = True
            results[candidate] = results[checking]+counters[candidate]


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

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10**7)
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)]

branch = [[] for _ in range(N)]
for i in range(N-1):
    branch[ab[i][0]-1].append(ab[i][1]-1)
    branch[ab[i][1]-1].append(ab[i][0]-1)

counters = [0 for _ in range(N)]
for i in range(Q):
    counters[px[i][0]-1] += px[i][1]

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

def repeat(node, counter, pre_node):
    counter = counter + counters[node]
    results[node] = counter
    candidates = branch[node]
    for candidate in candidates:
        if candidate != pre_node:
            repeat(candidate, counter, node)

repeat(0, 0, 0)

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

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(int(1e+6))
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)]

branch = [[] for _ in range(N)]
for i in range(N-1):
    branch[ab[i][0]-1].append(ab[i][1]-1)
    branch[ab[i][1]-1].append(ab[i][0]-1)

counters = [0 for _ in range(N)]
for i in range(Q):
    counters[px[i][0]-1] += px[i][1]

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

def repeat(node, counter, pre_node):
    counter += counters[node]
    for candidate in branch[node]:
        if candidate == pre_node:
            continue
        else:
            repeat(candidate, counter, node)
    results[node] = counter

repeat(0, 0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  sys.setrecursionlimit(int(1e+6))
  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)]

  branch = [[] for _ in range(N)]
  for i in range(N-1):
      branch[ab[i][0]-1].append(ab[i][1]-1)
      branch[ab[i][1]-1].append(ab[i][0]-1)

  counters = [0 for _ in range(N)]
  for i in range(Q):
      counters[px[i][0]-1] += px[i][1]

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

  def repeat(node, counter, pre_node):
      counter += counters[node]
      for candidate in branch[node]:
          if candidate == pre_node:
              continue
          else:
              repeat(candidate, counter, node)
      results[node] = counter
      return

  repeat(0, 0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e+6))
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)]

branch = [[] for _ in range(N)]
for i in range(N-1):
    branch[ab[i][0]-1].append(ab[i][1]-1)
    branch[ab[i][1]-1].append(ab[i][0]-1)

counters = [0 for _ in range(N)]
for i in range(Q):
    counters[px[i][0]-1] += px[i][1]

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

def repeat(node, counter, pre_node):
    counter += counters[node]
    for candidate in branch[node]:
        if candidate == pre_node:
            continue
        else:
            repeat(candidate, counter, node)
    results[node] = counter
    return
    
repeat(0, 0, 0)

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

Submission status: Time Limit Exceeded

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

def dfs(v):
    seen[v] = 1
    ans[v] += counter[v]

    for next_v in graph[v]:
        if seen[next_v]: continue
        ans[next_v] += ans[v]
        dfs(next_v)

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

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

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

seen = [0] * n
ans = [0] * n
dfs(0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC138D

import sys
sys.setrecursionlimit(1000000000)

def dfs(adj,v,p,px,x,ct):
    x+=px[v]
    for nv in adj[v]:
        if nv==p:
            continue
        else:
            dfs(adj,nv,v,px,x,ct)
    ct[v]+=x

N,Q=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    adj[a-1]+=[b-1]
    adj[b-1]+=[a-1]
px=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    px[p-1]+=x
    
ct=[0]*N
dfs(adj,0,-1,px,0,ct)


print(ct[0], end="")
for i in range(1,N):
    print(" {}".format(ct[i]),end="")
print("")

Submission status: Time Limit Exceeded

Solution code:
import queue

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

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

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

q = queue.Queue()
q.put(0)
seen = [0] * n
ans = [0] * n

while True:
    if q.empty(): break
    v = q.get()
    seen[v] = 1
    ans[v] += counter[v]

    for next_v in graph[v]:
        if seen[next_v]: continue
        q.put(next_v)
        ans[next_v] += ans[v]

print(*ans)

Submission status: Time Limit Exceeded

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

def dfs(v):
    seen[v] = 1
    ans[v] += counter[v]

    for next_v in graph[v]:
        if seen[next_v]: continue
        ans[next_v] += ans[v]
        dfs(next_v)

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

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

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

seen = [0] * n
ans = [0] * n
dfs(0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC138D

import sys
sys.setrecursionlimit(1000000000)
def dfs(kol,adj,v,p):
    for nv in adj[v]:
        if nv==p:
            continue
        else:
            dfs(kol,adj,nv,v)
    kol[v]+=[v]
    if p!=-1:
        kol[p]+=kol[v]
N,Q=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    adj[a-1]+=[b-1]
    adj[b-1]+=[a-1]
    
ct=[0]*N
kol=[[] for i in range(N)]

dfs(kol,adj,0,-1)

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

print(ct[0], end="")
for i in range(1,N):
    print(" {}".format(ct[i]),end="")
print("")

Submission status: Time Limit Exceeded

Solution code:
# 早くなるおまじない
import sys
input = sys.stdin.buffer.readline

# 再帰関数の呼び出し制限
sys.setrecursionlimit(10**6)

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

dic = {}
for i in range(n-1):
    aa, bb = map(int,input().split())

    if aa not in dic:
        dic[aa] = set()
        dic[aa].add(bb)
    else:
        dic[aa].add(bb)

    if bb not in dic:
        dic[bb] = set()
        dic[bb].add(aa)
    else:
        dic[bb].add(aa)


p = []
x = []
for _ in range(q):
    s, t = map(int,input().split())
    p.append(s)
    x.append(t)

res = [0]*n
for i in range(q):
    res[p[i]-1] += x[i]

visited = set()

# 深さが一つ前のやつのresの値を足す
# dfsはおk，ここで累積和を使う発想が出てこなかった
def dfs(node, prev):
    visited.add(node)
    if prev != 0:
        res[node-1] += res[prev-1]
    for i in dic[node]:
        if i not in visited:
            prev = node
            dfs(i, prev)

dfs(1, 0)
print(*res, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5) #再帰関数の呼び出し制限

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


dic = {}
for i in range(n-1):
    aa, bb = map(int,input().split())

    if aa not in dic:
        dic[aa] = set()
        dic[aa].add(bb)
    else:
        dic[aa].add(bb)

    if bb not in dic:
        dic[bb] = set()
        dic[bb].add(aa)
    else:
        dic[bb].add(aa)


p = []
x = []
for _ in range(q):
    s, t = map(int,input().split())
    p.append(s)
    x.append(t)

res = [0]*n
for i in range(q):
    res[p[i]-1] += x[i]

visited = set()

# 深さが一つ前のやつのresの値を足す
def dfs(node, prev):
    visited.add(node)
    if prev != 0:
        res[node-1] += res[prev-1]
    for i in dic[node]:
        if i not in visited:
            prev = node
            dfs(i, prev)

dfs(1, 0)
print(*res, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(3 * 10 ** 5)


def main() -> None:
    def dfs(v, par, cnt):
        ans[v] = cnt + vs[v]
        for c in edges[v]:
            if c == par:
                continue
            dfs(c, v, ans[v])

    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edges[a].append(b)
        edges[b].append(a)
    vs = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        vs[p - 1] += x
    ans = [0] * N
    dfs(0, -1, 0)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

import queue
q = queue.Queue()
q.put(0)
visited = [False for _ in range(n)]
visited[0]=True
while not q.empty():
  i = q.get()
  for j in G[i]:
    if visited[j]:
      continue
    cnt[j] += cnt[i]
    q.put(j)
    visited[j] = True

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*n
used=[0]*n
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

def f(now):
    for to in  edges[now]:
        if used[to]:continue
        cnt[to]+=cnt[now]
        used[to]=1
        f(to)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

used[0]=1
f(0)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*n
used=[0]*n
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

def f(now):
    for to in  edges[now]:
        if used[to]:continue
        cnt[to]+=cnt[now]
        used[to]=1
        f(to)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

used[0]=1
f(0)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

tree = [[] for _ in range(n)]
edge = collections.deque(edge)
flag = [False] * n
flag[0] = True
while len(edge) != 0:
    a, b = edge.popleft()
    if flag[a - 1]:
        tree[a - 1].append(b - 1)
        flag[b - 1] = True
    elif flag[b - 1]:
        tree[b - 1].append(a - 1)
        flag[a - 1] = True
    else:
        edge.append((a, b))

que = collections.deque([0])
while len(que) != 0:
    i = que.popleft()
    for j in tree[i]:
        counter[j] += counter[i]
        que.append(j)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

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

tree = [[] for _ in range(n)]
edge.sort()
edge = collections.deque(edge)
flag = [False] * n
flag[0] = True
while len(edge) != 0:
    a, b = edge.popleft()
    if flag[a - 1]:
        tree[a - 1].append(b - 1)
        flag[b - 1] = True
    elif flag[b - 1]:
        tree[b - 1].append(a - 1)
        flag[a - 1] = True
    else:
        edge.append((a, b))

que = collections.deque([0])
while len(que) != 0:
    i = que.popleft()
    counter[i] += p[i]
    for j in tree[i]:
        counter[j] = counter[i]
        que.append(j)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

n, q = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(n - 1)]
query = [tuple(map(int, input().split())) for _ in range(q)]

tree = [[] for _ in range(n)]
edge.sort()
edge = collections.deque(edge)
flag = [False] * n
flag[0] = True
while len(edge) != 0:
    a, b = edge.popleft()
    if flag[a - 1]:
        tree[a - 1].append(b - 1)
        flag[b - 1] = True
    elif flag[b - 1]:
        tree[b - 1].append(a - 1)
        flag[a - 1] = True
    else:
        edge.append((a, b))

p = [0] * n
for x, y in query:
    p[x - 1] += y
counter = [0] * n

que = collections.deque([0])
while len(que) != 0:
    i = que.popleft()
    counter[i] += p[i]
    for j in tree[i]:
        counter[j] = counter[i]
        que.append(j)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

n, q = map(int, input().split())
edge = collections.deque([tuple(map(int, input().split())) for _ in range(n - 1)])
query = [tuple(map(int, input().split())) for _ in range(q)]

tree = [[] for _ in range(n)]
flag = [False] * n
flag[0] = True
while len(edge) != 0:
    a, b = edge.popleft()
    if flag[a - 1]:
        tree[a - 1].append(b - 1)
        flag[b - 1] = True
    elif flag[b - 1]:
        tree[b - 1].append(a - 1)
        flag[a - 1] = True
    else:
        edge.append((a, b))

p = [0] * n
for x, y in query:
    p[x - 1] += y
counter = [0] * n

que = collections.deque([0])
while len(que) != 0:
    i = que.popleft()
    counter[i] += p[i]
    for j in tree[i]:
        counter[j] = counter[i]
        que.append(j)

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

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

n, q = map(int, input().split())
adj = [[] for _ in range(n + 1)]
lazy = [0] * (n + 1)

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

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

qu = Queue()
qu.put((1, 0))
while not qu.empty():
    pair = qu.get()
    u = pair[0]
    for v in adj[u]:
        if v == pair[1]: continue
        lazy[v] += lazy[u]
        qu.put((v, u))

for i in range(1, n + 1):
    print(str(lazy[i]), end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n , q = map(int, input().split())
r = [[]for i in range(n)]
s = [0]*n
v = [0]*n
for i in range(n-1):
    a , b = map(int, input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
for i in range(q):
    p , x = map(int, input().split())
    s[p-1]+=x

def dfs(now):
    v[now]=1
    for i in r[now]:
        if v[i]==0:
            s[i]+=s[now]
            dfs(i)
dfs(0)
print(' '.join(list(map(str,s))))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
N, Q = map(int,input().split())
graph = [[] for _ in range(N+1)]
point = [0] * (N+1)
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    point[p] += x

# dfsをします。
def dfs(x, parent):
    point[x] += point[parent]
    for i in range(len(graph[x])):
        if graph[x][i] == parent:
            continue
        dfs(graph[x][i], x)
dfs(1, 0)
point_str = [str(n) for n in point]
ans = ' '.join(point_str[1:])
print(ans)

Submission status: Time Limit Exceeded

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

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

# dfsをします。
def dfs(x, parent):
    point[x] += point[parent]
    for i in range(len(graph[x])):
        if graph[x][i] == parent:
            continue
        dfs(graph[x][i], x)
dfs(1, 0)
point_str = [str(n) for n in point]
ans = ' '.join(point_str[1:])
print(ans)

Submission status: Time Limit Exceeded

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

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

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

res = [0] * N
def dfs(n, p, s):
  res[n] = s
  for nei in adj[n]:
    if nei != p:
      dfs(nei, n, s+scores[nei])

dfs(0,-1,scores[0])

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
import sys
sys.setrecursionlimit(500000)

n, q, *d = map(int, open(0).read().split())
res = [0] * n
edge = [[] for _ in res]

for a, b in zip(d[:2*n-2:2],d[1:2*n-2:2]):
    a -= 1;b -= 1
    edge[a] += b,
    edge[b] += a,

def dfs(v, p):
    for j in edge[v]:
        if j != p:  # 親は弾く
            res[j] += res[v]
            dfs(j, v)

for p, x in zip(d[2*n-2::2],d[2*n-1::2]):
    p -= 1
    res[p] += x

dfs(0, -1)

print(*res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

n, q = map(int, input().split())
res = [0] * n
edge = [[] for _ in res]

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

def dfs(v, p):
    for j in edge[v]:
        if j != p:  # 親は弾く
            res[j] += res[v]
            dfs(j, v)

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

dfs(0, -1)

print(*res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
n, q = map(int, input().split())
res = [0] * n
edge = [[] for _ in res]

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

import sys
sys.setrecursionlimit(500000)
def dfs(v, p):
    for j in edge[v]:
        if j != p:  # 親は弾く
            res[j] += res[v]
            dfs(j, v)

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

dfs(0, -1)

print(*res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n, q = map(int, input().split())
res = [0] * n
edge = [[] for _ in res]

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

import sys
sys.setrecursionlimit(500000)
def dfs(v, p):
    for j in edge[v]:
        if j != p:  # 親は弾く
            res[j] += res[v]
            dfs(j, v)

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

dfs(0, -1)

print(*res)

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
ans = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x
def dfs(c, parent):
    for child in tree[c]:
        if child == parent:
            continue
        else:
            ans[child] += ans[c]
            dfs(child, c)
dfs(0, 0)
print(*ans)

Submission status: Time Limit Exceeded

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

fukasa = [0 for _ in range(n)]
fukasamoto = [set([]) for _ in range(n)]
fukasamoto[0].add(0)
kaisuu = 0
settansaku = set([])
setmada = {0}
kouho = 1

while kouho != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		kouho -= 1
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					kouho += 1
					fukasa[k] = kaisuu
					fukasamoto[k] = fukasamoto[i] | {i, k}

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

ansl = [0 for _ in range(n)]
for i in range(n):
	tmpans = 0
	for j in fukasamoto[i]:
		tmpans += kasan[j]
	ansl[i] = tmpans

print(" ".join([str(ansl[i]) for i in range(n)]))

Submission status: Time Limit Exceeded

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

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

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

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

def dfs(v, p):
    if p != -1:
        count[v] += count[p]
    for next_v in G[v]:
        if next_v == p: continue
        dfs(next_v, v)

dfs(0, -1)
print(" ".join(map(str, count)))

Submission status: Time Limit Exceeded

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

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

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

q = [[int(i) for i in input().split()] for j in range(Q)]
count = [0 for i in range(N)]
for i in range(Q):
    p, x = q[i]
    count[p-1] += x

def dfs(v, p):
    if p != -1:
        count[v] += count[p]
    for next_v in G[v]:
        if next_v == p: continue
        dfs(next_v, v)

dfs(0, -1)
print(" ".join(map(str, count)))