Problem:


Score : 400 points

Problem Statement

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

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

Now, the following Q operations will be performed:

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

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

Constraints

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

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

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

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

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

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

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

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20



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


Sample output:
100 110 111 110

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
from bisect import bisect, bisect_left


class Node:
    def __init__(self, idx):
        self.idx = idx
        self.v = 0
        self.parent = None
        self.children = []

    def add(self, x):
        self.v += x
        for c in self.children:
            c.add(x)

    def make_tree(self, addval=0):
        self.v += addval
        keyidx = bisect_left(brs_keys, self.idx)
        while keyidx < len(brs_keys) and brs_keys[keyidx] == self.idx:
            ni = brs[keyidx][1]
            node = nodes[ni]
            if not node.children:
                self.children.append(node)
            keyidx += 1
        for c in self.children:
            c.make_tree(self.v)

    def __str__(self):
        return str(self.idx)


N, Q = [int(_) for _ in input().split()]
nodes = [Node(i) for i in range(0, N)]

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

brs.sort()
brs_keys = [b[0] for b in brs]

# for n in nodes:
#     print(n.idx, [str(c) for c in n.children])

for i in range(Q):
    p, x = [int(_) for _ in input().split()]
    nodes[p - 1].v += x
    # nodes[p - 1].add(x)

nodes[0].make_tree()

print(*[n.v for n in nodes])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
a=[0]*(n-1)
c=[0 for i in range(n)]
for i in range(n-1):
  a[i]=list(map(int,input().split()))
 
a.sort()
 
for i in range(q):
  x,y=map(int,input().split())
  c[x-1]+=y
 
for i in range(n-1):
  c[a[i][1]-1]+=c[a[i][0]-1]
 
print(*c)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    graph = defaultdict(list)
    scores = defaultdict(int)
    N, Q = l_inpl()
    for _ in range(N-1):
        a, b = l_inpl()
        graph[a].append(b)
    for _ in range(Q):
        p, x = l_inpl()
        scores[p] += x

    ans = [0] * N
    def dfs(graph, node_start, visited, scores, score):
        if node_start in visited:
            return visited
        visited.add(node_start)
        score += scores[node_start]
        ans[node_start-1] = score
        for node_end in graph[node_start]:
            dfs(graph, node_end, visited, scores, score)
        return visited

    dfs(graph, 1, set(), scores, 0)
    for s in ans:
        print(s)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


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

tree = {}
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

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

stack = [1]
while stack:
    label = stack.pop()
    if tree.get(label):
        for next_label in tree[label]:
            count[next_label] += count[label]
        stack += tree[label]

ans = count[1:]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)


def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    output_lst[current_node] += adding
    for i in info_lst[current_node]:   #先の枝についても再帰
        adding += pi_xi_sum_lst[i]
        count_add(info_lst, pi_xi_sum_lst, output_lst, i, adding)
        adding -= pi_xi_sum_lst[i]

def glaph_2_tree(info_lst, passed_place, current_node):
    next_nodes_lst = info_lst[current_node][:]

    for next_node in next_nodes_lst:
        if passed_place[next_node]: # 通ったことがあったら、
            info_lst[current_node].remove(next_node)
        else:
            passed_place[next_node] = True
            glaph_2_tree(info_lst, passed_place, next_node)
            passed_place[next_node] = False
    passed_place[next_node] = True

N, Q = map(int, input().split())
info_lst = [[] for _ in range(N+1)]
for _ in range(N-1): # 10**5 # ここじゃない
    ai, bi = map(int, input().split())
    info_lst[ai].append(bi)
    info_lst[bi].append(ai)

passed_place = [False] * (N+1)
passed_place[1] = True
#########
glaph_2_tree(info_lst, passed_place, 1) # 10**5 # ここじゃない
#########

pi_xi_sum_lst = [0]*(N+1)
for _ in range(Q): # 10**5
    pi, xi = map(int, input().split())
    pi_xi_sum_lst[pi] += xi

output_lst = [0]*(N+1)
count_add(info_lst, pi_xi_sum_lst, output_lst, current_node=1, adding=pi_xi_sum_lst[1]) # ここじゃない
output_str = ""
for i in range(1, N+1): # ここじゃない
    output_str += str(output_lst[i]) + " "

print(output_str)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

tree = {}
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

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

stack = [1]
while stack:
    label = stack.pop()
    if tree.get(label):
        for next_label in tree[label]:
            count[next_label] += count[label]
        stack += tree[label]

ans = count[1:]
print(*ans)

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)]
ab.sort()
p = [0]*n
for i in range(q):
  a, b = map(int, input().split())
  p[a - 1] += b
s = ""
for i in ab:
  p[i[1]-1] += p[i[0]-1]
print(*p)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########
def dfs(graph, node_start, visited, scores, score, ans):
    if node_start in visited:
        return visited
    visited.add(node_start)
    score += scores[node_start]
    ans.append([node_start, score])
    for node_end in graph[node_start]:
        dfs(graph, node_end, visited, scores, score, ans)
    return visited, ans

def main():
    graph = defaultdict(list)
    scores = defaultdict(int)
    N, Q = l_inpl()
    for _ in range(N-1):
        a, b = l_inpl()
        graph[a].append(b)
    for _ in range(Q):
        p, x = l_inpl()
        scores[p] += x

    _, ans = dfs(graph, 1, set(), scores, 0, [])
    ans.sort()
    for _, s in ans:
        print(s)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

tree = {}
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

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

stack = [1]
while stack:
    label = stack.pop()
    if tree.get(label):
        for next_label in tree[label]:
            count[next_label] += count[label]
        stack += tree[label]

print(*count[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

A = defaultdict(lambda: [])
B = defaultdict(lambda: [])
_px = defaultdict(int)


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

# A = [0 for i in range(N)]
# B = [0 for i in range()]
# A = [{}]
# B = {}

ans = [0 for i in range(N)]
_a = [0 for i in range(N+1)]
PX = []

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

for q in range(Q):
    p, x = map(int, input().split())
    PX.append([p, x])
    _px[p] += x

# print(_px)
# print(A)
# print(B)
# print(PX)
counter = 0
_px = dict(_px)
# print(_px)
def find(x, plus):
    global counter
    for j in x:
        counter += 1
        ans[j-1] += plus
        if _a[j]:
            find(A[j], plus)

# for i in range(1, N):
#     counter += 1
#     ans[i-1] += _px[i]
#     find(A[i], _px[i])

for key, value in _px.items():
    counter += 1
    ans[key-1] += value
    find(A[key], value)

print(*ans)

# print(counter)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
N, Q = (int(x) for x in input().split())
 
dic = {}
for i in range(N) :
    dic[i+1] = []
 
for i in range(N-1) :
    a, b = (int(x) for x in input().split())
    dic[a].append(b)
    for n in dic.keys() :
        if a in dic[n] :
            dic[n].append(b)
 
SUM = [0]*n #np.zeros(N, dtype=np.int)
 
for i in range(Q) :
    p, x = (int(x) for x in input().split())
    SUM[p-1] = SUM[p-1] + x
    for n in dic[p] :
        SUM[n-1] = SUM[n-1] + x
 
print(' '.join(map(str, SUM)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, Q = map(int, input().split())
T = [[0, deque(), deque()] for _ in range(N+1)] #counter, parents, children
E = [list(map(int, input().split())) for _ in range(N-1)]
for e in E:
  p, c = e
  T[c][1] += T[p][1]
  T[c][1].append(p)
  for q in T[c][1]:
    T[q][2].append(c)
for _ in range(Q):
  p, x = map(int, input().split())
  T[p][0] += x
  for c in T[p][2]:
    T[c][0] += x
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200005)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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

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

ans = [0] * (n+1)

def dfs(cur, pre):
    global ps, ans, g
    ans[cur] = ans[pre] + ps[cur]
    for e in g[cur]:
        if e != pre:
            dfs(e, cur)

dfs(0, -1)

print(" ".join(map(str, ans[0:-1])))

Submission status: Time Limit Exceeded

Solution code:
n , q = map(int, input().split())

tree = {}
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

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

for root in tree.keys():
    for i in tree[root]:
        op[i] += op[root]

print(*op.values())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] += xi
sp = [0 for i in range(n)]
s = [0]
visited = [False for i in range(n)]
while len(s) > 0:
    x = s.pop(0)
    visited[x] = True
    sp[x] += px[x]
    for xc in d[x]:
        if not visited[xc]:
            s.append(xc)
            sp[xc] += sp[x]
for i in range(n):
    print(sp[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N,Q=map(int,input().split())
l=[ tuple( map(int,input().split()) ) for i in range(N-1) ]
p_l=[ tuple( map(int,input().split()) ) for i in range(Q) ]
d=defaultdict(list)

for f,g in l:
    d[f].append(g)

d_2=defaultdict(int)
for p,x in p_l:
    d_2[p]+=x

for n in range(1,N+1):
    d_2[n]+=0
    for m in d[n]:
        d_2[m]+=d_2[n]

print(*d_2.values())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200005)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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

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

ans = [0] * n

def dfs(cur, pre, curv):
    global ps, ans, g
    curv += ps[cur]
    ans[cur] = curv
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, curv)

dfs(0, -1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
T = [[0, [], []] for _ in range(N+1)] #counter, parents, children
E = [list(map(int, input().split())) for _ in range(N-1)]
for e in E:
  p, c = e
  T[c][1] += T[p][1]
  T[c][1].append(p)
  for q in T[c][1]:
    T[q][2].append(c)
for _ in range(Q):
  p, x = map(int, input().split())
  T[p][0] += x
  for c in T[p][2]:
    T[c][0] += x
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}

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

SUM = np.zeros(N, dtype=np.int)

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

for i in range(N-1) :
    SUM[i+1] += SUM[dic.get(i+2)-1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5 * 10**5)
input=sys.stdin.readline
 
N, Q = list(map(int, input().split()))
 
M = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    M[a-1].append(b-1)
    M[b-1].append(a-1)
 
X = [0] * N
for _ in range(Q):
    p, x = list(map(int, input().split()))
    X[p-1] += x
 
ans = [0] * N
 
def setAnswer(parent, number, value):
    ans[number] = value
 
    for i in M[number]:
        if i != parent:
            setAnswer(number, i, value + X[i])
 
setAnswer(0, 0, X[0])
 
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
T = [[0, [], []] for _ in range(N+1)] #counter, parents, children
E = sorted([list(map(int, input().split())) for _ in range(N-1)], key=lambda x:x[0])
for e in E:
  p, c = e
  T[c][1] += T[p][1]
  T[c][1].append(p)
  for q in T[c][1]:
    T[q][2].append(c)
for _ in range(Q):
  p, x = map(int, input().split())
  T[p][0] += x
  for c in T[p][2]:
    T[c][0] += x
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)

Submission status: Time Limit Exceeded

Solution code:
num=input().split( )
num=[int(n) for n in num]
N=num[0]
Q=num[1]

a=[]
b=[]
for i in range(N-1):
    num=input().split( )
    num=[int(n) for n in num]
    a.append(num[0])
    b.append(num[1])

counter=[0]*N
def addCounter(p, q):
    index=[i for i, j in enumerate(a) if j == p]
    for i in index:
        addCounter(b[i], q)
    counter[p-1]=counter[p-1] +q

for i in range(Q):
    num=input().split( )
    num=[int(n) for n in num]
    addCounter(num[0], num[1])

print(*counter)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
ab = {}
pq = {}
for i in range(N-1):
  arr = input().split()
  if not arr[0] in ab:
    ab[arr[0]] = []
  ab[arr[0]].append(arr[1])
for i in range(Q):
  arr = input().split()
  if not arr[0] in pq:
    pq[arr[0]] = 0
  pq[arr[0]] += int(arr[1])

ans = [0] * (N + 1)
que = ['1']
while len(que) > 0:
  n = str(que.pop(0))
  if n in pq:
    ans[int(n)] += int(pq[n])
  if n in ab:
    for i in range(len(ab[n])):
      j = int(ab[n][i])
      ans[j] += ans[int(n)]
      que.append(str(j))
ans.pop(0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = {}
for i in range(n-1):
    ai, bi = map(int,input().split())
    if ai-1 in d:
        d[ai-1] += [bi-1]
    else:
        d[ai-1] = [bi-1]
    if bi-1 in d:
        d[bi-1] += [ai-1]
    else:
        d[bi-1] = [ai-1]
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] += xi
sp = [0 for i in range(n)]
s = [[0,0]]
while len(s) > 0:
    x = s.pop(0)
    sp[x[0]] += px[x[0]]
    for xc in d[x[0]]:
        if xc != x[1]:
            s.append([xc,x[0]])
            sp[xc] += sp[x[0]]
for i in range(n):
    print(sp[i])

Submission status: Time Limit Exceeded

Solution code:
def solve(N, Q, ABs, PXs):
    values = {i: 0 for i in range(N + 1)}
    ans = [-1 for i in range(N + 1)]
    vertexes = {}
    for a, b in ABs:
        vertexes.setdefault(a, []).append(b)
        vertexes.setdefault(b, []).append(a)

    for p, x in PXs:
        values[p] += x

    queue = []
    queue.append((1, 0))
    while queue:
        index, parent_value = queue.pop()
        value = parent_value + values[index]
        ans[index] = value
        for child in vertexes[index]:
            if ans[child] == -1:
                queue.append((child, value))
    return " ".join([str(a) for a in ans[1:]])


if __name__ == "__main__":
    N, Q = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    PXs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, Q, ABs, PXs))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
PX = [list(map(int,input().split())) for _ in [0]*Q]

E = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)

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

q = [0]
done = [False]*N
while q:
    i = q.pop()
    done[i] = True
    for j in E[i]:
        if done[j] : continue
        V[j] += V[i]
        q.append(j)

print(*V)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}
#for i in range(N) :
#    dic[i+1] = []

for i in range(N-1) :
    a, b = (int(x) for x in input().split())
    #dic[a].append(b)
    #dic[b].append(a)
    dic[b] = a
    #for n in dic.keys() :
    #    if a in dic[n] :
    #        dic[n].append(b)

SUM = np.zeros(N, dtype=np.int)

for i in range(Q) :
    p, x = (int(x) for x in input().split())
    SUM[p-1] = SUM[p-1] + x
    #for n in dic[p] :
    #    SUM[n-1] = SUM[n-1] + x

for i in range(N-1) :
    SUM[i+1] += SUM[dic.get(i+2)-1]

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

Submission status: Time Limit Exceeded

Solution code:

N,Q=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PQ = [list(map(int,input().split())) for _ in range(Q)]
AB.sort()
PQ.sort()
l=[[] for _ in range(N)]
ans=[0]*N
for a,b in AB:
	l[a-1].append(b-1)
for p,q in PQ:
	ans[p-1]+=q
for i in range(N-1):
	for j in l[i]:
		ans[j]+=ans[i]
	
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict,deque


## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
stk = deque([0])
cost = [-1 for _ in range(N)]
cost[0] = cnt[0]
while len(stk) > 0:
  p = stk.pop()
  for q in route[p]:
    if cost[q] >= 0:
      continue
    cost[q] = cost[p] + cnt[q]
    stk.append(q)

print(*cost)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000000)

N, Q = [int(x) for x in input().split()]
# V = [set() for _ in range(N)]
V = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    # V[a].add(b)
    V[a].append(b)

C = [0] * N

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

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


def main():
    dfs(0, 0)
    print(" ".join([str(x) for x in ANS]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())

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


a_s = sorted(a)
b_s = sorted(b)
ans= [ 0 for _ in range(N)]


for i in range(Q):
    ans[b_s[i][0]-1] += b_s[i][1]

for i in range(N-1):
    ans[a_s[i][1]-1] += ans[a_s[i][0]-1]
    print(ans[i],end=" ")
print(ans[N-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import*
M=lambda:map(int,input().split())
n,q=M()
s=[[]for _ in range(n)]
for i in range(n-1):
  a,b=M()
  s[a-1].append(b-1)
  s[b-1].append(a-1)
p=[0]*n
for i in range(q):
  a,b=M()
  p[a-1]+=b
v=[1]+[0]*(n-1)
d=deque([(0,0)])
while d:
  b,c=d.popleft()
  c+=p[b]
  p[b]=c
  for i in s[b]:
    if v[i]:continue
    v[i]=1
    d.append((i,c))
print(*p)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

V = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    V[a].add(b)

C = [0] * N

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

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


def main():
    dfs(0, 0)
    print(" ".join([str(x) for x in ANS]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5 * 10**5)
 
N, Q = list(map(int, input().split()))
 
M = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    M[a-1].append(b-1)
    M[b-1].append(a-1)
 
ans = [0] * N
for _ in range(Q):
    p, x = list(map(int, input().split()))
    ans[p-1] += x
 
def setAnswer(parent, number):
    ans[number] += ans[parent]
 
    for i in M[number]:
        if i != parent:
            setAnswer(number, i)

ans.append(0)
setAnswer(N, 0)
ans.pop(N)
 
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)]
 
neigh = {}
 
scores = [0] * n
 
for i in range(q) :
    scores[px[i][0] - 1] += px[i][1]
#print(*scores) 
for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])
#print(neigh)

for k in sorted(neigh.keys()):
    for e in neigh[k]:
        scores[e-1]+=scores[k-1]
 
print(*scores)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

V = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    V[a].add(b)

C = [0] * N

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

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


def main():
    dfs(0, 0)
    print(" ".join([str(x) for x in ANS]))

if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

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

for i in range(N-1):
    new_a, new_b = map(int, input().split())
    tmp_branch = branch_list[new_a-1]
    tmp_branch.append(new_b)
    branch_list.pop(new_a-1)
    branch_list.insert(new_a-1, tmp_branch)

score_list = []
for i in range(N):
    score_list.append(0)

def branch_adder(p, x):
    p_branch = branch_list[p-1]
    score_list[p-1] += x
    for i in range(len(p_branch)):
        branch_adder(p_branch[i], x)

for i in range(Q):
    new_p, new_x = map(int, input().split())
    branch_adder(new_p, new_x)

for i in range(N):
    print(score_list[i], end=' ')

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, q = map(int, input().split())
    ab = sorted(list(list(map(int, input().split())) for _ in range(n - 1)))
    px = list(list(map(int, input().split())) for _ in range(q))
    counters = [0] * (n + 1)
    for p, x in px:
        counters[p] += x
    for i in range(2, n + 1):
        parent = list(filter(lambda x: x[1] == i, ab))[0][0]
        counters[i] += counters[parent]
    print(" ".join([str(c) for c in counters[1:]]))


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
d = {}
ans = [0]*(n+1)
for i in range(n-1):
    sta,gol = map(int,input().split())
    d[gol] = sta

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

for i in range(n):
    gol = i+1
    if gol in d:
        ans[gol]+=ans[d[gol]]
    

anss = ""
for i in range(n):
    anss = anss+str(ans[i+1])+" "
print(anss)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**5)
def parent(array,count,index,root):
    array[index-1].remove(root)
    count[index-1]+=count[root-1]
    for i in array[index-1]:
        parent(array,count,i,index)
num,q=map(int,input().split())
counter=[0 for _ in range(num)]
roots=[set() for _ in range(num)]
for _ in range(num-1):
    a,b=map(int,input().split())
    roots[a-1].add(b)
    roots[b-1].add(a)
for _ in range(q):
    p,x=map(int,input().split())
    counter[p-1]+=x
for ele in roots[0]:
    parent(roots,counter,ele,1)
print(" ".join([str(counter[i]) for i in range(num)]))

Submission status: Time Limit Exceeded

Solution code:
n , q = map(int, input().split())

tree = {}
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

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

for node in op.keys():
    if node in tree:
        for i in tree[node]:
            op[i] += op[node]

print(*op.values())

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n-1)])
px = [list(map(int, input().split())) for i in range(q)]
p = [0 for i in range(n)]
for i in px:
  p[i[0] - 1] += i[1]
s = ""
for i in ab:
  p[i[1]-1] += p[i[0]-1]
print(" ".join(map(str, p)))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(100000000)

n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

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

def dfs(x, v):
	ans[x] = ws[x] + v
	if len(ds[x]) > 0:
		for nxt in ds[x]:
			dfs(nxt, ans[x])

dfs(0, 0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5 * 10**5)
 
N, Q = list(map(int, input().split()))
 
M = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    M[a-1].append(b-1)
    M[b-1].append(a-1)
 
X = [0] * N
for _ in range(Q):
    p, x = list(map(int, input().split()))
    X[p-1] += x
 
ans = [0] * N
 
def setAnswer(parent, number, value):
    ans[number] = value
 
    for i in M[number]:
        if i != parent:
            setAnswer(number, i, value + X[i])
 
setAnswer(0, 0, X[0])
 
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

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


N, Q = map(int, input().split())
T = [[0, []] for _ in range(N+1)] #counter, nearest-children
E = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
for e in E:
  T[e[0]][1].append(e[1])
for px in PX:
  T[px[0]][0] += px[1]
for t in T:
  for c in t[1]:
    T[c][0] += t[0]
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)