Problem:


Score : 400 points

Problem Statement

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

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

Now, the following Q operations will be performed:

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

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

Constraints

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

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

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

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

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

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

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

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20



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


Sample output:
100 110 111 110

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

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

v = [[] for _i in range(n + 10)]

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

add = [0] * (n + 10)

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


def dfs(now, fa):
    add[now] += add[fa]
    for i in v[now]:
        if i == fa:
            continue
        dfs(i, now)


dfs(1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, Q = map(int, input().split())
edges = [[] for _ in range(n+1)]
count = [0]*(n+1)
used = []*(n+1)
q = deque()
q.append((1, 0))

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    count[p] += x

while(q):
    k = q.popleft()
    used.append(k[0])
    count[k[0]] += count[k[1]]
    for i in edges[k[0]]:
        if not i in used:
            q.append((i, k[0]))

print(*count[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
inf = [[] for _ in range(n+1)]
ab = [[x for x in map(int, input().split(' '))] for _ in range(n-1)]
for a,b in ab:
    inf[a].append(b)
    inf[b].append(a)
point = [0]*(n+1)
px = [[x for x in map(int, input().split(' '))] for _ in range(q)]
for p,x in px:
    point[p] += x
def add_p(num, oya):
    for k in inf[num]:
        if k != oya:
            point[k] += point[num]
            add_p(k, num)  
for i in inf[1]:
    point[i] += point[1]
    add_p(i,1)
point.pop(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
inf = [[] for _ in range(n+1)]
ab = [[x for x in map(int, input().split(' '))] for _ in range(n-1)]
for a,b in ab:
    inf[a].append(b)
    inf[b].append(a)
point = [0 for _ in range(n+1)]
px = [[x for x in map(int, input().split(' '))] for _ in range(q)]
for p,x in px:
    point[p] += x
def add_p(num, oya):
    for k in inf[num]:
        if k != oya:
            point[k] += point[num]
            add_p(k, num)  
for i in inf[1]:
    point[i] += point[1]
    add_p(i,1)
point.pop(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
inf = [[] for _ in range(n)]
ab = [[x for x in map(int, input().split(' '))] for _ in range(n-1)]
for a,b in ab:
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
point = [0 for _ in range(n)]
px = [[x for x in map(int, input().split(' '))] for _ in range(q)]
for p,x in px:
    point[p-1] += x
def add_p(num, oya):
    for k in inf[num]:
        if k != oya:
            point[k] += point[num]
            add_p(k, num)  
for i in inf[0]:
    point[i] += point[0]
    add_p(i,0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
     
inf = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split(' '))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
point = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split(' '))
    point[p-1] += x
def add_p(num, oya):
    for k in inf[num]:
        if k != oya:
            point[k] += point[num]
            add_p(k, num)  
for i in inf[0]:
    point[i] += point[0]
    add_p(i,0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
     
inf = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split(' '))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
point = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split(' '))
    point[p-1] += x
def add(num):
    for k in inf[num]:
        if k != num:
            point[k] += point[num]
            add(k)  
add(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
     
inf = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split(' '))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
point = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split(' '))
    point[p-1] += x
def add(num):
    for k in inf[num]:
        if k != num:
            inf[k].remove(num)
            point[k] += point[num]
            add(k)  
add(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
     
inf = [[] for _ in range(n)]
ab = [list(map(int, input().split(' '))) for i in range(n-1)]

for i in range(n-1):
    inf[ab[i][1]-1].append(ab[i][0]-1)
    inf[ab[i][0]-1].append(ab[i][1]-1)
point = [0 for _ in range(n)]
px = [list(map(int, input().split(' '))) for i in range(q)]
for i in range(q):
    point[px[i][0]-1] += px[i][1]
def add(num):
    if len(inf[num]) == 0:
        return 0
    for k in inf[num]:
        inf[k].remove(num)
        point[k] += point[num]
        add(k)
     
add(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
     
inf = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split(' '))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
point = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split(' '))
    point[p-1] += x
def add(num):
    if len(inf[num]) == 0:
        return 0
    for k in inf[num]:
        inf[k].remove(num)
        point[k] += point[num]
        add(k)
     
add(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = list(map(int, input().split(' ')))
inf = [[] for _ in range(n)]
p_list = [0 for _ in range(n)] 
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)   
for i in range(q):
    p, x = list(map(int, input().split(' ')))
    p_list[p-1] += x
visit = [0]*n
def add_p(num):
    visit[num] = 1
    for k in inf[num]:
        if visit[k] == 0:
            p_list[k] += p_list[num]
            add_p(k)
    return 0
add_p(0)
print(*p_list)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = list(map(int, input().split(' ')))
inf = [[] for _ in range(n)]
p_list = [0 for _ in range(n)]
     
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
     
for i in range(q):
    p, x = list(map(int, input().split(' ')))
    p_list[p-1] += x
visit = [0]*n
def add_p(num):
    """
    if all(visit[x] == 1 for x in inf[num]):
        return 0
    """
    visit[num] = 1
    for k in inf[num]:
        if visit[k] == 1:
            continue
        else:
            p_list[k] += p_list[num]
            add_p(k)
    return 0
add_p(0)
print(*p_list)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = list(map(int, input().split(' ')))
inf = [[] for _ in range(n)]
p_list = [0 for _ in range(n)]
     
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
     
for i in range(q):
    p, x = list(map(int, input().split(' ')))
    p_list[p-1] += x
     
def add_p(num):
    if len(inf[num]) == 0:
        return 0
    for k in inf[num]:
        inf[k] = [x for x in inf[k] if x != num]
        p_list[k] += p_list[num]
        add_p(k)
    return 0
     
add_p(0)
print(*p_list)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
inf = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split(' '))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
score = [0 for _ in range(n)]
visit = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split(' '))
    score[p-1] += x
def addp(num, parent):
    for i in inf[num]:
        if i != parent:
            if i != parent:
                score[i] += score[num]
                addp(i, num)
    return 0
for x in inf[0]:
    score[x] += score[0]
    addp(x, 0)
print(*score)

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

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

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

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

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Time Limit Exceeded

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

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

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

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

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

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Time Limit Exceeded

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

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

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x

def dfs(v,parent,add):
    for w in graph[v]:
        if w != parent:
             cnt[w-1] += add
             dfs(w,v,cnt[w-1])

for i in graph[1]:
    cnt[i-1] += cnt[0]
    dfs(i,1,cnt[i-1])

print(*cnt)

Submission status: Time Limit Exceeded

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

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

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x

def dfs(v,parent):
    for w in graph[v]:
        if w != parent:
             cnt[w-1] += cnt[v-1]
             dfs(w,v)

for i in graph[1]:
    cnt[i-1] += cnt[0]
    dfs(i,1)

print(*cnt)

Submission status: Time Limit Exceeded

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

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

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x

def dfs(v):
    for w in graph[v]:
        cnt[w-1] += cnt[v-1]
        graph[w].remove(v)
        if len(graph[w]) > 0:
            dfs(w)

dfs(1)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,q=map(int,input().split())
tree=[list(map(int,sys.stdin.readline().split())) for i in range(n-1)]
#f1は使ったのかどうかを表すフラッグ
#f2はそれまでに出てきたものを表すフラッグ
f1=[0]*(n-1)
f2=[0]*n
f2[0]=1

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

while f1!=[1]*(n-1):
    for i,t in enumerate(tree):
        if f1[i]==0:
            if f2[t[0]-1]==1:
                c[t[1]-1]+=c[t[0]-1]
                f1[i]=1
                f2[t[1]-1]=1
            elif f2[t[1]-1]==1:
                c[t[0]-1]+=c[t[1]-1]
                f1[i]=1
                f2[t[0]-1]=1
            else:
                pass

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################
n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    
stack = [0]
seen = dict()
seen[0] = 1
while stack:
    yy = stack.pop()
    for i in tree[yy]:
        if seen.get(i,-1) == -1:
            seen[i] = 1
            counter[i]+=counter[yy]
            stack.append(i)
            
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################


from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
def dfs(p,father=-1):
    for i in tree[p]:
        if i == father:
            continue
        counter[i]+=counter[p]
        dfs(i,p)

n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
dfs(0) 
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,q=map(int,input().split())
tree=[list(map(int,sys.stdin.readline().split())) for i in range(n-1)]
#f1は使ったのかどうかを表すフラッグ
#f2はそれまでに出てきたものを表すフラッグ
f1=[0]*(n-1)
f2=[1]

c=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x
#print(tree)
while f1!=[1]*(n-1):
    #print(c)
    for i,t in enumerate(tree):
        if f1[i]==0:
            if t[0] in f2:
                c[t[1]-1]+=c[t[0]-1]
                f1[i]=1
                f2.append(t[1])
            elif t[1] in f2:
                c[t[0]-1]+=c[t[1]-1]
                f1[i]=1
                f2.append(t[0])
            else:
                pass

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
tree=[list(map(int,input().split())) for i in range(n-1)]
#f1は使ったのかどうかを表すフラッグ
#f2はそれまでに出てきたものを表すフラッグ
f1=[0]*(n-1)
f2=[1]

c=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x
#print(tree)
while f1!=[1]*(n-1):
    #print(c)
    for i,t in enumerate(tree):
        if f1[i]==0:
            if t[0] in f2:
                c[t[1]-1]+=c[t[0]-1]
                f1[i]=1
                f2.append(t[1])
            elif t[1] in f2:
                c[t[0]-1]+=c[t[1]-1]
                f1[i]=1
                f2.append(t[0])
            else:
                pass

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC138 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
cnt = [0]*n
for _ in range(q):
    p,x = LI()
    cnt[p-1] += x
#オイラーツアー
def dfs(x,p):
    for i in graph[x]:
        if i != p:
            cnt[i] += cnt[x]
            dfs(i,x)
dfs(0,-1)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC138 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
#オイラーツアー
def dfs(x,p):
    lst.append(x)
    for i in graph[x]:
        if i != p:
            dfs(i,x)
    lst.append(p)
lst = []
dfs(0,-1)
lst.pop()
left,right = [-1]*n,[-1]*n
for i in range(2*n-1):
    if left[lst[i]] < 0:
        left[lst[i]] = i
for i in range(2*n-1)[::-1]:
    if right[lst[i]] < 0:
        right[lst[i]] = i
cnt = [0]*(2*n)
for _ in range(q):
    p,x = LI()
    cnt[left[p-1]] += x
    cnt[right[p-1]+1] -= x
cnt = list(accumulate(cnt))
ans = [cnt[left[i]] for i in range(n)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC138 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def dfs(x,p):
    lst.append(x)
    for i in graph[x]:
        if i != p:
            dfs(i,x)
    lst.append(p)
lst = []
dfs(0,0)
lst.pop()
inde = [[-1,-1] for _ in range(n)]
m = len(lst)
for i in range(m):
    if inde[lst[i]][0] < 0:
        inde[lst[i]][0] = i
for i in range(m)[::-1]:
    if inde[lst[i]][1] < 0:
        inde[lst[i]][1] = i
cnt = [0]*(m+1)
for _ in range(q):
    p,x = LI()
    cnt[inde[p-1][0]] += x
    cnt[inde[p-1][1]+1] -= x
cnt = list(accumulate(cnt))
ans = []
for i in range(n):
    ans.append(cnt[inde[i][0]])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#木の問題と書いてあるが、実際は木の構造がわからなくても解ける
#根の方から順に足していってあげればいい
#aiがbiの親であるとは限らないらしい
#これがある以上、木構造を作るしかない
#辞書で(他の人のコードを参照)親子関係を保持できる、初めて知った
#は？結局他人の使わないやんけ
from copy import deepcopy

n,q=map(int,input().split())
tree1=[list(map(int,input().split())) for i in range(n-1)]
tree2=[i for i in tree1 if i[0]==1]
tree1=[i for i in tree1 if i[0]!=1]

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

l=0
while tree1!=[]:
    for j in tree2[l:][:]:
        tree3=[k if j[1]==k[0] else [k[1],k[0]] for k in tree1 if j[1] in k]
        #print(tree3)
        l+=len(tree3)
        tree1=[k for k in tree1 if j[1] not in k]
        tree2.extend(tree3)
#print(tree2)
for i in tree2:
    c[i[1]-1]+=c[i[0]-1]

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
#木の問題と書いてあるが、実際は木の構造がわからなくても解ける
#根の方から順に足していってあげればいい
#aiがbiの親であるとは限らないらしい
#これがある以上、木構造を作るしかない
#辞書で(他の人のコードを参照)親子関係を保持できる、初めて知った
#は？結局他人の使わないやんけ
from copy import deepcopy

n,q=map(int,input().split())
tree1=[list(map(int,input().split())) for i in range(n-1)]
tree2=[i for i in tree1 if i[0]==1]
tree1=[i for i in tree1 if i[0]!=1]

c=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x
l=0
while tree1!=[]:
    for j in tree2[l:][:]:
        #l+=1
        #三項演算子でelseは省略できない
        #print(tree1)
        tree3=[(k if j[1]==k[0] else ([k[1],k[0]] if j[1]==k[1] else None)) for k in tree1]
        #print(tree3)
        tree3=[i for i in tree3 if i is not None]
        l+=len(tree3)
        tree1=[k for k in tree1 if j[1] not in k]
        tree2.extend(tree3)
#print(tree2)
for i in tree2:
    c[i[1]-1]+=c[i[0]-1]

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
tree1=[list(map(int,input().split())) for i in range(n-1)]
tree2=[i for i in tree1 if i[0]==1]
tree1=[i for i in tree1 if i not in tree2]

c=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x
    
l=0
while tree1!=[]:
    for j in tree2[:][l:]:
        l+=1
        for k in tree1[:]:
            if j[1]==k[0]:
                tree2.append(k)
                tree1.remove(k)
            elif j[1]==k[1]:
                tree2.append([k[1],k[0]])
                tree1.remove(k)



for i in tree2:
    c[i[1]-1]+=c[i[0]-1]

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
#木の問題と書いてあるが、実際は木の構造がわからなくても解ける
#根の方から順に足していってあげればいい
#aiがbiの親であるとは限らないらしい
#これがある以上、木構造を作るしかない
#辞書で(他の人のコードを参照)親子関係を保持できる、初めて知った
#は？結局他人の使わないやんけ

n,q=map(int,input().split())
tree1=[list(map(int,input().split())) for i in range(n-1)]
tree2=[i for i in tree1 if i[0]==1]
tree1=[i for i in tree1 if i not in tree2]

l=0
while tree1!=[]:
    for j in tree2[:][l:]:
        l+=1
        for k in tree1[:]:
            if j[1]==k[0]:
                tree2.append(k)
                tree1.remove(k)
            elif j[1]==k[1]:
                tree2.append(k[::-1])
                tree1.remove(k)

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

for i in tree2:
    c[i[1]-1]+=c[i[0]-1]

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
#木の問題と書いてあるが、実際は木の構造がわからなくても解ける
#根の方から順に足していってあげればいい
#aiがbiの親であるとは限らないらしい
#これがある以上、木構造を作るしかない
#辞書で(他の人のコードを参照)親子関係を保持できる、初めて知った
#は？結局他人の使わないやんけ

n,q=map(int,input().split())
tree1=[list(map(int,input().split())) for i in range(n-1)]
tree2=[i for i in tree1 if i[0]==1]
tree1=[i for i in tree1 if i not in tree2]

l=0
while tree1!=[]:
    for j in tree2[:][l:]:
        l+=1
        for k in tree1[:]:
            if j[1]==k[0]:
                l+=1
                tree2.append(k)
                tree1.remove(k)
            elif j[1]==k[1]:
                l+1
                tree2.append(k[::-1])
                tree1.remove(k)

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

for i in tree2:
    c[i[1]-1]+=c[i[0]-1]

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
#木の問題と書いてあるが、実際は木の構造がわからなくても解ける
#根の方から順に足していってあげればいい
#aiがbiの親であるとは限らないらしい
#これがある以上、木構造を作るしかない
#辞書で(他の人のコードを参照)親子関係を保持できる、初めて知った

n,q=map(int,input().split())
tree1=[list(map(int,input().split())) for i in range(n-1)]
tree2=[i for i in tree1 if i[0]==1]
tree1=[i for i in tree1 if i not in tree2]

l=0
while tree1!=[]:
    for j in tree2[:]:
        for k in tree1[:]:
            if j[1]==k[0]:
                tree2.append(k)
                tree1.remove(k)
            if j[1]==k[1]:
                tree2.append(k[::-1])
                tree1.remove(k)

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

for i in tree2:
    c[i[1]-1]+=c[i[0]-1]

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
#木の問題と書いてあるが、実際は木の構造がわからなくても解ける
#根の方から順に足していってあげればいい
#aiがbiの親であるとは限らないらしい
#これがある以上、木構造を作るしかない
#辞書で(他の人のコードを参照)親子関係を保持できる、初めて知った

n,q=map(int,input().split())
tree1=[list(map(int,input().split())) for i in range(n-1)]
tree2=[i for i in tree1 if i[0]==1]
for i in tree1[:]:
    if i in tree2:
        tree1.remove(i)
l=0
while tree1!=[]:
    #print(tree2)
    #print(tree1)
    for j in tree2[:]:
        for k in tree1[:]:
            if j[1]==k[0]:
                tree2.append(k)
                tree1.remove(k)
            if j[1]==k[1]:
                tree2.append(k[::-1])
                tree1.remove(k)


#print(tree)
#ab=[list(map(int,input().split())) for i in range(n-1)]
#ab.sort(key=lambda x:(x[0],x[1]))
c=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x
#print(tree2)

for i in tree2:
    c[i[1]-1]+=c[i[0]-1]

for i in range(n-1):
    print(c[i],end=" ")
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit


setrecursionlimit(2 * 10**5) #再帰の回数制限を増やす


def add_num(i, total, parent=-1):
    """隣接リストを取り出して深さ優先探索
    自分より上層の total のカウント数と部分木の頂点としてのカウント数を足す"""
    for p in adj[i]:
        if p != parent:
            ans_lst[p] = total + tmp[p]
            if adj[p] != [parent]:
                add_num(p, total + tmp[p], i)
    return
    
    
N, Q = [int(i) for i in input().split()]

adj = [[] for _ in range(N)] # 隣接リスト
tmp = [0] * N # 部分木の根としてのカウント数 
ans_lst = [0] * N # 答えのリスト

# 隣接リストの作成
for _ in range(N - 1):
    a, b = [int(i) - 1 for i in input().split()]
    adj[a].append(b)
    adj[b].append(a)

# ｔｍｐリストの作成
for _ in range(Q):
    p, x = [int(i) for i in input().split()]
    tmp[p-1] += x

ans_lst[0] = tmp[0]
total = tmp[0]
add_num(0, total)

print(*ans_lst, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(1000000)

"""解説
いもす法っぽいことする
[入力例]
4 3
1 2
2 3
2 4
2 10
1 100
3 1

[出力例]
"""
def solve():
    N, Q = list(map(int, input().split()))
    to = [[] for _ in range(N)]  # 木

    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        a, b = a-1, b-1  # 0始まりになるように
        to[a].append(b)  # 無向グラフになるように両方に加える
        to[b].append(a)  # 無向グラフになるように両方に加える

    #print(to)

    ans = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = list(map(int, input().split()))
        p = p-1  # 0始まりになるように
        ans[p] += x

    #print(ans)

    def dfs(v, p=-1):
        for u in to[v]:
            if u==p: continue
            ans[u] += ans[v]  # いもす法っぽい累積和をする
            dfs(u, v)

    dfs(0)

    print(*ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N, Q = list(map(int,input().split()))
    adjl = [[] for _ in range(N)]
    for _ in  range(N-1):
        a, b = list(map(lambda x: int(x)-1,input().split()))
        adjl[a].append(b)
        adjl[b].append(a)
    res = [0]*N
    for _ in  range(Q):
        p, x = list(map(lambda x: int(x),input().split()))
        res[p-1] += x
    def dfs(n, parent = None):
        if parent != None:
            res[n] += res[parent]
        for neigh in adjl[n]:
            if neigh == parent:
                continue
            else:
                dfs(neigh,n)
    dfs(0)
    for _ in range(N):
        print(res[_],end=" ")
    print()





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
E = [[] for _ in range(N)]
C = [0] * N
C[0] = 0
for _ in range(N - 1):
  a, b = map(int, input().split())
  E[a - 1].append(b - 1)
  E[b - 1].append(a - 1)
for _ in range(Q):
  p, x = map(int, input().split())
  C[p - 1] += x
D = [-1] * N
D[0] = 0
Q = [0]
while Q:
  q = Q.pop(0)
  for adj in E[q]:
    if D[adj] >= 0:
      continue
    D[adj] = D[q] + 1
    C[adj] += C[q]
    Q.append(adj)
print(' '.join([str(c) for c in C]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split(" "))
 
ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
 
flags = [False]*N
dic = [[] for _ in range(N)]
rlt = [0]*N
 
for i in range(N-1):
  dic[ns[i][1]-1] += [ns[i][0]-1]
  dic[ns[i][0]-1] += [ns[i][1]-1]
  
for p, x in (map(int, input().split()) for _ in range(Q)):
  rlt[p - 1] += x

que = [0]
while len(que):
  a = que.pop(0)
  flags[a] = True
  for e in dic[a]:
    if flags[e]:
      continue
    else:
      rlt[e] += rlt[a]
      que.append(e)
    
print(" ".join(map(str, rlt)))

Submission status: Time Limit Exceeded

Solution code:
N,Q=[int(s) for s in input().split()]
e_list=[[int(s) for s in input().split()] for i in range(N-1)]
#########深さ優先探索DFS
#########親と子の判定
#########木であることを前提とする
def dfs(edge_list,root):
  reach=[[root,1,0]]
  e_list=[[e[0],e[1],0] for e in edge_list]
  vertex=root
  endflag=0
  depth=1
  ans=[]
  while True :
    ###まずvertexから到達可能なものをすべてreachに入れる
    #辺の始点がvertexであるもの
    for e in e_list:
      if (e[0]==vertex and e[2]==0):
        reach.append([e[1],0,depth])
        ans.append([e[0],e[1]])
        e[2]=1
      elif (e[1]==vertex and e[2]==0):
        reach.append([e[0],0,depth])
        ans.append([e[1],e[0]])
        e[2]=1
    ###起点になっていないもののうち最後にreachに入ったものを、次の起点とする
    for i in range(len(reach)+1):
      if reach[-i][1]==0 :
        vertex=reach[-i][0]
        depth=reach[-i][2]+1
        #####ここでprint(vertex)などを入れる
        reach[-i][1]=1
        break
      if i==len(reach):  ####全ての場所に行っていれば終了
        return ans
        break
 #   if endflag==1:   
 #     break
 # print(reach)
 # return [e[0] for e in reach]
e_list=dfs(e_list,1)
answer=[0 for i in range(N+1)]
for i in range(Q):
  a,b=[int(s) for s in input().split()]
  answer[a]+=b
for e in e_list:
  answer[e[1]]+=answer[e[0]]
answer.remove(0)
print(*answer)