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(10**7)

N, Q = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

# 木構造をリストで表現する
G = [[] for _ in range(N+1)]

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

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for p, x in PX:
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point
    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

Submission status: Time Limit Exceeded

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

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

# 木構造をリストで表現する
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

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

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

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for p, x in PX:
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

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

AB = [[int(x) for x in input().split()] for _ in range(N-1)]

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

# 各操作で与えられる値を、各頂点ごとに集計しておく
PX = [[int(x) for x in input().split()] for _ in range(Q)]

P = [0] * (N+1)
for p, x in PX:
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

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 i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

# 各操作で与えられる値を、各頂点ごとに集計しておく
PX = [[int(x) for x in input().split()] for _ in range(Q)]

P = [0] * (N+1)
for p, x in PX:
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

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 i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

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 i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    P[p] += x

# 各頂点のカウンター
Count = [0] * (N+1)


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    Count[v] = point + P[v]

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, Count[v])


dfs(1, 0, 0)

res = ' '.join(map(str, Count[1:]))
print(res)

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 i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    P[p] += x

# 各頂点のカウンター
Count = [0] * (N+1)


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとし、
    new_point = point + P[v]
    Count[v] = new_point

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, new_point)


dfs(1, 0, 0)

res = " ".join(map(str, Count[1:]))

print(res)

Submission status: Time Limit Exceeded

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

seen=[]
#seen=dict()
path=[]

def dfs(g, v,add):
    xx[v]+=add
#    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v,xx[v])
#    path.append(v)

    return

icase=-1
if icase==-1:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    ab=[[int(x) for x in input().split()] for  _ in range(n-1)]
    px=[[int(x) for x in input().split()] for  _ in range(q)]

    g = [set() for _ in range(n)]
    for ai,bi in ab:
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)

    xx=[0]*n
    for pi,xi in px:
        xx[pi-1]=xx[pi-1]+xi
if icase==0:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
#        g[ai-1].append(bi-1)
#        g[bi-1].append(ai-1)
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:100 110 111 110

#c=[0]*n

seen=[False]*n
#for i in range(n):
#    seen[i]=False
dfs(g,0,0)

#print(path)

'''
seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()
'''

ans=" ".join(map(str,xx[0:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

seen=[]
#seen=dict()
path=[]

def dfs(g, v,add):
    xx[v]+=add
#    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v,xx[v])
#    path.append(v)

    return

icase=0
if icase==0:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
#        g[ai-1].append(bi-1)
#        g[bi-1].append(ai-1)
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:100 110 111 110

#c=[0]*n

seen=[False]*n
#for i in range(n):
#    seen[i]=False
dfs(g,0,0)

#print(path)

'''
seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()
'''

ans=" ".join(map(str,xx[0:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

graph = defaultdict(list)

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

dic = defaultdict(int)

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

ans = [0]*N

checked = [0]*N
checked[0] = 1

q = deque([])
q.append(0)

while q:
	n = q.popleft()
	ans[n] += dic[n]
	for node in graph[n]:
		if checked[node]:
			continue
		ans[node] += ans[n]
		checked[node] = 1
		q.append(node)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

queue = deque()

for _ in range(1, N):
    queue.append(tuple(map(int, input().split(' '))))

tree = {
    1: set()
}

while len(queue) > 0:
    a, b = queue.popleft()
    if a in tree:
        tree[a].add(b)
        tree[b] = set()
    elif b in tree:
        tree[b].add(a)
        tree[a] = set()
    else:
        queue.append((a, b))

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

stack = deque([1])

while len(stack) > 0:
    node = stack.popleft()
    for child in tree[node]:
        stack.append(child)
        results[child] += results[node]

print(' '.join([str(result) for result in results[1:]]))

Submission status: Time Limit Exceeded

Solution code:
from collections import (
    deque,
    Counter,
)

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

queue = deque()

for _ in range(1, N):
    queue.append(tuple(map(int, input().split(' '))))

tree = {
    1: set()
}

while len(queue) > 0:
    a, b = queue.popleft()
    if a in tree:
        tree[a].add(b)
        tree[b] = set()
    elif b in tree:
        tree[b].add(a)
        tree[a] = set()
    else:
        queue.append((a, b))

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

stack = deque([1])

results = [0] * (N + 1)

while len(stack) > 0:
    node = stack.popleft()
    results[node] += queries[node]
    for child in tree[node]:
        stack.append(child)
        results[child] += results[node]

print(' '.join([str(result) for result in results[1:]]))

Submission status: Time Limit Exceeded

Solution code:
from collections import (
    deque,
    Counter,
)

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

queue = deque()

for _ in range(1, N):
    queue.append(tuple(map(int, input().split(' '))))

tree = {
    1: set()
}

while len(queue) > 0:
    a, b = queue.popleft()
    if a in tree:
        tree[a].add(b)
        tree[b] = set()
    elif b in tree:
        tree[b].add(a)
        tree[a] = set()
    else:
        queue.append((a, b))

counter = Counter()

for _ in range(Q):
    p, x = map(int, input().split(' '))
    stack = deque()
    stack.appendleft(p)
    while len(stack) > 0:
        node = stack.popleft()
        for child in tree[node]:
            stack.append(child)
        counter[node] += x

print(' '.join([str(counter[node]) for node in range(1, N + 1)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)    
from collections import deque

seen=[]
#seen=dict()
path=[]

def dfs(g, v):
    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v)
    path.append(v)

    return

icase=0
if icase==0:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
#        g[ai-1].append(bi-1)
#        g[bi-1].append(ai-1)
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
    
c=[0]*n

seen=[False]*n
#for i in range(n):
#    seen[i]=False
dfs(g,0)

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)    
from collections import deque

seen=[]
#seen=dict()
path=[]

def dfs(g, v):
    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v)
    path.append(v)

    return

icase=0
if icase==0:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
#        g[ai-1].append(bi-1)
#        g[bi-1].append(ai-1)
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
    
c=[0]*n

seen=[False]*n
#for i in range(n):
#    seen[i]=False
dfs(g,0)

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)    
from collections import deque

seen=[]
#seen=dict()
path=[]

def dfs(g, v):
    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v)
    path.append(v)

    return

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
    
c=[0]*n

seen=[False]*n
#for i in range(n):
#    seen[i]=False
dfs(g,0)

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)    
from collections import deque

#seen=[]
seen=dict()
path=[]

def dfs(g, v):
    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v)
    path.append(v)

    return

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
    
c=[0]*n

#seen=[False]*n
for i in range(n):
    seen[i]=False
dfs(g,0)

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)    
from collections import deque

seen=[]
path=[]

def dfs(g, v):
    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v)
    path.append(v)

    return

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
    
c=[0]*n

seen=[False]*n
dfs(g,0)

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)    
from collections import deque

seen=[]
path=[]

def dfs(g, v):
    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v)
    path.append(v)

    return

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
    
c=[0]*n

seen=[False]*n
dfs(g,0)

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10000)    
from collections import deque

seen=[]
first_order =[]
last_order = []
path=[]

def dfs(g, v, first_ptr, last_ptr,xi):
    first_ptr=first_ptr+1
    last_ptr=first_ptr
    first_order[v] = first_ptr
    path.append(v)
    seen[v]=True
#    c[v]+=xi
#    print(v,c,g[v])          
    for next_v in g[v]:
        if seen[next_v]:
            continue
        first_ptr, last_ptr=dfs(g, next_v, first_ptr, last_ptr,xi)
    last_ptr=last_ptr+1
    first_ptr=last_ptr
    last_order[v] = last_ptr
    path.append(v)

    return first_ptr, last_ptr

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
    p=[0]*q
    x=[0]*q
    for i in range(q):
        pi,xi=map(int,input().split())
        p[i]=pi-1
        x[i]=xi
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
#ans:100 110 111 110
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10
#ans:100 110 111 110

xx=[0]*n
for i in range(q):
    xx[p[i]]=xx[p[i]]+x[i]
    
c=[0]*n

#for i in range(q):
#    seen=[False]*n
#    first_ptr=0
#    last_ptr=0
#    first_order =[-1]*n
#    last_order = [-1]*n
#    first_ptr, last_ptr=dfs(g,p[i],first_ptr, last_ptr,x[i])

seen=[False]*n
first_ptr=0
last_ptr=0
first_order =[-1]*n
last_order = [-1]*n
first_ptr, last_ptr=dfs(g,0,first_ptr, last_ptr,x[0])

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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)]

adlist=[]
finish=set()
def dfs():
    while deq:
        now=deq.pop()
       # print(now)
        finish.add(now)
        for i in range(len(adlist[now-1])):
            #print(adlist[now-1][i],now)
            if adlist[now-1][i] not in finish:
                point[adlist[now-1][i]-1]+=point[now-1]
                deq.append(adlist[now-1][i])
point=[0]*n
for h in range(n):    
    adlist.append([])
for j in range(n-1):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
for i in range(q):
    point[px[i][0]-1]+=px[i][1]
#print(point)
deq=deque()
deq.append(1)
#print(deq)
dfs()
for i in range(n):
    print(point[i],end=" ")

"""
finish=set()
finish.add(1)
#print(adlist)
dfs(1,finish)#引数がけすノード
print(ans)"""

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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)]

adlist=[]
finish=set()
def dfs():
    while deq:
        now=deq.pop()
       # print(now)
        finish.add(now)
        for i in range(len(adlist[now-1])):
            #print(adlist[now-1][i],now)
            if adlist[now-1][i] not in finish:
                point[adlist[now-1][i]-1]+=point[now-1]
                deq.append(adlist[now-1][i])
point=[0]*n
for h in range(n):    
    adlist.append([])
for j in range(n-1):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
for i in range(q):
    point[px[i][0]-1]+=px[i][1]
#print(point)
deq=deque()
deq.append(1)
#print(deq)
dfs()
for i in range(n):
    print(point[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,q = map(int,input().split())
graph = [[] for _ in range(n)]
point = [0]*n
for i in range(n-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for _ in range(q):
    a,b = map(int,input().split())
    a = a -1
    point[a]+=b
def dfs(now, prev = -1):
    for next in graph[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next, now)
dfs(0)
print(*point)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

que = deque()
que.append(0)
kaisos = [None for _ in range(N)]
kaisos[0] = 0
kaiso_depth = 1
while len(que) > 0:
    node_i = que.popleft()
    neighbors = Nodes[node_i]
    v = kaisos[node_i]
    for neighbor in neighbors:
        if kaisos[neighbor] is None:
            kaisos[neighbor] = v + 1
            kaiso_depth = v + 2
            que.append(neighbor)

# print("")
# print("kaiso:", kaisos)
# print("depth:", kaiso_depth)


ans = [0 for _ in range(N)]
imosu = [0 for _ in range(kaiso_depth)]
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
    kaiso = kaisos[p]
    if kaiso < kaiso_depth-1:
        imosu[kaiso+1] += x

#print("imosu:", imosu)

kaiso_values = [0 for _ in range(kaiso_depth)]
for i in range(1, kaiso_depth):
    kaiso_values[i] = kaiso_values[i-1] + imosu[i]

#print(kaiso_values)

# 解答
for i in range(N):
    kaiso = kaisos[i]
    ans[i] += kaiso_values[kaiso]
    print(ans[i], end=' ')

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

flg = [-1 for i in range(n)]
flg[0] = 1

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, weight): #weightは自分より上のノードの重さの和
    flg[start] = 1
    ans[start] = weight + omosa[start]
    for child in arr[start]:
        if flg[child] == -1:
            dfs(child, ans[start])
 
dfs(0,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.readline #文字列入力のときは注意

n,q = [int(i) for i in readline().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 = [int(i) for i in readline().split()]
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(q):
    tmpp,tmpx = [int(i) for i in readline().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)
readline = sys.stdin.readline #文字列入力のときは注意
n,q = [int(i) for i in readline().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)