Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,q = map(int,input().split())
p = []
x = []
arr = [[] for i in range(n)]
ans = [0 for i in range(n)]
omosa = [0 for i in range(n)]

for i in range(n-1):
    a,b = map(int,input().split())
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(q):
    tmpp,tmpx = map(int,input().split())
#    p.append(tmpp-1)
#    x.append(tmpx)
    omosa[tmpp-1] += tmpx

#for i in range(q):
#    omosa[p[i]] +=x[i]

def dfs(start, oya, weight): #weightは自分より上のノードの重さの和
    ans[start] = weight + omosa[start]
    for child in arr[start]:
        if child != oya:
            dfs(child, start, ans[start])
 
dfs(0,-1,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,q = map(int,input().split())
p = []
x = []
arr = [[] for i in range(n)]
ans = [0 for i in range(n)]
omosa = [0 for i in range(n)]

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

for i in range(q):
    omosa[p[i]] +=x[i]

def dfs(start, oya, weight): #weightは自分より上のノードの重さの和
    ans[start] = weight + omosa[start]
    for child in arr[start]:
        if child != oya:
            dfs(child, start, ans[start])
 
dfs(0,-1,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

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

adj = [[] for _ in range(N)]

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

def dfs(node, parent):
    for child in adj[node]:
        if child == parent: continue
        values[child] += values[node]
        dfs(child, node)

dfs(0, -1)

print(*values, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
#/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

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

adj = [[] for _ in range(N)]

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

def dfs(node, parent):
    for child in adj[node]:
        if child == parent: continue
        values[child] += values[node]
        dfs(child, node)

dfs(0, -1)

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

Submission status: Time Limit Exceeded

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

g = {}
for a, b in ab:
    if a in g: g[a].append(b)
    else: g[a] = [b]
    if b in g: g[b].append(a)
    else: g[b] = [a]

cnt = [0]*(N+1)

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

temp = [1]
visited = [0]*(N+1)
visited[1] = 1

while temp:
    q = temp.pop()   
    for i in g[q]:
        if visited[i] == 0:
            temp.append(i)
            visited[i] = 1
            cnt[i] += cnt[q]
print(*cnt[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

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

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

l=[0]*n
l[0]=1

def dfs(now,last=-1):
    for to in edge[now]:
        if to==last:continue
        ans[to]+=ans[now]
        dfs(to,now)
dfs(0)


for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

node = [0] * (N+1)
nxt = [[] for _ in range(N+1)]

#for ab in AB:
    #a, b = ab[0], ab[1]
for _ in range(N-1):
    a,b = map(int, input().split())
    nxt[a].append(b)
    nxt[b].append(a)

#for px in PX:
    #p,x = px[0], px[1]
for _ in range(Q):
    p,x = map(int, input().split())
    node[p] += x

visited = [False] * (N+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    v = q.get()
    visited[v] = True
    for nv in nxt[v]:
        if not visited[nv]:
            node[nv] += node[v]
            q.put(nv)

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

Submission status: Time Limit Exceeded

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

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

def dfs(i,j):
    nex=g[i]
    for d in nex:
        if d==j: continue
        #print(d)
        lis[d]+=lis[i]
        dfs(d,i)

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

Submission status: Time Limit Exceeded

Solution code:
import queue

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

node = [0] * (N+1)
nxt = [[] for _ in range(N+1)]

for ab in AB:
    a, b = ab[0], ab[1]
    nxt[a].append(b)
    nxt[b].append(a)

for px in PX:
    p,x = px[0], px[1]
    node[p] += x

visited = [False] * (N+1)
q = queue.Queue()
q.put(1)
visited[1] = True
while not q.empty():
    v = q.get()
    visited[v] = True
    for nv in nxt[v]:
        if not visited[nv]:
            node[nv] += node[v]
            q.put(nv)

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

Submission status: Time Limit Exceeded

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

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

def dfs(i,j,k):
    nex=g[i]
    lis[i]=k
    for d in nex:
        if d==j: continue
        #print(d)
        nk=k+lis[d]
        dfs(d,i,nk)

dfs(0,-1,lis[0])
print(*lis)

Submission status: Time Limit Exceeded

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

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

def dfs(i,j,k):
    nex=g[i]
    lis[i]=k
    for d in nex:
        if d==j: continue
        nk=k+lis[d]
        dfs(d,i,nk)

dfs(0,-1,lis[0])
print(*lis)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import deque

def main():
    n, q = map(int, input().split())
    link = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        link[a].append(b)
        link[b].append(a)
    manip = [list(map(int, input().split())) for _ in range(q)]

    child = [[] for _ in range(n+1)]
    parent = [0 for _ in range(n+1)]
    unchecked = [True for _ in range(n+1)]
    unchecked[1] = False
    que = deque([1])
    while que:
        p = que.popleft()
        for l in link[p]:
            if unchecked[l]:
                unchecked[l] = False
                child[p].append(l)
                parent[l] = p
                que.append(l)

    cnt = [0 for _ in range(n+1)]
    for m in manip:
        node, x = m
        cnt[node] += x

    que = deque([1])
    while que:
        node = que.pop()
        cnt[node] += cnt[parent[node]]
        que.extend(child[node])

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import deque

def main():
    n, q = map(int, input().split())
    link = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        link[a].append(b)
        link[b].append(a)
    manip = [list(map(int, input().split())) for _ in range(q)]

    child = [[] for _ in range(n+1)]
    unchecked = [True for _ in range(n+1)]
    unchecked[1] = False
    que = deque([1])
    while que:
        parent = que.popleft()
        for l in link[parent]:
            if unchecked[l]:
                unchecked[l] = False
                child[parent].append(l)
                que.append(l)

    cnt = [0 for _ in range(n+1)]
    for m in manip:
        p, x = m
        que = deque([p])
        while que:
            node = que.popleft()
            cnt[node] += x
            for c in child[node]:
                que.append(c)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

mp=[[x] for x in range(1,n+1)]
while len(star)>1 or star[0]!=1:
    nstar=[]
    for x in star:
        w=L[x-1][0]
        if x!=1:
            mp[w-1] += mp[x-1]
            L[w-1].remove(x)
        if w not in nstar:
            nstar.append(w)
    star=nstar

ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    for y in mp[p-1]:
        ans[y-1] += x
ans=[str(x) for x in ans]
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10**9)

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

# print('G', G)

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


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


dfs(0, -1)

# print('V', V)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10**9)

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

# print('G', G)

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


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


dfs(0, -1)

# print('V', V)

for v in V:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(node,cnt,par):
  for nd in tree[node]:
    if nd == par:
      continue
    counter[nd] += cnt
    dfs(nd,cnt+p[nd],node)
    


N,Q= map(int,input().split())
tree = {}
p = {}
counter = [0]*(N+1)
for i in range(1,N+1):
  tree[i] = []
  p[i] = 0
  
for i in range(N-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  
for i in range(Q):
  p_i,x = map(int,input().split())
  p[p_i] += x
  counter[p_i] += x

dfs(1,p[1],0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(node,cnt):
  for nd in tree[node]:
    if visited[nd] > -1:
      continue
    counter[nd] += cnt
    visited[nd] =1
    dfs(nd,cnt+p[nd])
    


N,Q= map(int,input().split())
tree = {}
p = {}
counter = [0]*(N+1)
visited = [-1]*(N+1)
for i in range(1,N+1):
  tree[i] = []
  p[i] = 0
  
for i in range(N-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  
for i in range(Q):
  p_i,x = map(int,input().split())
  p[p_i] += x
  counter[p_i] += x
  
visited[1] = 1

dfs(1,p[1])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(node,cnt):
  for nd in tree[node]:
    if visited[nd] > -1:
      continue
    counter[nd] += cnt
    visited[nd] =1
    dfs(nd,cnt+p[nd])
    


N,Q= map(int,input().split())
tree = {}
p = {}
counter = [0]*(N+1)
visited = [-1]*(N+1)
for i in range(1,N+1):
  tree[i] = []
  p[i] = 0
  
for i in range(N-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  
for i in range(Q):
  p_i,x = map(int,input().split())
  p[p_i] += x
  
visited[1] = 1
for i in range(1,N+1):
  counter[i] += p[i]
dfs(1,p[1])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(20000)

def dfs(i,x):
    ans[i]+=x
    if dist[i]==bottom:
        return
    for n in tree[i]:
        if dist[n]>dist[i]:
            dfs(n,x)

from collections import deque

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)

#BFSで各ノードの深さを調べる
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

#カウンターをDFSで制御
ans=[0 for _ in range(N)]
bottom=max(dist)
for j in range(Q):
    p,x=map(int,input().split())
    dfs(p-1,x)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 17 19:21:21 2020

@author: Kanaru Sato
"""
import sys
sys.setrecursionlimit(10**9)

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

connected = [[] for i in range(n+1)]
connected[0].append(1)
for i in range(n-1):
    a,b = list(map(int,input().split()))
    connected[a].append(b)
    connected[b].append(a)

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

visited = [0 for i in range(n+1)]
point = [0 for i in range(n+1)]

def dfs(n,p):
    visited[n] = 1
    point[n] += p
    if connected[n]:
        for v in set(connected[n]):
            if visited[v] == 0:
                vpoint = p+operations[v]
                dfs(v,vpoint)

dfs(0,0)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 17 19:21:21 2020

@author: Kanaru Sato
"""
import sys
sys.setrecursionlimit(10**9)

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

connected = [[] for i in range(n+1)]
connected[0].append(1)
for i in range(n-1):
    a,b = list(map(int,input().split()))
    connected[a].append(b)
    connected[b].append(a)

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

visited = [0 for i in range(n+1)]
point = [0 for i in range(n+1)]

def dfs(n,p):
    visited[n] = 1
    point[n] += p
    if connected[n]:
        for v in connected[n]:
            if visited[v] == 0:
                vpoint = p+operations[v]
                dfs(v,vpoint)

dfs(0,0)

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

Submission status: Time Limit Exceeded

Solution code:
N,Q = (int(x) for x in input().split())
connection ={i:[] for i in range(1,N+1)}
#木の構造
for i in range(1,N):
    a,b = (int(x) for x in input().split())
    connection[a].append(b)
    connection[b].append(a)
#頂点を通過した時のポイント
point ={i:0 for i in range(1,N+1)}
for i in range(1,Q+1):
    p,x = (int(x) for x in input().split())
    point[p] +=x

#幅優先探索
start =1
stack=[start]
#prev =0
#point[0]=0
passed =[]
while stack:
    sarch =stack.pop()
    next = connection[sarch]
    for i in next:
        if i not in passed:
            point[i] +=point[sarch]
            
            stack.append(i)
            passed.append(sarch)
            #print(i,end=" ")
print(*(point.values()))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
a = [0]*(N) #1 index
b = [0]*(N) #1 index
p = [0]*(Q+1) #1 index
x = [0]*(Q+1) #1 index
counter = [0]*(N+1) #1 index
for i in range(1, N):
    a[i], b[i] = map(int, input().split())
for i in range(1, Q+1):
    p[i], x[i] = map(int, input().split())
    counter[p[i]] += x[i]

from collections import deque
graph = {i: deque() for i in range(1, N+1)}
for i in range(1, N):
    graph[a[i]].append(b[i])
    graph[b[i]].append(a[i])


def dfs(v):
    seen = [0]*(N+1)
    stack = []
    seen[v] = 1
    stack.append(v)
    while stack:
        s = stack[-1]
        if not graph[s]:
            stack.pop()
            continue
        g = graph[s].popleft()
        if seen[g]:
            continue
        seen[g] = 1
        stack.append(g)
        counter[g] += counter[s]

dfs(v=1)
print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
N,Q=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for _ in range(N-1):
	u,v=map(int, sys.stdin.readline().split())
	al[u].append(v)
	al[v].append(u)

increment=[ 0 for _ in range(N+1) ]
for _ in range(Q):
    p,x=map(int, sys.stdin.readline().split())
    increment[p]+=x

socre=[ 0 for _ in range(N+1) ] #各頂点のカウンターの値を記録
visit=[ 0 for _ in range(N+1) ] #0なら未訪問、1なら訪問済み
point=0
def dfs(par,cur):
    visit[cur]=1
    global point
    point+=increment[cur]
    socre[cur]+=point       #各頂点のカウンターの値を記録
    old=point   #拡張点が子孫に遷移する前のカウンターの値を記録
    for to in al[cur]:
        if visit[to]==0:
            dfs(cur,to)
            point=old   #子孫に遷移し、増えたカウンターの値を自分の時の点数に戻す
dfs(-1,1)

for i in range(1,N+1):
    print socre[i],

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N,Q=map(int,input().split())
    M = N-1  # 頂点数，辺数
    ans=[0]*N
    # グラフ入力受取 (ここでは無向グラフを想定)
    G = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)
    
    for i in range(Q):
        p,x=map(int,input().split())
        p-=1
        ans[p]+=x

        
    
    seen = [False]*N
    
    
    def dfs(G, v):    
        seen[v] = True
    
        for next_v in G[v]:
            if seen[next_v]:
                continue
            ans[next_v]+=ans[v]
            dfs(G, next_v)
    
    
    # 頂点 0 をスタートとした探索
    dfs(G, 0)
    print(*ans)
    
    
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
ans = [0 for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
    root[b - 1].append(a - 1)
for _ in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x
    
def dfs(pos, before):
    for next_pos in root[pos]:
        if next_pos == before:
            continue
        ans[next_pos] += ans[pos]
        dfs(next_pos, pos)

dfs(0, -1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
ans = [0 for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
    root[b - 1].append(a - 1)
for _ in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x
    
def dfs(pos, before):
    check[pos] = True
    ans[pos] += ans[before]
    for next_pos in root[pos]:
        if check[next_pos]:
            continue
        dfs(next_pos, pos)

check = [False for _ in range(n)]
dfs(0, -1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
ans = [0 for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
    root[b - 1].append(a - 1)
for _ in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x
    
def dfs(pos, before):
    ans[pos] += ans[before]
    for next_pos in root[pos]:
        root[next_pos].remove(pos)
        dfs(next_pos, pos)

dfs(0, -1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
plus = [0 for _ in range(n)]
ans = [0 for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
    root[b - 1].append(a - 1)
for _ in range(q):
    p, x = map(int, input().split())
    plus[p - 1] += x
    
def dfs(pos, cost):
    check[pos] = True
    cost += plus[pos]
    ans[pos] = cost
    for next_pos in root[pos]:
        root[next_pos].remove(pos)
        dfs(next_pos, cost)

check = [False for _ in range(n)]
for i in range(n):
    if not check[i]:
        dfs(i, 0)

for i in ans[:-1]:
    print(i, end=" ")
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def dfs(fr, now, num):
    global graph, addsum, ans
    tmp = num + addsum[now]
    for a in graph[now]:
        if a == fr:
            continue
        dfs(now, a, tmp)
    ans[now] = tmp


def main():
    global graph, addsum, ans
    N, Q = map(int, readline().split())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, readline().split())
        a -= 1; b -= 1
        graph[a].append(b)
        graph[b].append(a)
    addsum = [0]*N
    for _ in range(Q):
        p, x = map(int, readline().split())
        p -= 1
        addsum[p] += x
    
    ans = [0]*N
    dfs(-1, 0, 0)

    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

visited = [False for _ in range(n)]
def dfs(v):
    visited[v] = True
    stack = deque([v])
    while len(stack) > 0:
        u = stack[-1]
        if len(to[u]) > 0:
            w = to[u].popleft()
            if visited[w]:
                continue
            score[w] += score[u]
            visited[w] = True
            stack.append(w)
        else:
            stack.pop()

dfs(0)
print(*score)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(202020)

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

visited = [False for _ in range(n)]
def dfs(v, p=-1):
    for u in to[v]:
        if visited[u]:
            continue
        visited[v] = True
        score[u] += score[v]
        dfs(u, p=v)

dfs(0)
print(*score)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
def dfs(p, v, num):
    global g, plus_list, ans
    tmp = num + plus_list[v]
    for x in g[v]:
        if x == p:
            continue
        dfs(v, x, tmp)
    ans[v] = tmp
    
def main():
    global g, plus_list, ans
    N, Q = map(int, input().split())
    g = [[] for i in range(N)] 
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    plus_list = [0] * N
    for i in range(Q):
        q, y = map(int, input().split())
        plus_list[q-1] += y

    ans = [0] * N
    
    dfs(-1, 0, 0)
    print(*ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(202020)

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

def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        score[u] += score[v]
        dfs(u, p=v)

dfs(0)
print(*score)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
N, Q = map(int, input().split())
g = [[] for i in range(N)] 
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

plus_list = [0] * N
for i in range(Q):
    q, y = map(int, input().split())
    plus_list[q-1] += y

ans = [0] * N
def dfs(v, p):
    ans[v] = plus_list[v] + ans[p]
    for i in range(len(g[v])):
        x = g[v][i]
        if x != p:
            dfs(x, v)

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

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
N, Q = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
d = [0]*N
ok = [True]*N
cnt = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x
q = Queue()
q.put(0)
while not q.empty():
    p = q.get()
    d[p] += cnt[p]
    ok[p] = False
    for np in E[p]:
        if ok[np]:
            cnt[np] += cnt[p]
            q.put(np)

print(*d)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
v = [[] for _ in range(n)]
for _ in range(n - 1):
    ai, bi = map(int, input().split())
    ai -= 1; bi -= 1
    v[ai].append(bi)
    v[bi].append(ai)
c = [0] * n
for _ in range(q):
    pi, xi = map(int, input().split())
    c[pi - 1] += xi

def dfs(i, cv=0, parent=-1):
    cv += c[i]
    c[i] = cv
    for j in v[i]:
        if j == parent:
            continue
        dfs(j, cv, i)

dfs(0)
print(*c)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n, q = MI()
    e = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = MI1()
        e[a].append(b)
        e[b].append(a)

    point = [0]*n
    for _ in range(q):
        p, x = MI()
        p -= 1
        point[p] += x

    # print(point)

    def dfs(v, v_pre=-1, pp=0):
        # ans = pp + point[v]
        # print(v)
        point[v] += pp
        for nv in e[v]:
            if nv == v_pre: continue
            dfs(nv, v, point[v])

    dfs(0)
    printlist(point, ' ')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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

result=[0]*(n+1)
def dfs(node,edge,par):
    result[node] = result[par] + point[node]
    for next_node in edge[node]:
        if next_node == par:
            continue
        dfs(next_node,edge,node)

dfs(1,edge,0)
print(*result[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q = map(int,input().split())
adjacent = [[] for i in range(N)]
counter = dict.fromkeys(list(range(N)),0)
for i in range(N-1):
    a,b = map(int,input().split())
    adjacent[a-1].append(b-1)
    adjacent[b-1].append(a-1)
for j in range(Q):
    p,q = map(int,input().split())
    counter[p-1] += q
start = 0
frontier = deque([start])
visited = [start]
while len(frontier) > 0:
    x = frontier.pop()
    for y in adjacent[x]:
        if y not in visited:
            frontier.append(y)
            counter[y] += counter[x]
            visited.append(y)
value = [counter[i] for i in range(N)]
print(*value)

Submission status: Time Limit Exceeded

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

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

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


def dfs(curr, pare):
    for chi in g[curr]:
        if chi == pare: continue
        pl[chi] += pl[curr]
        dfs(chi, curr)

def main():
    dfs(0,-1)
    print(*pl)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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


def dfs(curr, pare):
    for chi in g[curr]:
        if chi == pare: continue
        pl[chi] += pl[curr]
        dfs(chi, curr)

def main():
    dfs(0,-1)
    print(*pl)

if __name__ == "__main__":
    main()