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
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

N, Q = map(int, input().split())
info = [[] for _ in range(N)]
ans = [0 for _ in range(N)]

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


def checker(n, info2):
    for i in info[n]:
        if n in info2[i]:
            continue
        else:
            info2[n].append(i)
            checker(i, info2)


def plus(n, val):
    ans[n] += val
    for i in info2[n]:
        plus(i, val + Query[i])


info2 = [[] for _ in range(N)]
checker(0, info2)
Query = [0 for _ in range(N)]
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p - 1] += x
plus(0, Query[0])
ans = list(map(str, ans))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

N, Q = map(int, input().split())
info = [[] for _ in range(N)]
ans = [0 for _ in range(N)]

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


def checker(n):
    for i in info[n]:
        if n in info[i]:
            del info[i][info[i].index(n)]
        checker(i)


def plus(n, val):
    ans[n] += val
    for i in info[n]:
        plus(i, val + Query[i])


checker(0)
Query = [0 for _ in range(N)]
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p - 1] += x
plus(0, Query[0])
ans = list(map(str, ans))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,Q = list(map(int,input().split()))
    edges = [[] for i in range(N+1)]
    for i in range(N-1):
        a,b = list(map(int,input().split()))
        edges[a].append(b)
        edges[b].append(a)

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

    stack = [(1,0)]
    ans = [0]*(N+1)
    not_checked = [True]*(N+1)
    while stack:
        v,cnt = stack.pop()
        ans[v] = cnt+add[v]
        not_checked[v] = False
        for edge in edges[v]:
            if not_checked[edge]:
                stack.append((edge,ans[v]))

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import queue
        
N, Q = map(int, input().rstrip().split())
e = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(N-1)]
q = [list(map(int, input().rstrip().split())) for _ in range(Q)]

v2e = [set() for _ in range(N)]
for a, b in e:
    v2e[a].add(b)
    v2e[b].add(a)

v = [0] * N
for i in range(Q):
    v[q[i][0]-1] += q[i][1]
    
que = queue.Queue()
que.put((0, 0))
f = [False] * N
f[0] = True
while que.qsize() > 0:
    a, b = que.get()
    v[a] += b
    for c in v2e[a]:
        if f[c] == False:
            que.put((c, v[a]))
            f[c] = True
            
print(' '.join(list(map(str, v))))

Submission status: Time Limit Exceeded

Solution code:
N,Q = list(map(int,input().split()))
edges = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    edges[a].append(b)
    edges[b].append(a)

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

stack = [(1,0)]
ans = [0]*(N+1)
not_checked = [True]*(N+1)
while stack:
    v,cnt = stack.pop()
    ans[v] = cnt+add[v]
    not_checked[v] = False
    for edge in edges[v]:
        if not_checked[edge]:
            stack.append((edge,ans[v]))

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import queue
        
N, Q = map(int, input().rstrip().split())
e = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(N-1)]
q = [list(map(int, input().rstrip().split())) for _ in range(Q)]

v2e = [set() for _ in range(N)]
for a, b in e:
    v2e[a].add(b)
    v2e[b].add(a)

v = [0] * N
for i in range(Q):
    v[q[i][0]-1] += q[i][1]
    
que = queue.Queue()
que.put((0, 0))
f = [False] * N
f[0] = True
while que.qsize() > 0:
    a, b = que.get()
    v[a] += b
    for c in v2e[a]:
        if f[c] == False:
            que.put((c, v[a]))
            f[a] = True
            
print(' '.join(list(map(str, v))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
n,q=map(int,input().split())
g=[deque([]) for i in range(n)]
for _ 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 _ in range(q):
    a,b=map(int,input().split())
    add[a-1]+=b
st=set()  ; ans=[0]*n ; stack=[[0,add[0]]]
while stack:
    s=stack[-1]
    if s[0] not in st : 
        st.add(s[0])
        ans[s[0]]+=s[1]
    if not g[s[0]] : 
        stack.pop()
        continue
    while g[s[0]]:
        if g[s[0]][0] in st:
            g[s[0]].popleft()
        else:
            stack.append([g[s[0]][0],s[1]+add[g[s[0]][0]]])
            break
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
n,q=map(int,input().split())
g=[[] for i in range(n)]
for _ 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 _ in range(q):
    a,b=map(int,input().split())
    add[a-1]+=b
st=set() ; v=0 ; s=add[0]
ans=[0]*n
def dfs(g,v,s):
    global ans,st
    if v not in st:
        st.add(v)
        ans[v]+=s
    else: return
    for p in g[v]:
        dfs(g,p,s+add[p])
dfs(g,v,s)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, q = map(int, input().split())
node = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  node[a-1].append([a-1, b-1])
  node[b-1].append([b-1, a-1])

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

already = [False]*n
not_yet = deque(node[0])
already[0] = True
for i in not_yet:
  already[i[1]] = True
while not_yet:
  key = not_yet.popleft()
  a, b = key[0], key[1]
  already[b] = True
  ans[b] += ans[a]
  for i in range(len(node[b])):
    p, q = node[b][i][0], node[b][i][1]
    if already[q]:
      continue
    not_yet.append(node[b][i])
    already[q] = True
  
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, q = map(int, input().split())
node = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  node[a-1].append([a-1, b-1])
  node[b-1].append([b-1, a-1])

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

already = [[False]*n for i in range(n)]
not_yet = deque(node[0])
for k in not_yet:
  a, b = k[0], k[1]
  already[a][b] = True
  already[b][a] = True
while not_yet:
  key = not_yet.popleft()
  a, b = key[0], key[1]
  ans[b] += ans[a]
  for i in range(len(node[b])):
    p, q = node[b][i][0], node[b][i][1]
    if already[p][q] or already[p][q]:
      continue
    not_yet.append(node[b][i])
    already[p][q] = True
    already[q][p] = True
  
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

# Nがノードの数, Qが操作回数
N, Q = map(int, input().split())

points = [0] * N
nodes = [set() for _ in range(N)]
parents = [-1] * N

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

def fill_parent(parent, n):
  global parents, nodes
  parents[n] = parent
  if parent in nodes[n] and len(nodes[n]) == 1:
    return
  for i in nodes[n]:
    if i != parent:
      fill_parent(n, i)

for i in nodes[0]:
  fill_parent(0, i)

h = {}
for i in range(N):
  if parents[i] not in h:
    h[parents[i]] = set()
  h[parents[i]].add(i)

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

c = [0] * N

def calc(n):
  if n == 0:
    c[n] = points[n]
  else:
    c[n] = points[n] + c[parents[n]]
  if n in h:
    for i in h[n]:
      calc(i)

calc(0)
print(*c)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

N, Q = map(int,input().split())
edge = [[] for i in range(N+1)]

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

cnt = [0 for i in range(N+1)]

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

def dfs(parent,i,add):
    for k in edge[i]:
        if k != parent:
            cnt[k] += add
            dfs(i,k,cnt[k])
    

dfs(-1,1,cnt[1])

ans = cnt[1:]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

N, Q = map(int,input().split())
edge = [[]] * (N+1)

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

cnt = [0] * (N+1)

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

def dfs(parent,i):
    for k in edge[i]:
        if k != parent:
            cnt[k] += cnt[i]
            dfs(i,k)
    

dfs(-1,1)

ans = cnt[1:]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

N, Q = map(int,input().split())
edge = [[] for i in range(N+1)]

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

cnt = [0 for i in range(N+1)]

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

def dfs(parent,i):
    for k in edge[i]:
        if k != parent:
            cnt[k] += cnt[i]
            dfs(i,k)
    return

dfs(-1,1)

ans = cnt[1:]

print(*ans)

Submission status: Time Limit Exceeded

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

N,Q = map(int,input().split())
graph = [[] for i in range(N)]

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

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

notv = [True]*N
notv[0] = False
stack = [0]

while stack:
    now = stack.pop(0)
    for i in graph[now]:
        if notv[i]:
            notv[i] = False
            stack.append(i)
            v[i] += v[now]

print(*v)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

N, Q = map(int,input().split())
edge = [[] for i in range(N+1)]

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

cnt = [0 for i in range(N+1)]

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

def dfs(parent,i):
    for k in edge[i]:
        if k != parent:
            cnt[k] += cnt[i]
            dfs(i,k)

dfs(-1,1)

ans = cnt[1:]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

N, Q = map(int,input().split())
edge = [[] for i in range(N+1)]

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

children = [[] for i in range(N+1)]

def dfs(parent,i):
    for k in edge[i]:
        if parent != k:
            children[i].append(k)
            dfs(i,k)
        
dfs(-1,1)

cnt = [0 for i in range(N+1)]

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

def dfs_solve(i):
    for k in children[i]:
        cnt[k] += cnt[i]
        dfs_solve(k)

dfs_solve(1)

ans = cnt[1:]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

N, Q = map(int,input().split())
edge = [[] for i in range(N+1)]

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

subtree = [[] for i in range(N+1)]

def dfs(parent,i):
    if [parent] == edge[i]:
        subtree[i].append(i)
        return subtree[i]
    for k in edge[i]:
        if k != parent:
            subtree[i].extend(dfs(i,k))
    subtree[i].append(i)
    return subtree[i]
        
dfs(-1,1)

ans = [0 for i in range(N)]

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

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# 深さ優先探索の問題
import numpy as np
import sys

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

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

# 隣接リスト
t = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = [int(i) for i in readline().split()]
    t[a-1].append(b-1)
    t[b-1].append(a-1)

# スコア
s = [0] * N
for _ in range(Q):
    p, x = [int(i) for i in readline().split()]
    #s[p-1] = s[p-1] + x
    s[p-1] += x

ans = [0] * N

# 深さ優先探索
def dfs(v, p, value):
    #value = value + s[v]
    value += s[v]
    #ans[v] = ans[v] + value
    ans[v] += value
    for c in t[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

print(*ans)

Submission status: Time Limit Exceeded

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

N,Q=map(int,input().split())
cnt=[0]*(N+1)
ans=[0]*(N+1)
Graph=[[] 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):
    v,x=map(int,input().split())
    cnt[v]+=x

def dfs(Graph,v,x,p):
    global ans
    ans[v]=x
    for nv in Graph[v]:
        if nv==p:
            continue
        nx=x+cnt[nv]
        dfs(Graph,nv,nx,v)

dfs(Graph,1,cnt[1],-1)
ans=[str(ans[i]) for i in range(1,N+1)]
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
# =============================================================================
#　ABC138D Ki
# =============================================================================
import sys
sys.setrecursionlimit(10**8)

N,Q=map(int,input().split())
cnt=[0]*(N+1)
ans=[0]*(N+1)
Graph=[[] 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):
    v,x=map(int,input().split())
    cnt[v]+=x

def dfs(Graph,v,x,p):
    global ans
    ans[v]=x
    for nv in Graph[v]:
        if nv==p:
            continue
        nx=x+cnt[nv]
        dfs(Graph,nv,nx,v)

dfs(Graph,1,cnt[1],-1)
ans=[str(ans[i]) for i in range(1,N+1)]
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        fx = f[x]
        for y in v[x]:
            if d[y]:
                d[y] = 0
                f[y] += fx
                dfs(y)
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    d = [1]*n
    d[0] = 0
    dfs(0)
    print(*f,sep=" ")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class Tree:
    def __init__(self, n, init_list, root=1):
        self.num = (n + 1)
        self.parents = [-1] * self.num
        self.first_child = [-1] * self.num
        self.next_child = [-1] * self.num
        self.check = [-1] * self.num
        self.g = {i: [] for i in range(1, self.num)}
        self.make_g(init_list, root)

    def make_g(self, con, root):
        m = len(con)
        for i in range(m):
            self.g[con[i][0]].append(con[i][1])
            self.g[con[i][1]].append(con[i][0])
        q = deque([root])
        while q:
            node = q.pop()
            self.check[node] = 1
            cnt = 0
            for i, sub_node in enumerate(self.g[node]):
                if self.check[sub_node] != -1:
                    continue
                if cnt == 0:
                    self.first_child[node] = sub_node
                self.parents[sub_node] = node
                if i != len(self.g[node])-1:
                    self.next_child[sub_node] = self.g[node][i+1]
                q.append(sub_node)
                cnt += 1

    def childs(self, node):
        child_list = []
        if self.first_child[node] != -1:
            child_list.append(self.first_child[node])
            node = self.first_child[node]
            while 1:
                if self.next_child[node] == -1:
                    break
                else:
                    child_list.append(self.next_child[node])
                node = self.next_child[node]
        return child_list

    def parent(self, n):
        return self.parents[n]


import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

tr = Tree(N, AB)
# 800ms

q = deque()
q.extend(tr.childs(1))
while q:
    node = q.pop()
    V[node] += V[tr.parent(node)]
    tmp = tr.childs(node)
    if tmp:
        q.extendleft(tmp)

print(*V[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class Tree:
    def __init__(self, n, init_list, root=1):
        self.num = (n + 1)
        self.parents = [-1] * self.num
        self.first_child = [-1] * self.num
        self.next_child = [-1] * self.num
        self.check = [-1] * self.num
        self.g = {i: [] for i in range(1, self.num)}
        self.make_g(init_list, root)

    def make_g(self, con, root):
        m = len(con)
        for i in range(m):
            self.g[con[i][0]].append(con[i][1])
            self.g[con[i][1]].append(con[i][0])
        q = deque([root])
        while q != deque():
            node = q.pop()
            self.check[node] = 1
            cnt = 0
            for i, sub_node in enumerate(self.g[node]):
                if self.check[sub_node] != -1:
                    continue
                if cnt == 0:
                    self.first_child[node] = sub_node
                self.parents[sub_node] = node
                if i != len(self.g[node])-1:
                    self.next_child[sub_node] = self.g[node][i+1]
                q.append(sub_node)
                cnt += 1

    def childs(self, node):
        child_list = []
        if self.first_child[node] != -1:
            child_list.append(self.first_child[node])
            node = self.first_child[node]
            while 1:
                if self.next_child[node] == -1:
                    break
                else:
                    child_list.append(self.next_child[node])
                node = self.next_child[node]
        return child_list

    def parent(self, n):
        return self.parents[n]

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

tr = Tree(N, AB)
# 800ms

q = deque()
q.extend(tr.childs(1))
while q:
    node = q.pop()
    V[node] += V[tr.parent(node)]
    tmp = tr.childs(node)
    if tmp:
        q.extend(tmp)

print(*V[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

class Tree:
    def __init__(self, n, init_list, root=1):
        self.num = (n + 1)
        self.parents = [-1] * self.num
        self.first_child = [-1] * self.num
        self.next_child = [-1] * self.num
        self.check = [-1] * self.num
        self.g = {i: [] for i in range(1, self.num)}
        self.make_g(init_list, root)

    def make_g(self, con, root):
        m = len(con)
        for i in range(m):
            self.g[con[i][0]].append(con[i][1])
            self.g[con[i][1]].append(con[i][0])
        q = deque([root])
        while q != deque():
            node = q.pop()
            self.check[node] = 1
            cnt = 0
            for i, sub_node in enumerate(self.g[node]):
                if self.check[sub_node] != -1:
                    continue
                if cnt == 0:
                    self.first_child[node] = sub_node
                self.parents[sub_node] = node
                if i != len(self.g[node])-1:
                    self.next_child[sub_node] = self.g[node][i+1]
                q.append(sub_node)
                cnt += 1

    def childs(self, node):
        child_list = []
        if self.first_child[node] != -1:
            child_list.append(self.first_child[node])
            node = self.first_child[node]
            while 1:
                if self.next_child[node] == -1:
                    break
                else:
                    child_list.append(self.next_child[node])
                node = self.next_child[node]
        return child_list

    def parent(self, n):
        return self.parents[n]

input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

tr = Tree(N, AB)

q = deque()
q.extend(tr.childs(1))
while q != deque():
    node = q.pop()
    V[node] += V[tr.parent(node)]
    if tr.childs(node):
        q.extend(tr.childs(node))

print(*V[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class Tree:
    def __init__(self, n, init_list, root=1):
        self.num = (n + 1)
        self.parents = [-1] * self.num
        self.first_child = [-1] * self.num
        self.next_child = [-1] * self.num
        self.check = [-1] * self.num
        self.g = {i: [] for i in range(1, self.num)}
        self.make_g(init_list, root)

    def make_g(self, con, root):
        m = len(con)
        for i in range(m):
            self.g[con[i][0]].append(con[i][1])
            self.g[con[i][1]].append(con[i][0])
        q = deque([root])
        while q != deque():
            node = q.pop()
            self.check[node] = 1
            cnt = 0
            for i, sub_node in enumerate(self.g[node]):
                if self.check[sub_node] != -1:
                    continue
                if cnt == 0:
                    self.first_child[node] = sub_node
                self.parents[sub_node] = node
                if i != len(self.g[node])-1:
                    self.next_child[sub_node] = self.g[node][i+1]
                q.append(sub_node)
                cnt += 1

    def childs(self, node):
        child_list = []
        if self.first_child[node] != -1:
            child_list.append(self.first_child[node])
            node = self.first_child[node]
            while 1:
                if self.next_child[node] == -1:
                    break
                else:
                    child_list.append(self.next_child[node])
                node = self.next_child[node]
        return child_list

    def parent(self, n):
        return self.parents[n]


N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

tr = Tree(N, AB)

q = deque()
q.extend(tr.childs(1))
while q != deque():
    node = q.pop()
    V[node] += V[tr.parent(node)]
    if tr.childs(node) != []:
        q.extend(tr.childs(node))

print(*V[1:])

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
tree = [[] for _ in range(N+1)]
ans = [0 for _ in range(N+1)]

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

def main():

    AB = [list(map(int,input().split())) for _ in range(N-1)]
    AB.sort()

    for a,b in AB:
        tree[a].append(b)
        tree[b].append(a)
    # print(tree)

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

'''
#import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
#sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]

def main():
'''

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)
#print(G)

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

def dfs(v, pv):
    for nv in G[v]:
        if nv != pv:
            P[nv] += P[v]
            dfs(nv, v)


dfs(0, 0)
print(*P)


'''
if __name__ == '__main__':
    main()
'''

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]

'''
def main():
'''
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)
#print(G)

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

def dfs(v, pv):
    for nv in G[v]:
        if nv != pv:
            P[nv] += P[v]
            dfs(nv, v)


dfs(0, 0)
print(*P)


'''
if __name__ == '__main__':
    main()
'''