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


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [list() for i in range(N+1)]
    PX = list()
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def dfs(parent, G, C, V):
    V[parent] = True
    for child in G[parent]:
        if not V[child]:
            C[child] += C[parent]
            dfs(child, G, C, V)
    

def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [False for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    dfs(1, G, C, V)
    return ' '.join(map(str, C[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Time Limit Exceeded

Solution code:
import queue

class Tree:
    def __init__(self, ind):
        self.children = []
        self.counter = 0
        self.index = ind
        self.parent = -1


N, Q = map(int, input().split(" "))
tree = [Tree(i) for i in range(N)]
ans = [0 for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    tree[a - 1].children.append(b - 1)
    tree[b - 1].children.append(a - 1)

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

# bfs
que = queue.Queue()
que.put(0)  # root is 0

while not que.empty():
    ind = que.get()
    ans[ind] = tree[ind].counter
    for child in tree[ind].children:
        if child == tree[ind].parent:
            continue
        tree[child].counter += tree[ind].counter
        tree[child].parent = ind
        que.put(child)

print(' '.join([str(a) for a in ans]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,q = map(int,input().split())
ki = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
cnt = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    p -= 1
    cnt[p] += x

def dfs(cur,prev = -1):
    for nxt in ki[cur]:
        if nxt == prev: continue
        cnt[nxt] += cnt[cur]
        dfs(nxt,cur)

dfs(0)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,q = map(int,input().split())
ki = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
cnt = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    p -= 1
    cnt[p] += x

def dfs(cur,prev = -1):
    for nxt in ki[cur]:
        if nxt == prev: continue
        cnt[nxt] += cnt[cur]
        dfs(nxt,cur)

dfs(0)
print(" ".join(map(str,cnt)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n , q = map(int,input().split())
point = [0] * n
edge = [[] for i in range(n)]

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

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

def dfs(now, last=-1):
    for nxt in edge[now]:
        if nxt==last: continue
        point[nxt] += point[now]
        dfs(nxt, now)
dfs(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
N, Q=map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
T=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  T[a-1].append(b-1)
  T[b-1].append(a-1)
P=[0]*N
ans=[0]*N
for i in range(Q):
  p,x=map(int, input().split())
  P[p-1]+=x

def dfs(start, pre_node, pre_val):
  now_val=(pre_val+P[start])
  ans[start]=now_val
  
  for next_node in T[start]:
    if next_node==pre_node:
      continue
    dfs(next_node, start,now_val)
    
dfs(0,-1,0)   
for a in ans:
  print(a, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque



def read():
    N, Q = list(map(int, input().strip().split()))
    G = [list() for i in range(N+1)]
    PX = list()
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [0 for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    depth = [-1 for i in range(N+1)]
    parents = [-1 for i in range(N+1)]
    q = deque()
    q.append(1)
    depth[1] = 0
    parents[1] = 0
    while len(q) > 0:
        node = q.pop()
        for neighbor in G[node]:
            if depth[neighbor] < 0:
                depth[neighbor] = depth[node] + 1
                parents[neighbor] = node
                q.append(neighbor)
    order = np.argsort(depth[1:]) + 1
    V[1] = C[1]
    for i in order:
        child = i
        parent = parents[i]
        V[child] = V[parent] + C[child]
    return ' '.join(map(str, V[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque



def read():
    N, Q = list(map(int, input().strip().split()))
    G = [list() for i in range(N+1)]
    PX = list()
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [0 for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    depth = [-1 for i in range(N+1)]
    q = deque()
    q.append(1)
    depth[1] = 0
    while len(q) > 0:
        node = q.pop()
        for neighbor in G[node]:
            if depth[neighbor] < 0:
                depth[neighbor] = depth[node] + 1
                q.append(neighbor)
    order = np.argsort(depth[1:])
    V[1] = C[1]
    for node in np.arange(1, N+1)[order]:
        for neighbor in G[node]:
            if depth[neighbor] < depth[node]:
                parent = neighbor
                V[node] = V[parent] + C[node]
    return ' '.join(map(str, V[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [i for i in range(N+1)]
    PX = list()
    G[1] = 0  # 終点
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[b] = a  # 逆辺を張る
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [-1 for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    for i in range(N, 0, -1):
        node = i
        v = 0
        while node > 0:
            if V[node] >= 0:  # use cache
                v += V[node]
                break
            v += C[node]
            node = G[node]
        V[i] = v
    return ' '.join(map(str, V[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [i for i in range(N+1)]
    PX = list()
    G[1] = 0  # 終点
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[b] = a  # 逆辺を張る
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [-1 for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    for i in range(N, 0, -1):
        node = i
        v = 0
        while node > 0:
            if V[node] > 0:  # use cache
                v += V[node]
                break
            v += C[node]
            node = G[node]
        V[i] = v
    return ' '.join(map(str, V[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [i for i in range(N+1)]
    PX = list()
    G[1] = 0  # 終点
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[b] = a  # 逆辺を張る
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX

def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [-1 for i in range(N+1)]
    values = deque()
    for p, x in PX:
        C[p] += x
    for i in range(1, N+1):
        node = i
        v = 0
        while node > 0:
            if V[node] > 0:  # use cache
                v += V[node]
                break
            v += C[node]
            node = G[node]
        V[i] = v 
        values.append(v)
    return ' '.join(map(str, values))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [i for i in range(N+1)]
    PX = list()
    G[1] = 0  # 終点
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[b] = a  # 逆辺を張る
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX

def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    values = deque()
    for p, x in PX:
        C[p] += x
    for i in range(1, N+1):
        node = i
        v = 0
        while node > 0:
            v += C[node]
            node = G[node]
        values.append(v)
    return ' '.join(map(str, values))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,q=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
ans=[0 for _ in range(n)]
def dfs(u,par):
    if par!=-1:
        ans[u]+=ans[par]
    for v in g[u]:
        if v==par:
            continue
        dfs(v,u)
for _ in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
dfs(0,-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

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

c = [0] * n

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

q = queue.Queue()
q.put(0)

find = [False] * n

while not q.empty():
    v = q.get()
    find[v] = True
    for u in es[v]:
        if find[u]:
            continue
        c[u] += c[v]
        q.put(u)

print(*c)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

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

c = [0] * n

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

q = queue.Queue()
q.put(0)

find = [False] * n
find[0] = True

while not q.empty():
    v = q.get()
    for u in es[v]:
        if not find[u]:
            c[u] += c[v]
            find[u] = True
            q.put(u)

print(*c)

Submission status: Time Limit Exceeded

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

def DFS(v, parent):
  global v_count
  for u in adj[v]:
    if u != parent:
      v_count[u] += v_count[v]
      DFS(u,v)

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

adj = [[] for _ in range(N)]
v_count = [0] * N

for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)# aがbの親とは限らないため

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

# 0起点に親ノードの数字を子ノードに足していく
DFS(0, -1)# 現在のノード, 親ノード
print(*v_count)

Submission status: Time Limit Exceeded

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

def DFS(v, parent):
  global v_count
  for u in adj[v]:
    if u != parent:
      v_count[u] += v_count[v]
      DFS(u,v)

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

adj = [[] for _ in range(N)]
v_count = [0] * N

for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)# aがbの親とは限らないため

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

# 0起点に親ノードの数字を子ノードに足していく
DFS(0, -1)# 現在のノード, 親ノード
print(*v_count)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

#全体に同じものを足すときは累積和を考えたい

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

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

for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]
check[1] = True
for p,x in PX:
    counter[p] += x

def bfs(graph,counter,edge):
    que = Queue()
    que.put(edge)
    while not que.empty():
        p = que.get()
        for e in graph[p]:
            if check[e]:
                continue
            counter[e] += counter[p]
            que.put(e)
            check[e] = True

bfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#全体に同じものを足すときは累積和を考えたい

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

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

for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]
check[1] = True
for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if check[e]:
                continue
            counter[e] += counter[p]
            stk.append(e)
            check[e] = True

dfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())

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

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

def dfs(v1, parent, add):
    values[v1] += add
    for v2 in graph[v1]:
        if v2 == parent:
            continue
        dfs(v2, v1, values[v1])


dfs(0, 0, 0)

print(*values)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
graph = [[0]*(n) for _ in range(n)]

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

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

def dfs(v1, parent, add):
    values[v1] += add
    for v2 in range(n):
        if not graph[v1][v2]:
            continue
        if v2 == parent:
            continue
        dfs(v2, v1, values[v1])


dfs(0, 0, 0)

print(*values)

Submission status: Time Limit Exceeded

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

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

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

    def dfs(v=0, p=-1):
        for u in to[v]:
            if u == p:
                continue
            else:
                node[u] = node[u] + node[v]
                dfs(u, v)

    dfs()
    for i in range(n):
        if i == n-1:
            print(node[i])
        else:
            print(node[i], end=' ')
main()

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10**6)
def main():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        to[a].append(b)
        to[b].append(a)

    node = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        node[p] += x  
    def dfs(v, p=-1):
        for u in to[v]:
            if u == p:
                continue
            else:
                node[u] += node[v]
                dfs(u, v)
    dfs(0)
    for i in range(n):
        if i == n-1:
            print(node[i])
        else:
            print(node[i], end=' ')
main()

Submission status: Time Limit Exceeded

Solution code:
#python3
import sys
sys.setrecursionlimit(10**6)
def main():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        to[a].append(b)
        to[b].append(a)

    node = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        node[p] += x  
    def dfs(v, p=-1):
        for u in to[v]:
            if u == p:
                continue
            else:
                node[u] += node[v]
                dfs(u, v)
    dfs(0)
    for i in range(n):
        if i == n-1:
            print(node[i])
        else:
            print(node[i], end=' ')
main()

Submission status: Time Limit Exceeded

Solution code:
#全体に同じものを足すときは累積和を考えたい

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

graph = [set([]) for _ in range(N+1)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]

for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        check[p] = True
        for e in graph[p]:
            if not check[e]:
                counter[e] += counter[p]
                stk.append(e)
                check[e] = True

dfs(graph,counter,1)

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

Submission status: Time Limit Exceeded

Solution code:
#全体に同じものを足すときは累積和を考えたい

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

graph = [set([]) for _ in range(N+1)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]

for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        check[p] = True
        for e in graph[p]:
            if not check[e]:
                counter[e] += counter[p]
                stk.append(e)
                check[e] = True

dfs(graph,counter,1)

counter = counter[1:]
ans = " ".join(map(str,counter))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#全体に同じものを足すときは累積和を考えたい

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

graph = [set([]) for _ in range(N+1)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]

for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        check[p] = True
        for e in graph[p]:
            if not check[e]:
                counter[e] += counter[p]
                stk.append(e)
                check[e] = True

dfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)

Submission status: Time Limit Exceeded

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


def inpl():
    return list(map(int, input().split()))


def bfs():
    visited[0] = True
    ans[0] = counter[0]
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter[nv]
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

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

bfs()

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

Submission status: Time Limit Exceeded

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


def inpl():
    return list(map(int, input().split()))


def bfs():
    visited[0] = True
    ans[0] = counter.get(0, 0)
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter.get(nv, 0)
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

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

bfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def dfs(v=0, c=0):
    visited[v] = True
    c += counter.get(v, 0)
    ans[v] = c
    for nv in edge[v]:
        if visited[nv] is True:
            continue
        dfs(nv, c)
    return


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

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

dfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def dfs(v=0, c=0):
    if visited[v] is True:
        return
    visited[v] = True
    c += counter[v]
    ans[v] = c
    for nv in edge[v]:
        if visited[nv] is True:
            continue
        dfs(nv, c)
    return


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] += q

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

dfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def dfs(v=0, c=0):
    if visited[v] is True:
        return
    visited[v] = True
    c += counter[v]
    ans[v] = c
    for nv in edge[v]:
        dfs(nv, c)
    return


N, Q = inpl()
AB = [inpl() for i in range(N - 1)]
PQ = [inpl() for i in range(Q)]

edge = [[] for i in range(N)]
for a, b in AB:
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
counter = {k: 0 for k in range(N)}
for p, q in PQ:
    counter[p - 1] += q

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

dfs()

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

Submission status: Time Limit Exceeded

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

import sys

def dfs(i, p, add):
    add += add_node[i]
    counter[i] += add
    for j in adj[i]:
        if j != p:
            dfs(j, i, add)

sys.setrecursionlimit(10 ** 6)
n, q = map(int, input().split())
adj = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
add_node = [0 for i in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    add_node[p - 1] += x
counter = [0 for i in range(n)]
dfs(0, -1, 0)
print(" ".join(str(x) for x in counter))

Submission status: Time Limit Exceeded

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

import sys

def dfs(i, p, add):
    add += add_node[i]
    counter[i] += add
    for j in adj[i]:
        if j != p:
            dfs(j, i, add)

sys.setrecursionlimit(10 ** 6)
n, q = map(int, input().split())
adj = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
add_node = [0 for i in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    add_node[p - 1] += x
counter = [0 for i in range(n)]
visited = [False for i in range(n)]
dfs(0, -1, 0)
print(" ".join(str(x) for x in counter))

Submission status: Time Limit Exceeded

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

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n, q = map(int, input().split())
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    add_node = [0 for i in range(n)]
    for i in range(q):
        p, x = map(int, input().split())
        add_node[p - 1] += x
    counter = [0 for i in range(n)]
    visited = [False for i in range(n)]
    dfs(0, adj, visited, counter, 0, add_node)
    print(" ".join(str(x) for x in counter))

def dfs(i, adj, visited, counter, add, add_node):
    visited[i] = True
    add += add_node[i]
    counter[i] += add
    for j in adj[i]:
        if not visited[j]:
            dfs(j, adj, visited, counter, add, add_node)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import deque
import sys

sys.setrecursionlimit(10**6)

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

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

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

ans = [0] * N
def dfs(v, u, counter):
    counter += score[v]
    ans[v] = counter
    for c in Graph[v]:
        if c == u:
            continue
        dfs(c, v, counter)

dfs(0, -1, 0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = [int(x) for x in input().split()]
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = [int(x)-1 for x in input().split()]
    G[a].append(b)
    G[b].append(a)
count = [0]*n
for _ in range(q):
    a,b = [int(x) for x in input().split()]
    a -= 1
    count[a] += b

from collections import deque
ans = [0]*n
q = deque()
used = [0]*n
q.append(0)
used[0]=1
ans[0] += count[0]

while q:
    p = q.popleft()
    for i in G[p]:
        if used[i]!=1:
            used[i]=1
            ans[i]+=ans[p]+count[i]
            q.append(i)

an = ""
for i in ans:
    an += str(i) + " "
print(an)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) #for deep recursion

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

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def dfs(point, pre):
    connected_vertices = all_connected_vertices[point]
    for c in connected_vertices:
        if c == pre:
            continue
        counts[c-1] += counts[point-1]
        dfs(c, point)
    
dfs(1, -1)
    
print(*counts)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = [0] * N
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def get_connected_vertices(v):
    return all_connected_vertices[v]
    
def dfs(point, pre):
    connected_vertices = get_connected_vertices(point)
    children = [v for v in connected_vertices if v != pre]
    for c in children:
        counts[c-1] += counts[point-1]
        dfs(c, point)
    
dfs(1, -1)
    
print(*counts)