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:
from collections import deque

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

graph, parents, values, visited = [],[],[],[]
for _ in range(N):
  graph.append([])
  parents.append(-1)
  values.append(0)
  visited.append(False)

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())
  values[p-1] += x

bfs_queue = deque()
bfs_queue.append(0)
bfs_queue_len = 1
while bfs_queue_len:
  cur = bfs_queue.popleft()
  bfs_queue_len -= 1
  visited[cur] = True

  for other in graph[cur]:
    if not visited[other]:
      parents[other] = cur
      values[other] += values[cur]
      bfs_queue_len += 1
      bfs_queue.append(other)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
  a,b=map(int,input().split())
  e=[[]for i in range(a)]

  for i in range(a-1):
    c1,c2=map(int,input().split())
    e[c1-1].append(c2-1)
    e[c2-1].append(c1-1)

  g=[[]for i in range(a)]
  f=[[0,-1]]
  ans=[0 for _ in range(a)]
  for i in range(b):
    ten,p=map(int,input().split())
    ans[ten-1]+=p
  i=0
  while len(f)!=0:
    i,fr=f.pop(0)
    for j in e[i]:
      if j==fr:
        continue
      else:
        ans[j]+=ans[i]
        f.append([j,i]) 
  print(*ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
input = sys.stdin.readline
N, Q = map(int, input().split())

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

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


q = [1]
while q:
    now = q.pop()
    for next in tree[now]:
        values[next] += values[now]
        q.append(next)


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


n,q=map(int,input().split())
ki=[[] for i in range(n+1)]
ki[0]="null"
 
for i in range(n-1):
    a,b=map(int,input().split())
    ki[a].append(b)
    ki[b].append(a)
 
scores=[0 for i in range(n+1)]
scores[0]="null"
for i in range(q):
    p,x=map(int,input().split())
    scores[p]+=x
 
 
ans=[0 for i in range(n+1)]
ans[0]="null"
point=0

ed=[]
 
def tansa(n,point):
    ed.append(n)
    point+=scores[n]
    for p in ki[n]:
        if not p in ed:
            tansa(p,point)
    else:
        ans[n]=point
        
tansa(1,0)
 
ans=ans[1:]
ans=[str(i) for i in ans]
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
input = sys.stdin.readline
N, Q = map(int, input().split())

tree = [[] for i in range(N+1)]
values = [0] * (N+1)
visit = [False]*(N+1)
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

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


q = queue.Queue()
q.put(1)
visit[1] = True
while (not q.empty()):
    now = q.get()
    for next in tree[now]:
        if not visit[next]:
            values[next] += values[now]
            visit[next] = True
            q.put(next)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

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

tree = [[] for i in range(N+1)]
values = [0] * (N+1)
visit = [False]*(N+1)
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

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


q = queue.Queue()
q.put(1)
visit[1] = True
while (not q.empty()):
    now = q.get()
    for next in tree[now]:
        if not visit[next]:
            values[next] += values[now]
            visit[next] = True
            q.put(next)

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

Submission status: Time Limit Exceeded

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

def dfs(i, d):
  visited[i] = True
  ans[i] = d + pp[i]
  for j in edges[i]:
    if not visited[j]:
      dfs(j, d + pp[i])

n, q = map(int, input().split())
ans = [0 for _ in range(n)]
visited = [False for _ in range(n)]
edges = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)
pp = [0 for _ in range(n)]
for _ in range(q):
  p, x = map(int, input().split())
  pp[p-1] += x
dfs(0, 0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]

e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[]for i in range(a)]
f=deque()
f.append((0,-1))
ans=[0 for _ in range(a)]
for i in range(b):
  ten,p=map(int,input().split())
  ans[ten-1]+=p
i=0
while len(f)!=0:
  i,fr=f.popleft()
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i]) 
print(*ans)

Submission status: Time Limit Exceeded

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

t = [[] for _ in range(n)]
c = [0] * n

for a, b in ab:
    t[a-1].append(b-1)
    t[b-1].append(a-1)

for p, x in px:
    c[p-1] += x

ans = [0] * n

def func(x, v, p):
    w = v + c[x]
    ans[x] = w
    for s in t[x]:
        if s != p:
            func(s, w, x)
    return

func(0,0,0)

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

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]

e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[]for i in range(a)]
f=[[0,-1]]
ans=[0 for _ in range(a)]
for i in range(b):
  ten,p=map(int,input().split())
  ans[ten-1]+=p
i=0
while len(f)!=0:
  i,fr=f.pop(0)
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i]) 
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[list(map(int,input().split())) for i in range(b)]
e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[]for i in range(a)]
f=[[0,-1]]
ans=[0 for _ in range(a)]
for i in d:
  ans[i[0]-1]=ans[i[0]-1]+i[1]
i=0
while len(f)!=0:
  i,fr=f.pop(0)
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i])



  

  
print(*ans)

Submission status: Time Limit Exceeded

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

t = dict()
c = dict()
for i in range(n):
    t[i] = []
    c[i] = 0

for a, b in ab:
    t[a-1].append(b-1)
    t[b-1].append(a-1)

for p, x in px:
    c[p-1] += x

ans = [0] * n

def func(x, v, p):
    w = v + c[x]
    ans[x] = w
    for s in t[x]:
        if s != p:
            func(s, w, x)
    return

func(0,0,0)

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

Submission status: Time Limit Exceeded

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

def dfs(v, p, tree, cnt):
    for u in tree[v]:
        if u != p:
            cnt[u] += cnt[v]
            dfs(u, v, tree, cnt)


def main():
    # ai may be not a parent of bi. -> set a skip condition (p) in dfs
    N, Q = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    P = tuple(tuple(map(int, input().split())) for _ in range(Q))
    T = [[] for _ in range(N + 1)]
    cnt = [0] * (N + 1)
    for a, b in A:  # set tree relations
        T[a] += [b]
        T[b] += [a]
    for p, x in P:  # increment on roots
        cnt[p] += x
    dfs(1, -1, T, cnt)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

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)]
values=[0]*(n+1)

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

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

#print(graph)

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

dfs(1,0,0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
 
stdin=sys.stdin
sys.setrecursionlimit(10 ** 7)
ni=lambda:int(ns())
na=lambda:list(map(int,stdin.readline().split()))
ns=lambda:stdin.readline().rstrip()  # ignore trailing spaces


n,q=na()
AB=[[int(x) for x in na()] for _ in range(n-1)]
PX=[[int(x) for x in na()] for _ in range(q)]

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

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

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

#print(graph)

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

dfs(1,0,0)

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split(" "))
 
ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
vs = [list(map(int, input().split(" ")))  for _ in range(Q)]
 
flags = [True]+[False]*(N-1)
dic = [[] for _ in range(N)]
rlt = [0]*N
 
for i in range(N-1):
  dic[ns[i][1]-1] += [ns[i][0]-1]
  dic[ns[i][0]-1] += [ns[i][1]-1]
  
for j in range(Q):
  rlt[vs[j][0]-1] += vs[j][1]
  
for k in range(N):
  for l in dic[k]:
    if flags[l]:
      continue
    else:
      rlt[l] += rlt[k]
      flags[l] = True
    
print(" ".join(map(str, rlt)))

Submission status: Time Limit Exceeded

Solution code:
(n,q),*t=[map(int,t.split())for t in open(0)]
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
for a,b in t:
 if~-n:n-=1;e[a-1]+=b-1,;e[b-1]+=a-1,
 else:d[a-1]+=b
while s:
 v=s.pop()
 for w in e[v]:
  if f[w]:d[w]+=d[v];s+=w,;f[w]=0
print(*d)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split(" "))
 
ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
vs = [list(map(int, input().split(" ")))  for _ in range(Q)]
ns = sorted(ns)

flags = [True]+[False]*(N-1)
dic = [[] for _ in range(N)]
rlt = [0]*N
 
for i in range(N-1):
  if flags[ns[i][1]-1]:
    dic[ns[i][1]-1] += [ns[i][0]-1]
  else:
    dic[ns[i][0]-1] += [ns[i][1]-1]
    flags[ns[i][1]-1] = True
  
for j in range(Q):
  rlt[vs[j][0]-1] += vs[j][1]
  
for k in range(N):
  for l in dic[k]:
    rlt[l] += rlt[k]
    
    
print(" ".join(map(str, rlt)))

Submission status: Time Limit Exceeded

Solution code:
I=lambda:map(int,input().split())
n,q=I()
s=[0]
d=s*n
e=[[]for _ in d]
while~-n:n-=1;a,b=I();e[a-1]+=b-1,;e[b-1]+=a-1,
while q:q-=1;p,x=I();d[p-1]-=x
d[0]*=-1
while s:
 v=s.pop()
 for w in e[v]:
  if d[w]<w:d[w]=d[v]-d[w];s+=w,
print(*d)

Submission status: Time Limit Exceeded

Solution code:
(n,q),*t=[map(int,t.split())for t in open(0)]
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
for a,b in t[:-q]:e[a-1]+=b-1,;e[b-1]+=a-1,
for p,x in t[-q:]:d[p-1]+=x
while s:
 v=s.pop()
 for w in e[v]:
  if f[w]:f[w]=0;d[w]+=d[v];s+=w,
print(*d)

Submission status: Time Limit Exceeded

Solution code:
# ABC138D - Ki
import sys
sys.setrecursionlimit(10 ** 7)

def dfs(v, p, tree, cnt):
    for u in tree[v]:
        if u != p:
            cnt[u] += cnt[v]
            dfs(u, v, tree, cnt)


def main():
    N, Q = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    P = tuple(tuple(map(int, input().split())) for _ in range(Q))
    T = [[] for _ in range(N + 1)]  # T[i] := children of vertex i
    cnt = [0] * (N + 1)
    for a, b in A:  # set tree relations
        T[a] += [b]
        T[b] += [a]
    for p, x in P:  # increment on roots
        cnt[p] += x
    dfs(1, -1, T, cnt)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
(n,q),*t=[map(int,t.split())for t in open(0)]
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
for a,b in t[:-q]:e[a-1]+=b-1,;e[b-1]+=a-1,
for p,x in t[-q:]:d[p-1]+=x
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d)

Submission status: Time Limit Exceeded

Solution code:
(n,q),*t=[map(int,t.split())for t in open(0)]
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
for a,b in t:
 if~-n:n-=1;e[a-1]+=b-1,;e[b-1]+=a-1,
 else:d[a-1]+=b
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d)

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
d = {}
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}
counter = [0] * (N + 1)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    counter[p] += x

nodes = [1]
visit = set()
while nodes:
    node = nodes.pop()
    visit.add(node)
    v = counter[node]
    for child in d[node]:
        if child not in visit:
            nodes.append(child)
            counter[child] += v
print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
d = {}
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}
counter = [0] * (N + 1)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    counter[p] += x

parents = {1}
visit = set()
while True:
    children = set()
    for parent in parents:
        if parent in visit:
            continue
        visit.add(parent)
        v = counter[parent]
        children |= d[parent]
        for child in d[parent]:
            if child in visit:
                continue
            counter[child] += v
    if len(children) == 0:
        break
    parents = children
print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
I=lambda:map(int,input().split())
n,q=I()
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
while~-n:n-=1;a,b=I();e[a-1]+=b-1,;e[b-1]+=a-1,
while q:q-=1;p,x=I();d[p-1]+=x
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d)

Submission status: Time Limit Exceeded

Solution code:
I=lambda:map(int,input().split())
n,q=I()
s=[1]
d=[0]*-~n
f=[0,0]+s*n
e=[[]for _ in d]
while~-n:n-=1;a,b=I();e[a]+=b,;e[b]+=a,
while q:q-=1;p,x=I();d[p]+=x
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d[1:])

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
d = {}
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}
counter = [0] * (N + 1)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    counter[p] += x

parents = {1}
while True:
    children = set()
    for parent in parents:
        v = counter[parent]
        for child in d[parent]:
            d[child].remove(parent)
            children.add(child)
            counter[child] += v
    if len(children) == 0:
        break
    parents = children
print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
I=lambda:map(int,input().split());n,q=I();s=[0];d=s*n;f=s+[1]*n;e=[[]for _ in d]
while~-n:n-=1;a,b=I();e[a-1]+=b-1,;e[b-1]+=a-1,
while q:q-=1;p,x=I();d[p-1]+=x
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d)

Submission status: Time Limit Exceeded

Solution code:
N,Q=list(map(int,input().strip().split(' ')))
gr=[[] for _ in range(N)]
val=[0]*N
for _ in range(N-1):
    a,b=list(map(int,input().strip().split(' ')))
    a-=1
    b-=1
    gr[a]+=[b]
    gr[b]+=[a]
for _ in range(Q):
    p,x=list(map(int,input().strip().split(' ')))
    p-=1
    val[p]+=x
ans=[0]*N
stack=[0]
checked=[0]*N
checked[0]=1
ans[0]=val[0]
while stack:
    x=stack.pop()
    for v in gr[x]:
        if checked[v]==0:
            stack+=[v]
            checked[v]=1
            ans[v]=ans[x]+val[v]
ans=[str(x) for x in ans]

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
N,Q=list(map(int,input().strip().split(' ')))
gr=[[] for _ in range(N)]
val=[0]*N
for _ in range(N-1):
    a,b=list(map(int,input().strip().split(' ')))
    a-=1
    b-=1
    gr[a]+=[b]
    gr[b]+=[a]
for _ in range(Q):
    p,x=list(map(int,input().strip().split(' ')))
    p-=1
    val[p]+=x
ans=[0]*N
stack=[0]
checked=[0]*N
checked[0]=1
ans[0]=val[0]
while stack:
    x=stack.pop()
    for v in gr[x]:
        if checked[v]==0:
            stack+=[v]
            checked[v]=1
            ans[v]=ans[x]+val[v]
for x in ans:
    print(x,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
# 深さ優先探索で各直線を考える


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        # 累積和の計算
        ans[u] += ans[v]
        dfs(u, v)


n, q = map(int, input().split())
# tree[i]: 頂点i+1の子どもたち
tree = [[] for i in range(n)]
ans = [0] * n

for _ in range(0, 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())
    ans[p - 1] += x

# 根ノードの頂点 1 から開始
dfs(0, -1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
# 深さ優先探索で各直線を考える


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        # 累積和の計算
        ans[u] += ans[v]
        dfs(u, v)


n, q = map(int, input().split())
# tree[i]: 頂点i+1の子どもたち
tree = [[] for i in range(n)]
ans = [0] * n

for _ in range(0, 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())
    ans[p - 1] += x

# 根ノードの頂点 1 から開始
dfs(0, -1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from collections import deque, defaultdict

n, q = list(map(int, input().strip().split(" ")))
edges = defaultdict(set)
for _ in range(n-1):
    a_i, b_i = list(map(int, input().strip().split(" ")))
    # edges[a_i-1].append(b_i-1)
    # edges[b_i-1].append(a_i-1)
    edges[a_i-1].add(b_i-1)
    edges[b_i-1].add(a_i-1)

# p = defaultdict(int)
# counter = defaultdict(int)
counter = [0] * n
p = [0] * n
x = []
for _ in range(q):
    p_i, x_i = list(map(int, input().strip().split(" ")))
    # p[p_i-1] += x_i
    counter[p_i-1] += x_i


parents = deque()
# parents.append(0)
# parents = []
parents.append(0)
visited = set()
while parents:
    parent = parents.popleft()
    # parent = parents.pop()
    if parent in visited:
        continue
    visited.add(parent)
    # counter[parent] += p[parent]
    # print("parent")
    # print(parent, counter[parent])
    for child in edges[parent]:
        if child in visited:
            continue
        # if counter[child] != 0:
        #    continue
        counter[child] += counter[parent]
        # print("child")
        # print(child, counter[child])
        parents.append(child)
        # parents.add(child)

#print(" ".join(list(map(str, counter.values()))))
print(" ".join(list(map(str, counter))))

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from collections import deque, defaultdict

n, q = list(map(int, input().strip().split(" ")))
edges = defaultdict(set)
for _ in range(n-1):
    a_i, b_i = list(map(int, input().strip().split(" ")))
    # edges[a_i-1].append(b_i-1)
    # edges[b_i-1].append(a_i-1)
    edges[a_i-1].add(b_i-1)
    edges[b_i-1].add(a_i-1)

# p = defaultdict(int)
p = [0] * n
x = []
for _ in range(q):
    p_i, x_i = list(map(int, input().strip().split(" ")))
    p[p_i-1] += x_i

# counter = defaultdict(int)
counter = [0] * n

parents = deque()
# parents.append(0)
# parents = []
parents.append(0)
visited = set()
while parents:
    parent = parents.popleft()
    # parent = parents.pop()
    if parent in visited:
        continue
    visited.add(parent)
    counter[parent] += p[parent]
    # print("parent")
    # print(parent, counter[parent])
    for child in edges[parent]:
        if child in visited:
            continue
        # if counter[child] != 0:
        #    continue
        counter[child] += counter[parent]
        # print("child")
        # print(child, counter[child])
        parents.append(child)
        # parents.add(child)

#print(" ".join(list(map(str, counter.values()))))
print(" ".join(list(map(str, counter))))

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    # counter = defaultdict(int)
    counter = [0] * n

    parents = deque()
    # parents.append(0)
    # parents = []
    parents.append(0)
    visited = set()
    while parents:
        parent = parents.popleft()
        # parent = parents.pop()
        if parent in visited:
            continue
        visited.add(parent)
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        for child in edges[parent]:
            if child in visited:
                continue
            # if counter[child] != 0:
            #    continue
            counter[child] = counter[parent]
            # print("child")
            # print(child, counter[child])
            parents.append(child)
            # parents.add(child)

    #print(" ".join(list(map(str, counter.values()))))
    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    edges = defaultdict(set)
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        # edges[a_i-1].append(b_i-1)
        # edges[b_i-1].append(a_i-1)
        edges[a_i-1].add(b_i-1)
        edges[b_i-1].add(a_i-1)

    # p = defaultdict(int)
    p = [0] * n
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    counter = defaultdict(int)

    parents = deque()
    # parents.append(0)
    # parents = []
    parents.append(0)
    visited = set()
    while parents:
        parent = parents.popleft()
        # parent = parents.pop()
        if parent in visited:
            continue
        visited.add(parent)
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        for child in edges[parent]:
            if child in visited:
                continue
            # if counter[child] != 0:
            #    continue
            counter[child] = counter[parent]
            # print("child")
            # print(child, counter[child])
            parents.append(child)
            # parents.add(child)

    print(" ".join(list(map(str, counter.values()))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    edges = defaultdict(set)
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        # edges[a_i-1].append(b_i-1)
        # edges[b_i-1].append(a_i-1)
        edges[a_i-1].add(b_i-1)
        edges[b_i-1].add(a_i-1)

    p = defaultdict(int)
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    counter = defaultdict(int)

    parents = deque()
    # parents.append(0)
    # parents = []
    parents.append(0)
    visited = set()
    while parents:
        parent = parents.popleft()
        # parent = parents.pop()
        if parent in visited:
            continue
        visited.add(parent)
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        if parent in edges:
            for child in edges[parent]:
                if child in visited:
                    continue
                # if counter[child] != 0:
                #    continue
                counter[child] = counter[parent]
                # print("child")
                # print(child, counter[child])
                parents.append(child)
                # parents.add(child)

    print(" ".join(list(map(str, counter.values()))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    edges = defaultdict(set)
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        # edges[a_i-1].append(b_i-1)
        # edges[b_i-1].append(a_i-1)
        edges[a_i-1].add(b_i-1)
        edges[b_i-1].add(a_i-1)

    p = defaultdict(int)
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

Submission status: Time Limit Exceeded

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

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

T = [[]for i in range(N)]

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

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

def dfs(x, p):
    for j in T[x]:
        if j == p:
            continue
        X[j] += X[x]
        dfs(j, x)

dfs(0, -1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
 
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):
    ans[n] = ans[frm] + cost[n]
    for to in edge[n]:
        if ans[to] != -1:
            continue
        dfs(n, to)
 
dfs(-1, 0)
print(" ".join([str(item) for item in ans[:-1]]))

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    counter = defaultdict(int)

    # parents = deque()
    # parents.append(0)
    parents = set()
    parents.add(0)
    visited = set()
    while parents:
        # parent = parents.popleft()
        parent = parents.pop()
        if parent in visited:
            continue
        visited.add(parent)
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        if parent in edges:
            for child in edges[parent]:
                if child in visited:
                    continue
                # if counter[child] != 0:
                #    continue
                counter[child] = counter[parent]
                # print("child")
                # print(child, counter[child])
                # parents.append(child)
                parents.add(child)

    print(" ".join(list(map(str, counter.values()))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    edges = defaultdict(set)
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        # edges[a_i-1].append(b_i-1)
        # edges[b_i-1].append(a_i-1)
        edges[a_i-1].add(b_i-1)
        edges[b_i-1].add(a_i-1)

    p = defaultdict(int)
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

Submission status: Time Limit Exceeded

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

def calc():
  
  def dfs(v,val):
    cnt[v]+=val
    checked[v]=1
    for u in g[v]:
      if checked[u]==1:
        continue
      dfs(u,cnt[v])

  n,q=map(int,input().split())
  cnt=[0]*(n+1)
  g=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
  for _ in range(q):
    v,val=map(int,input().split())
    cnt[v]+=val
  checked=[0]*(n+1)
  checked[1]=1
  dfs(1,0)
  print(*cnt[1:])

calc()

Submission status: Time Limit Exceeded

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

def dfs(v,val):
  cnt[v]+=val
  checked[v]=1
  for u in g[v]:
    if checked[u]==1:
      continue
    dfs(u,cnt[v])

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
for _ in range(q):
  v,val=map(int,input().split())
  cnt[v]+=val
checked=[0]*(n+1)
checked[1]=1
dfs(1,0)
print(*cnt[1:])

Submission status: Time Limit Exceeded

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

def dfs(v,val):
  cnt[v]+=val
  for u in g[v]:
    if checked[u]==1:
      continue
    checked[u]=1
    dfs(u,cnt[v])

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
for _ in range(q):
  v,val=map(int,input().split())
  cnt[v]+=val
checked=[0]*(n+1)
checked[1]=1
dfs(1,0)
print(*cnt[1:])