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())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = set()
alr.add(0)
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i not in alr:
            que.append(i)
            alr.add(i)
            px[i] += sumq
print(*px)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = [0]
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i not in alr:
            que.append(i)
            alr.append(i)
            px[i] += sumq
print(*px)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = [0]
que.append(0)
ans = [0 for i in range(N)]
ans[0] = px[0]
while que:
    q = que.popleft()
    sumq = ans[q]
    for i in ab[q]:
        if i not in alr:
            que.append(i)
            alr.append(i)
            ans[i] += px[i]+sumq
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = [0]
que.append(0)
ans = [0 for i in range(N)]
ans[0] = px[0]
while que:
    q = que.popleft()
    for i in ab[q]:
        if i not in alr:
            que.append(i)
            alr.append(i)
            ans[i] += px[i]+ans[q]
print(*ans)

Submission status: Time Limit Exceeded

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

def main():
    N, Q = map(int, input().split())
    visited = [False] * N
    c = [0] * N

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

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

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

    def dfs(v, p=-1):
        # p: どの頂点から来たか
        for u in G[v]:
            if u == p:
                continue
            c[u] += c[v]
            dfs(u, v)

    dfs(0)
    print(" ".join([str(i) for i in c]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,q = inpl()
g = [[]for i in range(n)]
c = [0 for i in range(n)]
seen = set()
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for i in range(q):
    a,b = inpl()
    c[a-1] += b
def dfs(node):
    for v in g[node]:
        if v in seen:
            continue
        c[v] += c[node]
        seen.add(v)
        dfs(v) 

seen.add(0)
dfs(0)
for i in c:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,q = inpl()
g = [[]for i in range(n)]
c = [0 for i in range(n)]
seen = set()
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for i in range(q):
    a,b = inpl()
    c[a-1] += b
def dfs(node):
    for v in g[node]:
        if v in seen:
            continue
        c[v] += c[node]
        seen.add(v)
        dfs(v) 

seen.add(0)
dfs(0)
print(*c)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y


N,Q=LI()
TR=[[] for i in range(N+1)]
TR_score = [0] * (N+1)
RES = [-1]*(N+1)

for i in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

for i in range(Q):
    p, x = LI()
    TR_score[p] += x

ST = [(1, TR_score[1])]
while ST:
    i, score = ST.pop()
    RES[i] = score
    for j in TR[i]:
        if RES[j] == -1:
            ST.append((j, score + TR_score[j]))

for value in RES[1:-1]: print(value, end=" ")
print(RES[-1])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1)]
PX=[list(map(int,input().split())) for i in range(Q)]

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

pt= [0 for i in range(N+1)]
for a,b in AB:
    eda[a].append(b)
    eda[b].append(a)
for p,x in PX:
    pt[p]+=x
eda=[sorted(i) for i in eda]

stack=[[1,eda[1]]]
v=set()
v.add(1)
while stack:
    while stack[-1][1]:
        a=stack[-1][1].pop()
        if not a in v:
            v.add(a)
            pt[a]+=pt[stack[-1][0]]
            stack.append([a,eda[a]])
    stack.pop()
print(" ".join(list(map(str,pt[1:]))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

tree=[[] for i in range(n)]
for i in range(n-1):
 i,j=map(int,input().split())
 tree[i-1].append(j-1)
 tree[j-1].append(i-1)

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

cnt=[-1]*n
cnt[0]=t_cnt[0]

seen=([0])

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 for i in tree[x]:
#  if cnt[i]==-1:
#  if i in seen:
#   continue
#  else:
   if i not in seen:
    seen.append(i)
    dq.append(i)
    cnt[i]=cnt[x]+t_cnt[i]

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

tree=[[] for i in range(n)]
for i in range(n-1):
 i,j=map(int,input().split())
 tree[i-1].append(j-1)
 tree[j-1].append(i-1)

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

cnt=[-1]*n
cnt[0]=t_cnt[0]

#seen=([0])
seen=[0]

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 for i in tree[x]:
#  if cnt[i]==-1:
   if i in seen:
    continue
   else:
    seen.append(i)
    dq.append(i)
    cnt[i]=cnt[x]+t_cnt[i]

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)


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

A=[[] for i in range(N)]
c=[0]*N

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

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

def dfs(now,prev=-1):
    for next in A[now]:
        if next==prev:continue
        else:
            c[next]+=c[now]
            dfs(next,now)
dfs(0)
print(*c)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion

N,Q = map(int,input().split())
graph = [[False for i in range(N)] for j in range(N)]
visited = [False for i in range(N)]
ans = [0 for i in range(N)]

for i in range(N-1):
  v,u = map(int,input().split())
  v -= 1
  u -= 1
  graph[v][u] = True
  graph[u][v] = True

for i in range(Q):
  node,value = map(int,input().split())
  node -= 1
  ans[node] += value

def dfs(v):
  queue = [v]
  while queue != []:
    now = queue.pop()
    visited[now] = True
    for next in range(N):
      if visited[next]:continue
      if not graph[now][next]:continue
      queue.append(next)
      ans[next] += ans[now]
      
dfs(0)
print(*ans)

Submission status: Time Limit Exceeded

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


n, q = map(int, input().split())
GRAPH = [[] for _ in range(n + 1)]
COUNTS = [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())
    COUNTS[p] += x

def dfs(now, prev):
    for vertex in GRAPH[now]:
        if vertex == prev:
            continue
        else:
            next = vertex
        COUNTS[next] += COUNTS[now]
        dfs(next, now)
dfs(1, 0)

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

Submission status: Time Limit Exceeded

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

def input():
  return sys.stdin.readline()[:-1]

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

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

px=[list(map(int, input().split())) for i in range(Q)]

counter=[0]*(N+1)
for i in range(Q):
  counter[px[i][0]]+=px[i][1]
  
def f(num, prenum=-1, p=0):
  counter[num]+=p
  for postnum in link[num]:
    if postnum==prenum:
      continue
    f(postnum, num, counter[num])
    
f(1)

print(*counter[1:])

Submission status: Time Limit Exceeded

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

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

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

px=[list(map(int, input().split())) for i in range(Q)]

counter=[0]*(N+1)
for i in range(Q):
  counter[px[i][0]]+=px[i][1]
  
def f(num, prenum=-1, p=0):
  counter[num]+=p
  for postnum in link[num]:
    if postnum==prenum:
      continue
    f(postnum, num, counter[num])
    
f(1)

print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

def denpan(oya,ko):
    for i in range(len(ne[ko])):
        if ne[ko][i]!=oya:
            cnt[ne[ko][i]]+=cnt[ko]
            denpan(ko,ne[ko][i])

ne=[[] for i in range(n+1)]
for i in range(n-1):
    ne[ab[i][0]].append(ab[i][1])
    ne[ab[i][1]].append(ab[i][0])
# print(ne)
cnt=[0]*(n+1)
for i in range(q):
    cnt[px[i][0]]+=px[i][1]
# print(cnt)
denpan(1,1)
cnt.remove(0)
print(' '.join(map(str,cnt)))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

def denpan(oya,ko):
    for i in range(len(ne[ko])):
        if ne[ko][i]!=oya:
            cnt[ne[ko][i]]+=cnt[ko]
            denpan(ko,ne[ko][i])

ne=[[] for i in range(n+1)]
for i in range(n-1):
    ne[ab[i][0]].append(ab[i][1])
    ne[ab[i][1]].append(ab[i][0])
# print(ne)
cnt=[0]*(n+1)
for i in range(q):
    cnt[px[i][0]]+=px[i][1]
# print(cnt)
denpan(1,1)
for i in range(1,n+1):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**6)
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

def denpan(oya,ko):
    for i in range(len(ne[ko])):
        if ne[ko][i]!=oya:
            cnt[ne[ko][i]]+=cnt[ko]
            denpan(ko,ne[ko][i])

ne=[[] for i in range(n+1)]
for i in range(n-1):
    ne[ab[i][0]].append(ab[i][1])
    ne[ab[i][1]].append(ab[i][0])
# print(ne)
cnt=[0]*(n+1)
for i in range(q):
    cnt[px[i][0]]+=px[i][1]
# print(cnt)
denpan(1,1)
for i in range(1,n+1):
    print(cnt[i])

Submission status: Time Limit Exceeded

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

def main():
    N, Q = map(int, input().split())
    visited = [False] * N
    c = [0] * N

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

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

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

    def dfs(v, p=-1):
        # p: どの頂点から来たか
        for u in G[v]:
            if u == p:
                continue
            c[u] += c[v]
            dfs(u, v)

    dfs(0)
    print(" ".join([str(i) for i in c]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

c = None
G = None

# p: どの頂点から来たか
def dfs(v, p=-1):
    for u in G[v]:
        if u == p:
            continue
        c[u] += c[v]
        dfs(u, v)


def main():
    global c
    global G

    N, Q = map(int, input().split())
    visited = [False] * N
    c = [0] * N

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

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

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

    dfs(0, 0)
    print(" ".join([str(i) for i in c]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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

    visited = [False] * N

    def dfs(v, d):
        if visited[v]:
            return
        c[v] += d
        visited[v] = True
        val = c[v]
        for child in G[v]:
            dfs(child, val)

    dfs(0, 0)
    print(" ".join([str(i) for i in c]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    G = []
    for i in range(N):
        G.append([False] * N)

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

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

    visited = [False] * N

    def dfs(v, d):
        if visited[v]:
            return
        c[v] += d

        visited[v] = True
        val = c[v]
        for i, n in enumerate(G[v]):
            if n:
                dfs(i, val)

    dfs(0, 0)
    print(" ".join([str(i) for i in c]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,q = map(int,input().split())
ki = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
point = [0]*n
for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    point[p] += x
def dfs(now,last ,add):
    point[now] += add
    for next in ki[now]:
        if next == last:continue
        dfs(next,now,point[now])
dfs(0,-1,0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
input = sys.stdin.readline

N,Q=map(int,input().split())
c=[0]*N#count

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

for i in range(N-1):
    a,b =map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
    
    
for i in range(Q):
    p,x =map(int,input().split())
    p-=1
    c[p]+=x
    
q=queue.Queue()
q.put((0,-1))


while not q.empty():
    v,prev=q.get()
    for i in range(len(to[v])):
        v_next=to[v][i]
        if v_next!=prev:
            q.put((v_next,v))
            c[v_next]+=c[v]

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

Submission status: Time Limit Exceeded

Solution code:
import queue

N,Q=map(int,input().split())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*N#count
p=[0]*Q
x=[0]*Q

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

for i in range(N-1):
    a[i],b[i] =map(int,input().split())
    a[i]-=1
    b[i]-=1
    to[a[i]].append(b[i])
    to[b[i]].append(a[i])
    
    
for i in range(Q):
    p[i],x[i] =map(int,input().split())
    p[i]-=1
    c[p[i]]+=x[i]
    
q=queue.Queue()
q.put((0,-1))


while not q.empty():
    v,prev=q.get()
    for i in range(len(to[v])):
        v_next=to[v][i]
        if v_next!=prev:
            q.put((v_next,v))
            c[v_next]+=c[v]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = [list(map(int,readline().split())) for i in range(N-1)]
co = [list(map(int,readline().split())) for i in range(Q)]
 
ki.sort()

kid = deque(ki)
ver = [0 for i in range(N)]
check = [False for i in range(N)]
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = [list(map(int,readline().split())) for i in range(N-1)]
co = [list(map(int,readline().split())) for i in range(Q)]
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = [0 for i in range(N)]
check = [False for i in range(N)]
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid.append(k)


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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
for i in range(N):
    ver.append([0,False])
 
for c in co:
    ver[c[0]-1][0] += c[1]

ver[0][1] = True

while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)

ans = [ver[i][0] for i in range(N)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
for i in range(N):
    ver.append([0,False])
 
for i in range(Q):
    ver[co[i][0]-1][0] += co[i][1]

ver[0][1] = True

while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)

ans = [ver[i][0] for i in range(N)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from collections import deque
 
N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[0])
 
#print(ki)
 
kid = deque(ki)
#print(kid)
 
ver = []
for i in range(N):
    ver.append([0,False])
 
for i in range(Q):
    ver[co[i][0]-1][0] += co[i][1]
 
ver[0][1] = True
#print(ver)
 
 
while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)
 
for i in range(N):
    print(ver[i][0],end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

#print(ki)

kid = deque(ki)
#print(kid)

ver = []
for i in range(N):
    ver.append([0,False])
 
for i in range(Q):
    ver[co[i][0]-1][0] += co[i][1]

ver[0][1] = True
#print(ver)


while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
#print(ki)

kid = deque(ki)
#print(kid)

ver = []
for i in range(N):
    ver.append([0,False])
 
for i in range(Q):
    ver[co[i][0]-1][0] += co[i][1]

ver[0][1] = True
#print(ver)


while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort()
#print(ki)

kid = deque(ki)
#print(kid)

ver = []
for i in range(N):
    ver.append([0,False])
 
for i in range(Q):
    ver[co[i][0]-1][0] += co[i][1]

ver[0][1] = True
#print(ver)


while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from collections import deque
 
N,Q = map(int,readline().split())
ki = [list(map(int,readline().split())) for i in range(N-1)]
co = [list(map(int,readline().split())) for i in range(Q)]
 
ki.sort()
#print(ki)
 
kid = deque(ki)
#print(kid)
 
ver = [[0,False] for i in range(N)]
 
for i in range(Q):
    ver[co[i][0]-1][0] += co[i][1]
 
ver[0][1] = True
#print(ver)
 
 
while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)
 
'''
for i in range(N-1):
    if ver[ki[i][1]-1] != ver2[ki[i][1]-1]:
        ver[ki[i][0]-1] += ver[ki[i][1]-1]
    else:
        ver[ki[i][1]-1] += ver[ki[i][0]-1]
'''
for i in range(N):
    print(ver[i][0],end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = [list(map(int,readline().split())) for i in range(N-1)]
co = [list(map(int,readline().split())) for i in range(Q)]
 
ki.sort()
#print(ki)

kid = deque(ki)
#print(kid)
 
ver = [[0,False] for i in range(N)]
 
for i in range(Q):
    ver[co[i][0]-1][0] += co[i][1]

ver[0][1] = True
#print(ver)


while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)

'''
for i in range(N-1):
    if ver[ki[i][1]-1] != ver2[ki[i][1]-1]:
        ver[ki[i][0]-1] += ver[ki[i][1]-1]
    else:
        ver[ki[i][1]-1] += ver[ki[i][0]-1]
'''
for i in range(N):
    print(ver[i][0],end=' ')