Problem:


Score : 400 points

Problem Statement

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

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

Now, the following Q operations will be performed:

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

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

Constraints

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

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

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

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

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

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

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

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20



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


Sample output:
100 110 111 110

Submission status: Time Limit Exceeded

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

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

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

q = [[int(i) for i in input().split()] for j in range(Q)]
count = [0 for i in range(N)]
for i in range(Q):
    p, x = q[i]
    count[p-1] += x

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

q = [[int(i) for i in input().split()] for j in range(Q)]
count = [0 for i in range(N)]
for i in range(Q):
    p, x = q[i]
    count[p-1] += x

ls = deque([0])
seen = [0 for i in range(N)]
while len(ls) > 0:
    root = ls.popleft()
    seen[root] = 1

    for next_v in G[root]:
        if not seen[next_v]:
            count[next_v] += count[root]
            ls.append(next_v)

for i in range(N):
    if i == N-1:
        print(count[i])
    else:
        print(count[i], end=" ")

Submission status: Time Limit Exceeded

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

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

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

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

ans = [0] * n


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


dfs(0, -1, 0)

# print(add)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
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)]

from collections import defaultdict
g = defaultdict(list)
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

adder = defaultdict(int)
for p, x in px:
    p -= 1
    adder[p] += x

ans = [float('inf')] * n
ans[0] = adder[0]
qu = [0]

while qu:
    cur = qu.pop()

    for target in g[cur]:
        if ans[target] == float('inf'):
            ans[target] = ans[cur] + adder[target]
            qu.append(target)

for _ans in ans:
    print(_ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    _map, _int, _input = map, int, input
    n, q = _map(_int, _input().split())
    t = [[] for _ in range(n)]
    r = [0]*n
    for _ in range(n-1):
        a, b = map(lambda x: _int(x)-1, _input().split())
        t[a].append(b)
        t[b].append(a) # leafの順序が保証されないため双方向にリンクを設定
    # root(t[0])からleafまで親ノードのリンクを消しながら辿る
    e = [0]
    eadd = e.append
    while len(e) > 0:
        i = e.pop()
        for j in t[i]:
            t[j].remove(i)
            eadd(j)
    
    query = [0] * n
    for _ in range(q):
        p, x = _map(_int, _input().split())
        query[p-1] += x
    
    for p, x in enumerate(query):
        #p -= 1
        r[p] += x
        s = t[p][:]
        spop = s.pop
        sext = s.extend
        while len(s) > 0:
            i = spop()
            r[i] += x
            sext(t[i])
    print(*r)
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    _map, _int, _input = map, int, input
    n, q = _map(_int, _input().split())
    t = [[] for _ in range(n)]
    r = [0]*n
    for _ in range(n-1):
        a, b = map(lambda x: _int(x)-1, _input().split())
        t[a].append(b)
        t[b].append(a) # leafの順序が保証されないため双方向にリンクを設定
    # root(t[0])からleafまで親ノードのリンクを消しながら辿る
    e = [0]
    eadd = e.append
    while len(e) > 0:
        i = e.pop()
        for j in t[i]:
            t[j].remove(i)
            eadd(j)
    
    for _ in range(q):
        p, x = _map(_int, _input().split())
        p -= 1
        r[p] += x
        s = t[p][:]
        spop = s.pop
        sext = s.extend
        while len(s) > 0:
            i = spop()
            r[i] += x
            sext(t[i])
    print(*r)
            
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())
    t = [[] for _ in range(n)]
    r = [0]*n
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        t[a].append(b)
        t[b].append(a) # leafの順序が保証されないため双方向にリンクを設定
    # root(t[0])からleafまで親ノードのリンクを消しながら辿る
    e = [0]
    while len(e) > 0:
        i = e.pop()
        for j in t[i]:
            t[j].remove(i)
            e.append(j)
    #print("tree", t)
    
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        r[p] += x
        s = t[p][:]
        while len(s) > 0:
            #print("next", s)
            #print("end", e)
            i = s.pop()
            r[i] += x
            s.extend(t[i])
        #print(">>", *r)
    print(*r)
            
        
if __name__ == "__main__":
    main()

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)]
ans = [0 for _ in range(n)]
ch = [[] for _ in range(n)]
pr = [0 for _ in range(n)]
ed = pr[:]
rl = ch[:]
od = [0]
for a,b in ab:
    rl[a-1].append(b-1)
    rl[b-1].append(a-1)
dq = deque([0])
ed[0] = 1
while dq:
    v = dq.popleft()
    for x in rl[v]:
        if ed[x] == 0:
            dq.append(x)
            ed[x] = 1
            od.append(x)


for a,b in ab:
    ia = od.index(a-1)
    ib = od.index(b-1)
    if ia > ib:
        a,b = b,a
    pr[b-1] = a-1
    ch[a-1].append(b-1)     
cntl = [0 for _ in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    cntl[p-1] += x
#print(cntl)
#print(pr)
#print(ch)
#print(od)
for y in od:
    x = cntl[y]
    x += ans[pr[y]] 
    ans[y] = x

   

print(*ans)

Submission status: Time Limit Exceeded

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

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

graph = defaultdict(set)

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

arr = [0] * (n + 1)

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


def solve(graph, arr):
    curr, root = 1, -1
    visited = [True] * 2 + [False] * (n - 1)

    def dfs(curr, root):
        stack = graph[curr]

        while stack:
            leaf = stack.pop()
            if visited[leaf]:
                continue
            arr[leaf] += arr[curr]
            visited[leaf] = True
            dfs(leaf, curr)

        return arr

    return dfs(curr, root)


ans = solve(graph, arr)

print(*ans[1:])

Submission status: Time Limit Exceeded

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

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

graph = defaultdict(deque)

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

arr = [0] * (n + 1)

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


def solve(graph, arr):
    curr, root = 1, -1
    visited = [True] * 2 + [False] * (n - 1)

    def dfs(curr, root):
        stack = graph[curr]

        while stack:
            leaf = stack.pop()
            if visited[leaf]:
                continue
            arr[leaf] += arr[curr]
            visited[leaf] = True
            dfs(leaf, curr)

        return arr

    return dfs(curr, root)


ans = solve(graph, arr)

print(*ans[1:])

Submission status: Time Limit Exceeded

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

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

graph = [set() for _ in range(n + 1)]

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

arr = [0] * (n + 1)

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


def solve(graph, arr):
    curr, root = 1, -1
    visited = [0] * (n + 1)

    def dfs(curr, root):
        stack = graph[curr]

        while stack:
            leaf = stack.pop()
            if leaf == root:
                continue
            arr[leaf] += arr[curr]
            dfs(leaf, curr)

        return arr

    return dfs(curr, root)


ans = solve(graph, arr)

print(*ans[1:])

Submission status: Time Limit Exceeded

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

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

graph = defaultdict(deque)

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

arr = [0] * (n + 1)

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


def dfs(curr, root):
    stack = graph[curr]

    while stack:
        leaf = stack.pop()
        if leaf == root:
            continue
        arr[leaf] += arr[curr]
        dfs(leaf, curr)


dfs(1, -1)

print(*arr[1:])

Submission status: Time Limit Exceeded

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

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

graph = defaultdict(deque)

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

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


def solve(graph, arr):
    curr, root = 1, -1

    def dfs(curr, root):
        stack = graph[curr]

        while stack:
            leaf = stack.pop()
            if leaf == root:
                continue
            arr[leaf] += arr[curr]
            dfs(leaf, curr)

        return arr

    return dfs(curr, root)


ans = solve(graph, arr)

print(*ans[1:])

Submission status: Time Limit Exceeded

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

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

graph = defaultdict(deque)

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

ans = [0] * (n + 1)

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


def solve(graph, ans):
    curr, root = 1, -1

    def dfs(curr, root):
        stack = graph[curr]

        while stack:
            leaf = stack.pop()
            if leaf == root:
                continue
            ans[leaf] += ans[curr]
            dfs(leaf, curr)

        return ans

    return dfs(curr, root)


ans = solve(graph, ans)

print(*ans[1:])

Submission status: Time Limit Exceeded

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

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

graph = defaultdict(set)

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

ans = [0] * (n + 1)

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


def solve(graph, ans):
    curr, root = 1, -1

    def dfs(curr, root):
        for leaf in graph[curr]:
            if leaf == root:
                continue
            ans[leaf] += ans[curr]
            dfs(leaf, curr)
        return ans

    return dfs(curr, root)


ans = solve(graph, ans)

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,q=mp()
tree=[[] for i in range(n+1)]
c=[0]*(n+1)
done=[0]*(n+1)
for i in range(n-1):
    a,b=mp()
    tree[a].append([a,b])
    tree[b].append([b,a])
for i in range(q):
    p,x=mp()
    c[p]+=x
que=deque()
que.append(tree[1])
done[1]=1
while len(que):
    q=que.popleft()
    for v in q:
        if done[v[1]]==0:
            done[v[1]]=1
            c[v[1]]+=c[v[0]]
            que.append(tree[v[1]])
print(*c[1:])

Submission status: Time Limit Exceeded

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

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

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

ans=[0]*n

check=[False]*n
temp=0
def dfs(v):
    global temp

    check[v]=True
    temp+=add[v]
    ans[v]=temp

    for next in G[v]:
        if check[next]:
            continue
        dfs(next)
    
    temp-=add[v]

dfs(0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,q = readInts()
G = [[] for _ 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)
val = [0] * n
for i in range(q):
    p,x = readInts()
    p -= 1
    val[p] += x

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

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

Submission status: Time Limit Exceeded

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,q = readInts()
G = [[] for _ 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)
val = [0] * n
for i in range(q):
    p,x = readInts()
    p -= 1
    val[p] += x

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n, q = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n-1)]
    a = [ab[i][0] for i in range(n-1)]
    b = [ab[i][1] for i in range(n-1)]
    px = [list(map(int, input().split())) for i in range(q)]
    p = [px[i][0] for i in range(q)]
    x = [px[i][1] for i in range(q)]
    res = [0]*n
    g = [[] for i in range(n)]
    for i in range(n-1):
        g[a[i] - 1].append(b[i] - 1)
        g[b[i] - 1].append(a[i] - 1)
    def dfs(v, p):
        if p != -1:
            res[v] += res[p]
        for i in g[v]:
            if i == p: continue
            dfs(i, v)

    for i in range(q):
        res[p[i]-1] += x[i]

    dfs(0, -1)
    
    print(*res,sep = " ")
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Time Limit Exceeded

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

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

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

ans_q = queue.Queue()
ans_q.put((0, ans[0]))

while not ans_q.empty():
    start = ans_q.get()
    cost = start[1]
    ans[start[0]] = cost
    for e in edge[start[0]]:
        if checked[e] == 0:
            checked[e] = 1
            ans_q.put((e, cost+ans[e]))

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

Submission status: Time Limit Exceeded

Solution code:
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)]

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

from collections import deque
    
c = [0] * N
for j, (pj, xj) in enumerate(px):
    c[pj - 1] += xj
    
ans = [None] * N
q_0 = deque([(0, 0)])
while len(q_0) > 0:
    score, src = q_0.popleft()
    # print("#", score, src)
    score_tmp = score + c[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] == None:
            q_0.append((score_tmp, dst))

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

Submission status: Time Limit Exceeded

Solution code:
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)]

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

from collections import deque
    
c = [0] * N
for j, (pj, xj) in enumerate(px):
    c[pj - 1] += xj
    
ans = [None] * N
ans[0] = c[0]
q_0 = deque([(c[0], 0)])
while len(q_0) > 0:
    score, src = q_0.popleft()
    # print("#", score, src)
    ans[src] = score
    for dst in graph[src]:
        if ans[dst] == None:
            q_0.append((score + c[dst], dst))

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

Submission status: Time Limit Exceeded

Solution code:
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)]

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

from collections import deque
    
q = deque([(0, 0)])
d = [None] * N
p = [None] * N
while len(q) > 0:
    depth, src = q.popleft()
    d[src] = depth
    for dst in graph[src]:
        if d[dst] == None:
            p[dst] = src
            q.append((depth + 1, dst))

c = [0] * N
for j, (pj, xj) in enumerate(px):
    c[pj - 1] += xj
    
ans = [None] * N
for i in range(N):
    if ans[i] != None: continue
    q = []
    src = i
    while src != None:
        if ans[src] != None:
            q.append((src, ans[src]))
            src = None
        else:
            q.append((src, c[src]))
            src = p[src]
    #
    score = 0
    while len(q) > 0:
        src, score_tmp = q.pop()
        score += score_tmp
        ans[src] = score

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

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)
readline = sys.stdin.readline

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

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

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

ans = [0]*n

def dfs(v, p, value): # v:これから見るnode、p:親node、
    value += add[v]
    ans[v] = value
    for u in to[v]:
        if u == p: continue # 親nodeは足さない
        dfs(u, v, value)

dfs(0,-1,0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
"""
keyword: dfs
"""

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

#n, q = map(int, input().split())
n,q = [int(i) for i in readline().split()]
to = [[] for _ in range(n)]
ans = [0]*n

def dfs(v, p=-1): # v:これから見るnode、p:親node
    global ans
    for i in range(len(to[v])):
        u = to[v][i]
        if u == p: continue # 親nodeは確認済みなので見ない
        ans[u] += ans[v]
        dfs(u, v)

for i in range(n-1):
#    a, b = map(int, input().split())
    a,b = [int(i) for i in readline().split()]
    a -= 1; b -= 1
    to[a].append(b)
    to[b].append(a)

for i in range(q):
#    v, x = map(int, input().split())
    v,x = [int(i) for i in readline().split()]
    v -= 1
    ans[v] += x

dfs(0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
"""
keyword: dfs
"""

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
to = [[] for _ in range(n)]
ans = [0]*n

def dfs(v, p=-1): # v:これから見るnode、p:親node
    global ans
    for i in range(len(to[v])):
        u = to[v][i]
        if u == p: continue # 親nodeは確認済みなので見ない
        ans[u] += ans[v]
        dfs(u, v)

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

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

dfs(0)

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

branch = [[] for _ in range(N)]
res = [0,]*N
root = [None]*N
t = 0

def search(p):
    global t
    root[p-1] = t
    t += 1
    for q in branch[p-1]:
        if root[q-1] != None:
            continue
        search(q)
    t -= 1

def dfs(p, x):
    res[p-1] += x
    for q in branch[p-1]:
        if root[q-1] < root[p-1]:
            continue
        dfs(q, x)


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

search(1)

for _ in range(Q):
    p, x = map(int, input().split())
    dfs(p, x)


print(*res)

Submission status: Time Limit Exceeded

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

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

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

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

isSearched = [False]*(n+1)
isSearched[0] = True
def dfs(now):
    ln = l[now]
    for i in ln:
        if isSearched[i]:
            continue
        score[i] += score[now]
        isSearched[i] = True
        dfs(i)

dfs(0)
w = ""
for i in range(n-1):
    w += (str(score[i]) + " ")

w += str(score[n-1])
print(w)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

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

sys.setrecursionlimit(10**6)

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


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


ans = [0] * n


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


dfs(0, -1, 0)

# print(add)

print(*ans)

Submission status: Time Limit Exceeded

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

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

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


root_tree = [[] for _ in range(n)]

check = [0 for _ in range(n)]

queue = deque([0])
while(len(queue) > 0):
    # print(queue)
    index = queue.pop()
    list_ = tree[index]
    if check[index] == 1:
        continue
    check[index] = 1
    # print(list_)
    for child in list_:
        if check[child] == 0:
            root_tree[index].append(child)
            queue.append(child)

ans = [0 for _ in range(n)]

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


# queue = deque([0])
# while(len(queue) > 0):
#     print(queue)
#     index = queue.pop()
#     list_ = tree[index]
#     if check[index] == 1:
#         continue
#     check[index] = 1
#     for child in list_:
#         if check[child] == 0:
#             root_tree[index].append(child)
#             queue.append(child)


queue = deque([0])

# add = ans[0]
while(len(queue) > 0):
    # print(queue)
    index = queue.pop()
    add = ans[index]
    list_ = root_tree[index]
    for child in list_:
        ans[child] += add
        queue.append(child)

for i in ans:
    print(i, "", end="")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
num_ver, times_plus = map(int,input().split())
graph_ls = [[] for _ in range(num_ver)]
for i in range(num_ver-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    graph_ls[a].append(b)
    graph_ls[b].append(a)

point_ls = [0] * num_ver
for i in range(times_plus):
    ver, point = map(int,input().split())
    ver -= 1
    point_ls[ver] += point

ans_ls = [0] * num_ver
visited_ls = [0] * num_ver

def dfs(ver,point_before):
    visited_ls[ver] = 1
    point_after = point_before + point_ls[ver]
    ans_ls[ver] = point_after
    for nex in graph_ls[ver]:
        if not visited_ls[nex]:
            dfs(nex, point_after)

dfs(0,0)
for ans in ans_ls:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = map(int, input().split())
child = [[i] for i in range(N)]
counter = [0] * N
graph = [deque([]) for _ in range(N + 1)]
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 i in range(Q):
  p, x = map(int, input().split())
  counter[p - 1] += x 

#print(graph, counter)
# 深さ優先探索
def dfs(v):
    #global time
    #time += 1
    visited[v] = 1
    stack = [v]
    #print(stack, v)
    #arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if visited[w] == 0:
              visited[w] = 1
              counter[w] += counter[v]
              stack.append(w) 
        else:
            stack.pop()          
    return 0

visited = [0] * N
# 孤立している頂点対策
for i in range(N):
    if visited[i] == 0:
       dfs(i)


#print(counter)
for i in range(N):
  print(counter[i], end = " ")

Submission status: Time Limit Exceeded

Solution code:
# 20/5/28
import sys
sys.setrecursionlimit(3 * 10 ** 5)
# input = sys.stdin.readline

def bfs(root, parent):
    global AL, cnt
    for v in AL[root]:
        if v != parent:
            cnt[v] += cnt[root]
            bfs(v, root)

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

cnt = [0] * (N + 1)
for j in range(Q):
    p, x = [int(x) for x in input().split()]
    cnt[p] += x

bfs(1, -1)
print(*cnt[1:])

Submission status: Time Limit Exceeded

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

def bfs(root, parent):
    global AL, cnt
    for v in AL[root]:
        if v != parent:
            cnt[v] += cnt[root]
            bfs(v, root)

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

cnt = [0] * (N + 1)
for j in range(Q):
    p, x = [int(x) for x in input().split()]
    cnt[p] += x

bfs(1, -1)
s = " ".join(map(str, cnt[1:]))
print(s)