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(10000000)
N, Q = map(int, input().split())
cnt = [0 for i in range(N)]
val = [0 for i in range(N)]
t = [[] for i in range(N)]
seen = [False for i in range(N)]

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

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

points = 0
#dfsでいけなくなったらそのノードの点を引く
def dfs(u):
    global points
    points += val[u]
    cnt[u] = points
    for v in t[u]:
        if seen[v]:
            continue
        seen[v] = 1
        dfs(v)
    points -= val[u]

seen[0] = 1
dfs(0)
for i in range(N):
    print(cnt[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
n, q = map(int, input().split())
#隣接リスト
G = defaultdict(lambda:[])
#################################
for _ in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
    
#################################

#深さ優先探索でトポロジカル順序を決める
#右奥から調べていく
parent = [0]*n #p[i]:頂点iの親
order = [] #トポロジカル順序
def dfs():
    parent[0] = -1
    stack = []
    u = 0
    stack.append(u)
    while stack:
        x = stack.pop()
        order.append(x)
        for v in G[x]:
            if v == parent[x]:
                continue
            parent[v] = x
            stack.append(v)

dfs()
################################
point = [0]*n
def f(p, x):
    p -=1
    ind = order.index(p)
    order1 = order[ind:]
    order2 = order[:ind]
    order2.append(-1)
    for i in order1:
        if i == p:
            point[i] += x
        else:
            if parent[i] not in order2:
                point[i] += x
            else:
                break
    
for i in range(q):
    p, x = map(int, input().split())
    f(p, x)

print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000) #上限上げないと引っかかる
n,q = map(int, sys.stdin.readline().rstrip().split())
sco = [0]*(n+1)
G =[[] for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int, sys.stdin.readline().rstrip().split())
    G[a].append(b)
    G[b].append(a)

for j in range(q):
    p,x = map(int, sys.stdin.readline().rstrip().split())
    sco[p]+=x


#本体
seen = [False for _ in range(n+1)]
def dfs(G,V,score):
    global sco
    sco[V] +=score

    seen[V] = True
    for next_V in G[V]:
        if (seen[next_V]):
            continue
        dfs(G, next_V,sco[V])

#入力受け取り
#例
dfs(G,1,0)
print(*sco[1:])
#単にdfs(G,0)だと、木構造でないとき(頂点1つでない時)不正解

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000) #上限上げないと引っかかる




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

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


#本体
seen = [False for _ in range(n+1)]
def dfs(G,V,score):
    global sco
    sco[V] +=score

    seen[V] = True
    for next_V in G[V]:
        if (seen[next_V]):
            continue
        dfs(G, next_V,sco[V])

#入力受け取り
#例
dfs(G,1,0)
print(*sco[1:])
#単にdfs(G,0)だと、木構造でないとき(頂点1つでない時)不正解

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

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

connect_dic = defaultdict(list)

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

query_weight = defaultdict(int)
for _ in range(Q):
    q, x = map(int, input().split())
    query_weight[q] += x

used = set()
dq = deque([1])
used.add(1)
ans = [0] * (N + 1)

while dq:
    node = dq.popleft()
    can = connect_dic[node]

    used.add(node)
    ans[node] += query_weight[node]

    for c in can:
        if c not in used:
            ans[c] += ans[node]
            dq.append(c)


ans = [str(w) for w in ans[1:]]
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,q = map(int,input().split())
g = [[] for i in range(n)]
c = [0]*n
reach = [False]*n
for i in range(n-1):
    a,b = map(lambda x: int(x)-1,input().split())
    g[a].append(b)
    g[b].append(a)

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

def dfs(v):
    reach[v] = True
    for i in g[v]:
        if not reach[i]:
            c[i] += c[v]
            dfs(i)

reach[0] = True
dfs(0)
print(*c)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,q = map(int,input().split())
g = [[] for i in range(n)]
c = [0]*n
reach = [False]*n
for i in range(n-1):
    a,b = map(lambda x: int(x)-1,input().split())
    g[a].append(b)
    g[b].append(a)

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

def dfs(v):
    reach[v] = True
    for i in g[v]:
        if not reach[i]:
            c[i] += c[v]
            dfs(i)

reach[0] = True
dfs(0)
print(*c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
connected = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append(b)
    connected[b-1].append(a)
counter = [0] * N
for _ in range(Q):
    p,x = (int(y) for y in input().split())
    counter[p-1] += x
ans = counter
q = deque([(1,0)])
searched = [0] * N
while q:
    a,p = q.popleft()
    if searched[a-1] == 0:
        if p != 0:
            ans[a-1] += ans[p-1]
        searched[a-1] = 1
        for child in connected[a-1]:
            q.append((child,a))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
#import numpy as np #消すの忘れてた
N,Q = (int(x) for x in input().split())
aa=0  
bb=0
a=[0] 
b=[0]
a_set =set()
#ki_kouzou =np.zeros((N+1,1),dtype=np.int32)
ki_kouzou_dic ={i:set() for i in range(1,N+1)}

#木の構造を入力
for i in range(1,N): #直接つながっているところ。
    aa,bb = (int(x) for x in input().split())
    if bb in a_set: #親子判定 頂点3⇒頂点2もありうる
        #np.append(ki_kouzou[bb,:],aa,axis=1)
        a_set.add(aa)
        ki_kouzou_dic[bb].add(aa)
    else:
        #np.append(ki_kouzou[aa,:],bb,axis=1)
        #ki_kouzou[aa].append(bb)
        ki_kouzou_dic[aa].add(bb)
        a_set.add(bb)
    a.append(aa)     
    b.append(bb)


#間接的に繋がっているところ
kansetu ={i:set() for i in range(1,N+1)}
for ki_key in range(1,N+1) :
    for v_v in ki_kouzou_dic[ki_key]:
        if v_v in ki_kouzou_dic.keys():
            kansetu[ki_key] = kansetu[ki_key] | ki_kouzou_dic[v_v] 

for i in range(1,N+1):
    ki_kouzou_dic[i] =ki_kouzou_dic[i] | kansetu[i] #直接 ＋ 間接
    ki_kouzou_dic[i].add(i) #各頂点自身はは必ずポイント加算あり


# ポイント入力-計算
point={i:0 for i in range(1,N+1)}
pp=0 ; xx=0
for _ in range(Q):
    pp,xx = (int(x) for x in input().split())
    for i in ki_kouzou_dic[pp]:
        point[i] += xx 

print(*point.values())

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import numpy as np 
N,Q = (int(x) for x in input().split())
aa=0  
bb=0
a=[0] 
b=[0]
a_set =set()
ki_kouzou =np.zeros((N+1,1),dtype=np.int32)
ki_kouzou_dic ={i:set() for i in range(1,N+1)}

#木の構造を入力
for i in range(1,N): #直接つながっているところ。
    aa,bb = (int(x) for x in input().split())
    if bb in a_set: #親子判定 頂点3⇒頂点2もありうる
        #np.append(ki_kouzou[bb,:],aa,axis=1)
        a_set.add(aa)
        ki_kouzou_dic[bb].add(aa)
    else:
        #np.append(ki_kouzou[aa,:],bb,axis=1)
        #ki_kouzou[aa].append(bb)
        ki_kouzou_dic[aa].add(bb)
        a_set.add(bb)
    a.append(aa)     
    b.append(bb)


#間接的に繋がっているところ
kansetu ={i:set() for i in range(1,N+1)}
for ki_key in range(1,N+1) :
    for v_v in ki_kouzou_dic[ki_key]:
        if v_v in ki_kouzou_dic.keys():
            kansetu[ki_key] = kansetu[ki_key] | ki_kouzou_dic[v_v] 

for i in range(1,N+1):
    ki_kouzou_dic[i] =ki_kouzou_dic[i] | kansetu[i] #直接 ＋ 間接
    ki_kouzou_dic[i].add(i) #各頂点自身はは必ずポイント加算あり


# ポイント入力-計算
point={i:0 for i in range(1,N+1)}
pp=0 ; xx=0
for _ in range(Q):
    pp,xx = (int(x) for x in input().split())
    for i in ki_kouzou_dic[pp]:
        point[i] += xx 

print(*point.values())

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
pairs=list(tuple(map(lambda x:int(x)-1,input().split())) for _ in range(n-1))
point=list(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(q))

node=[[] for _ in range(n)]
parent=[None for _ in range(n)]
parent[0]=0
res=[0 for _ in range(n)]

for p in pairs:
  node[p[0]].append(p[1])
  node[p[1]].append(p[0])
  
for s in point:
  res[s[0]]+=(s[1]+1)
    
for i in range(n):
  for c in node[i]:
    if parent[c]==None:
      parent[c]=i
      res[c]+=res[i]
      
print(*res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def dfs(G, start):
    S = deque()
    S.append(start)
    while len(S) > 0:
        x, parent = S.pop()
        Counter[x] += Counter[parent]
        for g in G[x]:
            if g == parent:
                continue
            S.append((g, x))


N, Q = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N - 1)]
PX = [tuple(map(int, input().split())) for _ in range(Q)]
G = [[] for _ in range(N + 1)]
for a, b in AB:
    G[a].append(b)
    G[b].append(a)

Counter = [0 for _ in range(N + 1)]

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

dfs(G, (1, 0))
Counter = [str(a) for a in Counter]
print(" ".join(Counter[1:]))

Submission status: Time Limit Exceeded

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


def DFS(num,point):
    D[num]=point+Q[num]
    color[num]="gray"
    for i in M[num]:
        if color[i]=="white":
            DFS(i,D[num])
    color[num]="black"


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

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

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

color=["white" for _ in range(n+1)]
D=[0]*(n+1)

DFS(1,0)
print(*D[1:])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

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

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)

Submission status: Time Limit Exceeded

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


def f(x):
    if cnt[x]!=-1:return 
    ret=add[x]
    fd=0
    for to in edges[x]:
        if cnt[to]!=-1:ret+=cnt[to];fd=to;break
    cnt[x]=ret
    for to in edges[x]:
        if to!=fd:f(to)
    
    
f(0)
print(' '.join(str(c) for c in cnt))

Submission status: Time Limit Exceeded

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


def f(x):
    if cnt[x]!=-1:return 
    ret=add[x]
    fd=0
    for to in edges[x]:
        if cnt[to]!=-1:ret+=cnt[to];fd=to;break
    cnt[x]=ret
    for to in edges[x]:
        if to!=fd:f(to)
    
    
f(0)
print(*cnt,sep=" ")

Submission status: Time Limit Exceeded

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


def f(x):
    if cnt[x]!=-1:return 
    ret=add[x]
    fd=0
    for to in edges[x]:
        if cnt[to]!=-1:ret+=cnt[to];fd=to;break
    cnt[x]=ret
    for to in edges[x]:
        if to!=fd:f(to)
    
    
f(0)
print(*cnt,sep=" ")

Submission status: Time Limit Exceeded

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


def f(x):
    if cnt[x]!=-1:return 
    ret=add[x]
    fd=0
    for to in edges[x]:
        if cnt[to]!=-1:ret+=cnt[to];fd=to;break
    cnt[x]=ret
    for to in edges[x]:
        if to!=fd:f(to)
    
    
f(0)
print(*cnt,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s=map(int,input().split());a-=1;s-=1
    edges[a].append(s)
    edges[s].append(a)
cnt=[-1]*n
add=[0]*n
for _ in range(q):
    a,s=map(int,input().split())
    add[a-1]+=s

def f(x):
    if cnt[x]!=-1:return cnt[x]
    ret=add[x]
    after=[]
    for to in edges[x]:
        if cnt[to]==-1:after.append(to)
        else:ret+=cnt[to]
    cnt[x]=ret
    for i in after:
        f(i)
    return 0
f(0)
print(*cnt,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

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

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)

Submission status: Time Limit Exceeded

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


def DFS(num,point):
    D[num]=point+Q[num]
    color[num]="gray"
    for i in M[num]:
        if color[i]=="white":
            DFS(i,D[num])
    color[num]="black"


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

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

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

color=["white" for _ in range(n+1)]
D=[0]*(n+1)

DFS(1,0)
print(*D[1:])

Submission status: Time Limit Exceeded

Solution code:
# 木上の累積和

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


from collections import defaultdict

N, Q = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
cnt = [0] * N
for _ in ra(Q):
    q, x = read_ints()
    cnt[q - 1] += x

# dfsでcntに木に沿った累積和をsetしていく


def dfs(c, u, p):  # uは現在のノード、pは親のノード、cはuは含まない累積のスコア
    cnt[u] += c
    for nv in tree[u]:
        if nv == p:
            continue
        dfs(cnt[u], nv, u)


dfs(0, 0, -1)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
rela = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rela[a].append(b)
    rela[b].append(a)
    cnt = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p - 1] += x
from collections import deque
que = deque([[-1, 0]])
while que:
    par, cur = que.popleft()
    for new in rela[cur]: 
        if new == par:
            continue
        cnt[new] += cnt[cur]
        que.append([cur, new])
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
rela = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rela[a].append(b)
    rela[b].append(a)
    cnt = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    cnt[p] += x
from collections import deque
que = deque([[-1, 0]])
while que:
    par, cur = que.popleft()
    for new in rela[cur]: 
        if new == par:
            continue
        cnt[new] += cnt[cur]
        que.append([cur, new])
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
rela = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rela[a].append(b)
    rela[b].append(a)
    cnt = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p - 1] += x
from collections import deque
que = deque([[-1, 0]])
while que:
    par, cur = que.popleft()
    for new in rela[cur]: 
        if new == par:
            continue
        cnt[new] += cnt[cur]
        que.append([cur, new])
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n , q = map(int,input().split())
lot = [[] for i in range(n)]
ans = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    lot[a-1].append(b-1)
    lot[b-1].append(a-1)
tyu = [0]*n
for i in range(q):
    p , x = map(int,input().split())
    tyu[p-1] += x

taiki = deque()
taiki.append(0)
owari = []
while  taiki:
    s = taiki.pop()
    for i in lot[s]:
        if owari.count(i) == 0:
            tyu[i] += tyu[s]
            taiki.append(i)
    owari.append(s)
for i in tyu:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

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

Submission status: Time Limit Exceeded

Solution code:
# tempt
N,Q=map(int,input().split())
Graph=[[] for i in range(N)]

num=[0 for i in range(N)]



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


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


def dfs(a):
    tmp=Graph[a]
    while tmp:
        g=tmp.pop()
        print(g)
        num[g]+=num[a]
        tmp.append(g)

dfs(0)
print(Graph)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
rela = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rela[a].append(b)
    rela[b].append(a)
hoge = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    hoge[p] += x
from collections import deque
que = deque([0])
while que:
    cur = que.pop()
    for new in rela[cur]:
        hoge[new] += hoge[cur]
        que.append(new)
print(*hoge)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
p = {}
e = {}
c = {}
r = {}
def trv(start, v):
    if start in p:
        v = v + p[start]
    r[start] = v
    if start in e:
        el = e[start]
        for k in el:
            trv(k, v)
            
q = []
e[1] = []
c[1] = 1
for i in range(1,N):
    tmpa, tmpb = map(int, input().split())
    if tmpa in e:
        e[tmpa].append(tmpb)
        c[tmpb] = 1
    elif tmpb in e:
        e[tmpb].append(tmpa)
        c[tmpa] = 1
    elif tmpa in c:
        if tmpa in e:
            e[tmpa].append(tmpb)
        else:
            e[tmpa] = [tmpb]
        c[tmpb] = 1
    elif tmpb in c:
        if tmpb in e:
            e[tmpb].append(tmpa)
        else:
            e[tmpb] = [tmpa]
        c[tmpa] = 1
    else:
        q.append([tmpa, tmpb])

while len(q) > 0:
    qtmp = []
    for [a,b] in q:
        if a in e:
            e[a].append(b)
            c[b] = 1
        elif b in e:
            e[b].append(a)
            c[a] = 1
        elif a in c:
            if a in e:
                e[a].append(b)
            else:
                e[a] = [b]
            c[b] = 1
        elif b in c:
            if b in e:
                e[b].append(a)
            else:
                e[b] = [a]
            c[a] = 1
        else:
            qtmp.append([a,b])
    q = qtmp

for i in range(1,Q+1):
    tmpp, tmpx = map(int, input().split())
    if tmpp in p:
        p[tmpp] = p[tmpp] + tmpx
    else:
        p[tmpp] = tmpx
for i in range(1,N+1):
    r[i] = 0
    
trv(1, 0)
res = []
for i in range(1,N+1):
    res.append(r[i])
print(' '.join(map(str, res)))

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

cost=[0]*200010
G=[[] for _ in range(200010)]
visited=[False]*200010
visited[0]=True

def dfs(s):
  global cost
  global G
  global visited
  for e in G[s]:
    if visited[e]==False:
      cost[e]+=cost[s]
      visited[e]=True
      dfs(e)
      visited[e]=False

def main():
  global cost
  global G
  global visited
  n,q=LI()
  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

  for i in range(q):
    p,x=LI()
    p-=1
    cost[p]+=x
  dfs(0)

  return ' '.join([str(x) for x in cost[:n]])

# main()
print(main())

Submission status: Time Limit Exceeded

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

n, q = map(int,input().split())
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)
points = [0]*(n+1)
for _ in range(q):
    p, x = map(int,input().split())
    points[p] += x
# print(g)
# print(points)
def dfs(e,preve = -1):
    for nexte in g[e]:
        # print(nexte)
        if nexte == preve:
            continue
        points[nexte] = points[nexte] + points[e]
        dfs(nexte,e)
dfs(1)
print(*points[1:])

Submission status: Time Limit Exceeded

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

n, q = map(int,input().split())
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)
points = [0]*(n+1)
for _ in range(q):
    p, x = map(int,input().split())
    points[p] += x
# print(g)
# print(points)
def dfs(e,preve):
    for nexte in g[e]:
        # print(nexte)
        if nexte == preve:
            continue
        
        points[nexte] = points[nexte] + points[e]
        dfs(nexte,e)
dfs(1,-1)
print(*points[1:])

Submission status: Time Limit Exceeded

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

n, q = map(int,input().split())
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)
points = [0]*(n+1)
for _ in range(q):
    p, x = map(int,input().split())
    points[p] += x
# print(g)
# print(points)
def dfs(e,preve):
    for nexte in g[e]:
        # print(nexte)
        if nexte != preve:
            points[nexte] = points[nexte] + points[e]
            dfs(nexte,e)
dfs(1,-1)
print(*points[1:])

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())
graph=[[]for _ in range(N)]
point=[0]*N
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for _ in range(Q):
    a,b=map(int,input().split())
    a=a-1
    point[a]=point[a]+b

def dfs(now,prev=-1):
    for i in graph[now]:
        if i==prev:
            continue
        point[i]=point[i]+point[now]
        dfs(i,now)
dfs(0)
print(*point)

Submission status: Time Limit Exceeded

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

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if seen[i]:
    continue
  dfs(i, ook[i])
    
print(" ".join(map(str,r)))

Submission status: Time Limit Exceeded

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

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if not seen[i]:
    dfs(i, ook[i])
    
print(" ".join(map(str,r)))

Submission status: Time Limit Exceeded

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

from collections import defaultdict
dic = defaultdict(int)
for _ in range(q):
   p,x = map(int,input().split())
   dic[p-1] += x

ans = [0 for i in range(n)]
ans[0] = dic[0]

used = [0 for i in range(n)]
used[0] = 1
quu = [0]
while quu:
   k = quu.pop()
   for l in m[k]:
      if used[l] == 0:
         used[l] = 1
         quu.append(l)
         ans[l] = ans[k] + dic[l]

for i in ans:
   print(i)

Submission status: Time Limit Exceeded

Solution code:
import queue
n,Q = map(int,input().split())
ki = [[] for i in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
q = queue.Queue()
cnt = [0] * n
for _ in range(Q):
    p,x = map(int,input().split())
    cnt[p-1] += x
vis = [-1] * n
q.put(0)
vis[0] = 1
while True:
    if q.empty():
        break
    a = q.get()
    a_ = ki[a]
    for i in a_:
        if vis[i] == -1:
            q.put(i)
            vis[i] = 1
            cnt[i] += cnt[a]
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys #追加
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())

from collections import defaultdict
dic = defaultdict(list)


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


dic2 = defaultdict(int)

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

ansl = [0 for i in range(n)]
used = [-1 for i in range(n)]
used[0] = 1
que = [0]
while que:
    pos = que.pop()
    used[pos] = 1
    for p in dic[pos]:
        if used[p] == -1:
            ansl[p] = ansl[pos] + dic2[pos]
            que.append(p)


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

Submission status: Time Limit Exceeded

Solution code:
import sys #追加
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())

from collections import defaultdict
dic = defaultdict(list)


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


dic2 = defaultdict(int)

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

ansl = [0 for i in range(n)]
used = [-1 for i in range(n)]
used[0] = 1
que = [0]
while que:
    pos = que.pop()
    for p in dic[pos]:
        if used[p] == -1:
            ansl[p] = ansl[pos] + dic2[pos]
            used[p] = 1
            que.append(p)


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