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:
# D - Ki

import queue

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

children = [[] for _ in range(N)]
points = [0] * N

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

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

q = queue.Queue()
q.put(0)
visited = [False] * N
while not q.empty():
    key = q.get()
    for child in children[key]:
        if visited[child] == True:
            continue
        points[child] += points[key]
        visited[key] = True
        q.put(child)

print(*points)

Submission status: Time Limit Exceeded

Solution code:
# D - Ki

import queue

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

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

q = queue.Queue()
q.put(0)
visited = [False] * N
while not q.empty():
    key = q.get()
    visited[key] = True
    for child in children[key]:
        if visited[child] == False:
            points[child] += points[key]
            q.put(child)

print(*points)

Submission status: Time Limit Exceeded

Solution code:
# D - Ki

import queue

class Node:
    def __init__(self, children, point):
        self.children = children
        self.point = 0

N, Q = map(int, input().split())
nodes = [Node([], 0) for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].children.append(b - 1)
    nodes[b - 1].children.append(a - 1)

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

q = queue.Queue()
q.put(0)
visited = [False] * N
while not q.empty():
    key = q.get()
    visited[key] = True
    for child in nodes[key].children:
        if visited[child] == False:
            nodes[child].point += nodes[key].point
            q.put(child)

print(*[node.point for node in nodes])

Submission status: Time Limit Exceeded

Solution code:
class Tree:
    value=0
    def __init__(self,position):
        self.position = position
        self.kid = set()
        self.value = 0

    def add_kid(self,it):
        self.kid.add(it)

    def add_val(self,val):
        self.value += val

    def calc(self,val=0):
        self.add_val(val)
        # print("called",self.position)
        for i in self.kid:
            if(i.position in visited):
                continue
            visited.add(i.position)
            i.calc(self.value)

    def print_val(self):
        print(self.value,end=" ")


N,Q = [int(x) for x in input().split()]
ki = [Tree(i) for i in range(N)]

for i in range(N-1): #O(N)
    a,b = [int(x) for x in input().split()]
    ki[a-1].add_kid(ki[b-1])
    ki[b-1].add_kid(ki[a-1])

for i in range(Q): #O(Q)
    position,val = [int(x) for x in input().split()]
    ki[position-1].add_val(val)

visited = set()
visited.add(0)
ki[0].calc() #Recursion

for i in ki:
    i.print_val()
print()

Submission status: Time Limit Exceeded

Solution code:
class Tree:
    value=0
    def __init__(self,position):
        self.position = position
        self.kid = set()
        self.value = 0

    def add_kid(self,it):
        self.kid.add(it)

    def add_val(self,val):
        self.value += val

    def calc(self,val=0):
        self.add_val(val)
        # print("called",self.position)
        for i in self.kid:
            if(i.position in visited):
                continue
            visited.add(i.position)
            i.calc(self.value)

    def print_val(self):
        print(self.value,end=" ")

N,Q = [int(x) for x in input().split()]
ki = [Tree(i) for i in range(N)]

for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    ki[a-1].add_kid(ki[b-1])
    ki[b-1].add_kid(ki[a-1])

for i in range(Q):
    position,val = [int(x) for x in input().split()]
    ki[position-1].add_val(val)

visited = set()
visited.add(0)
ki[0].calc()

for i in ki:
    i.print_val()
print()

Submission status: Time Limit Exceeded

Solution code:
class Tree:
    value=0
    def __init__(self,position):
        self.position = position
        self.kid = set()
        self.value = 0

    def add_kid(self,it):
        self.kid.add(it)

    def add_val(self,val):
        self.value += val

    def calc(self,val=0):
        self.add_val(val)
        # print("called",len(self.kid))
        for i in self.kid:
            if(not(i.position in serched)):
                serched.add(i.position)
                i.calc(self.value)

    def print_val(self):
        print(self.value,end=" ")

N,Q = [int(x) for x in input().split()]
ki = [Tree(i) for i in range(N)]

for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    ki[a-1].add_kid(ki[b-1])
    ki[b-1].add_kid(ki[a-1])

for i in range(Q):
    position,val = [int(x) for x in input().split()]
    ki[position-1].add_val(val)

serched = set()
serched.add(0)
ki[0].calc()

for i in ki:
    i.print_val()
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)
 
tree = dict()
cnt = dict()
N, Q = list(map(int, input().split())) 
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    if a not in tree:
        tree[a] = []
    tree[a].append(b)
    if b not in tree:
        tree[b] = []
    tree[b].append(a)
    
for _ in range(Q):
    p, x = list(map(int, input().split()))
    if p not in cnt:
        cnt[p] = 0
    cnt[p] += x
 
ans = [0 for _ in range(N)]
visited = set()

@lru_cache(maxsize=None)
def dfs(node, val):
    visited.add(node)
    if node in cnt:
        val += cnt[node]
    ans[node-1] += val
    if node not in tree:
        return
    nexts = tree[node]
    for nx_node in nexts:
        if nx_node not in visited:
            dfs(nx_node, val)

dfs(1, 0)
ans = [str(val) for val in ans]
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

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

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

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

visited = [False for _ in range(N + 1)]
visited[1] = True


def add(i, val):
    X[i] += val
    for to in E[i]:
        if visited[to]:
            continue
        visited[to] = True
        add(to, X[i])


add(1, 0)

print(*X[1:])

Submission status: Time Limit Exceeded

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


def dfs(now, prev=-1):
    for next in tree[now]:
        # 1個前のノードを参照した時はcontinue
        if next == prev:
            continue

        # 現在のポイントを次のノードへ加算して累積和をとる
        point[next] += point[now]

        # 次のノードへ
        dfs(next, now)


N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
point = [0]*N

# 木構造を2次元配列で表現。要素Xのノードからつながっているノード番号が格納される。
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

# 各ノードのポイントを求める
for _ in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x

dfs(0)
print(*point)

Submission status: Time Limit Exceeded

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

N, Q = [int(_) for _ in input().split()]

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

P = [0] * (N + 1)

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


def f(v, parent=0):
    P[v] += P[parent]

    for next_v in edges[v]:
        if next_v == parent: continue
        f(next_v, v)


f(1)
print(*[P[i] for i in range(1, N + 1)])

Submission status: Time Limit Exceeded

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

N, Q = [int(_) for _ in input().split()]

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

P = [0] * (N + 1)

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


def f(v, parent=0):
    P[v] += P[parent]

    for next_v in edges[v]:
        if next_v == parent: continue
        f(next_v, v)


f(1)
print(*[P[i] for i in range(1, N + 1)])

Submission status: Time Limit Exceeded

Solution code:
import queue
n,q = map(int,input().split())
c = [[] for _ in range(n)]
for i in range(n-1):
    A,B = map(int,input().split())
    c[A-1].append(B)
    c[B-1].append(A)
z = [0] * n
for i in range(q):
    P,X = map(int,input().split())
    z[P - 1] += X


d = [-1] * n
d[0] = 0
q = queue.Queue()
q.put(1)
while(not q.empty()):
    tp = q.get()
    td = d[tp - 1]
    for n2 in c[tp - 1]:
        if(d[n2 - 1] == -1):
            d[n2 - 1] = td + 1
            z[n2 - 1] += z[tp - 1]
            q.put(n2)

print(*z)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i 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

from collections import deque
todo = deque([(1,0)])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append((y,x))

print(*value[1:])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i 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

from collections import deque
todo = deque([[1,0]])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append([y,x])

print(*value[1:])

Submission status: Time Limit Exceeded

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

graph={}
for i in range(1,N+1):
    graph[i]=[]
for i in range(N-1):
    graph[ab[i][0]].append(ab[i][1])
    graph[ab[i][1]].append(ab[i][0])

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

from collections import deque
todo = deque([[1,0]])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append([y,x])

print(*value[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_rpw_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def dfs(current, parent, edges, ans_list):
    for child in edges[current]:
        if child == parent:
            continue
        ans_list[child] += ans_list[current]
        dfs(child, current, edges, ans_list)

def main():
    n, q = i_map()

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = i_map()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    ans_list = [0] * n
    for i in range(q):
        p, x = i_map()
        ans_list[p-1] += x

    dfs(0, -1, edges, ans_list)

    print(*ans_list)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_rpw_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 7)
INF = float('inf')
MOD = 10 ** 9 + 7

def dfs(current, parent, edges, ans_list):
    for child in edges[current]:
        if child == parent:
            continue
        ans_list[child] += ans_list[current]
        dfs(child, current, edges, ans_list)

def main():
    n, q = i_map()

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = i_map()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    ans_list = [0] * n
    for i in range(q):
        p, x = i_map()
        ans_list[p-1] += x

    dfs(0, -1, edges, ans_list)

    print(*ans_list)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def i_map(): return map(int, input().split())
sys.setrecursionlimit(10 ** 7)

def dfs(current, parent, edges, ans_list):
    for child in edges[current]:
        if child == parent:
            continue
        ans_list[child] += ans_list[current]
        dfs(child, current, edges, ans_list)

def main():
    n, q = i_map()

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = i_map()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    ans_list = [0] * n
    for i in range(q):
        p, x = i_map()
        ans_list[p-1] += x

    dfs(0, -1, edges, ans_list)

    print(*ans_list)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_rpw_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def dfs(current, parent, edges, ans_list):
    for child in edges[current]:
        if child == parent:
            continue
        ans_list[child] += ans_list[current]
        dfs(child, current, edges, ans_list)

def main():
    n, q = i_map()

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = i_map()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    ans_list = [0] * n
    for i in range(q):
        p, x = i_map()
        ans_list[p-1] += x

    dfs(0, -1, edges, ans_list)

    print(*ans_list)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_rpw_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def dfs(current, parent, edges, ans_list):
    for child in edges[current]:
        if child == parent:
            continue
        ans_list[child] += ans_list[current]
        dfs(child, current, edges, ans_list)

def main():
    n, q = i_map()

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = i_map()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    ans_list = [0] * n
    for i in range(q):
        p, x = i_map()
        ans_list[p-1] += x

    dfs(0, -1, edges, ans_list)

    print(*ans_list)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

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

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

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

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

dfs(0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

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

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

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

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

dfs(0)

print(*ans)
# for i in ans:print(i)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
sys.setrecursionlimit(10000000)

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

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

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

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

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

dfs(0)

for i in ans:print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
#def input():
    #return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b
# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue
        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]
        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)

Submission status: Time Limit Exceeded

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

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

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

X = [list(map(int, input().split())) for _ in range(Q)]
C = [0 for _ in range(N)]

for x in X:
    C[x[0]-1] += x[1]

Seen = [False] * N


def dfs(v, c):
    Seen[v] = True
    C[v] += c

    if E[v] == []:
        return

    for nextv in E[v]:
        if Seen[nextv]:
            continue
        dfs(nextv, C[v])


dfs(0, 0)

print(*C)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
#普通にinputするよりstdin.readlineのほうがはやい
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]


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

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

def dfs(v,par):
    for nv in Graph[v]:
        if nv==par:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv,v)

dfs(1,-1)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]
seen=[False for _ in range(n+1)]

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

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

def dfs(v):
    seen[v]=True
    for nv in Graph[v]:
        if seen[nv]:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv)

dfs(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

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

n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]
seen=[False for _ in range(n+1)]

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

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x
    
def dfs(v):
    seen[v]=True
    for nv in Graph[v]:
        if seen[nv]:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv)

dfs(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

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

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

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

seen=[False for _ in range(n+1)]
ans=[0 for _ in range(n+1)]
ans[1]=score[1]
def dfs(v):
    seen[v]=True
    for nv in Graph[v]:
        if seen[nv]:
            continue
        else:
            ans[nv]=ans[v]+score[nv]
            dfs(nv)

dfs(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import sys
def input():
    return sys.stdin.readline()[:-1]
    
n,q = map(int,input().split())
graph = [[] for _ in range(n)]
point = [0]*n

for _ in range(n-1):
    a, b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
#print(graph)
for _ in range(q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b
#print(point)

def dfs(now , prev = -1):
    for next in graph[now]:
        #print(next)
        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 _ in range(n-1):
    a, b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
#print(graph)
for _ in range(q):
    a, b = map(int,input().split())
    a -= 1
    point[a] += b
#print(point)

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

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0] * (n + 1)
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    ans = [0] * (n + 1)
    que = queue.Queue()
    visited = []

    def bfs(root, base):
        base += counter[root]
        visited.append(root)
        for e in tree[root]:
            if e in visited:
                continue
            que.put(e)
            counter[e] += base

        while not que.empty():
            x = que.get()
            point = counter[x]
            visited.append(x)
            for e in tree[x]:
                if e in visited:
                    continue
                que.put(e)
                counter[e] += point

    bfs(1, 0)
    for i in range(1, n + 1):
        print(counter[i], '', end='')
    return ans


m()

Submission status: Time Limit Exceeded

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

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0] * (n + 1)
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    ans = [0] * (n + 1)
    visited = []
    add_visited = visited.append
    def dfs(root, point):
        point += counter[root]
        ans[root] = point
        add_visited(root)
        for j in tree[root]:
            if j in visited:
                continue
            dfs(j, point)
        return

    dfs(1, 0)
    for i in range(1, n + 1):
        print(ans[i], '', end='')
    return ans


m()

Submission status: Time Limit Exceeded

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

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0 for _ in range(n + 1)]
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    ans = [0] * (n + 1)
    visited = []

    def dfs(root, point):
        point += counter[root]
        ans[root] = point
        visited.append(root)
        for j in tree[root]:
            if j in visited:
                continue
            dfs(j, point)
        return

    dfs(1, 0)
    for i in range(1, n + 1):
        print(ans[i], '', end='')
    return ans


m()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
input = lambda: sys.stdin.readline().strip()

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0 for _ in range(n + 1)]
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    ans = [0] * (n + 1)
    visited = []

    def dfs(root, point):
        point += counter[root]
        ans[root] = point
        visited.append(root)
        for j in tree[root]:
            if j in visited:
                continue
            dfs(j, point)
        return

    dfs(1, 0)
    for i in range(1, n + 1):
        print(ans[i], '', end='')
    return ans


m()

Submission status: Time Limit Exceeded

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

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0 for _ in range(n + 1)]
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    ans = [0] * (n + 1)
    visited = []

    def dfs(root, point):
        point += counter[root]
        ans[root] = point
        visited.append(root)
        for j in tree[root]:
            if j in visited:
                continue
            dfs(j, point)
        return

    dfs(1, 0)
    for i in range(1, n + 1):
        print(ans[i], '', end='')
    return ans


m()

Submission status: Time Limit Exceeded

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

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

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

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


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)