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**6)

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

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

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


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


dfs(0, -1)


print(*point)

Submission status: Time Limit Exceeded

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

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

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

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


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


dfs(0, -1)


print(*point)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

for i in range(q):
    pl.append(list(map(int, input().split())))

parent = [-1 for _ in range(n)]
child = [[] for _ in range(n)]
parent[0] = 0
point = [0] * n
que = deque([])


def makeTree():
    global parent, neighbor, child, que
    queue = deque([[0, 0]])
    while len(queue) > 0:
        now = queue.popleft()
        que.append(now[0])
        for neiv in neighbor[now[0]]:
            if parent[neiv] == -1:
                parent[neiv] = now[0]
                queue.append([neiv, now[1]])
                child[now[0]].append(neiv)


def calcPoint():
    global pl, parent, point, que
    for p in pl:
        point[p[0] - 1] += p[1]
    que.popleft()
    for v in que:
        point[v] += point[parent[v]]


makeTree()

calcPoint()

print(*point)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

for i in range(q):
    pl.append(list(map(int, input().split())))

parent = [-1 for _ in range(n)]
child = [[] for _ in range(n)]
parent[0] = 0
point = [0] * n
que = deque([])


def makeTree():
    global parent, neighbor, child
    queue = deque([[0, 0]])
    while len(queue) > 0:
        now = queue.popleft()
        que.append(now[0])
        for neiv in neighbor[now[0]]:
            if parent[neiv] == -1:
                parent[neiv] = now[0]
                queue.append([neiv, now[1]])
                child[now[0]].append(neiv)


def calcPoint():
    global pl, parent, point, que
    for p in pl:
        point[p[0] - 1] += p[1]
    que.popleft()
    while len(que) > 0:
        now = que.popleft()
        point[now] += point[parent[now]]


makeTree()

calcPoint()

print(*point)

Submission status: Time Limit Exceeded

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

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

for i in range(q):
    pl.append(list(map(int, input().split())))

parent = [-1 for _ in range(n)]
child = [[] for _ in range(n)]
parent[0] = 0
point = [0] * n
que = []


def makeTree():
    global parent, neighbor, child
    queue = [[0, 0]]
    while len(queue) > 0:
        now = queue.pop(0)
        que.append(now[0])
        for neiv in neighbor[now[0]]:
            if parent[neiv] == -1:
                parent[neiv] = now[0]
                queue.append([neiv, now[1]])
                child[now[0]].append(neiv)


def calcPoint():
    global pl, parent, point, que
    for p in pl:
        point[p[0] - 1] += p[1]
    que.pop(0)
    while len(que) > 0:
        now = que.pop(0)
        point[now] += point[parent[now]]


makeTree()

calcPoint()

print(*point)

Submission status: Time Limit Exceeded

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

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

for i in range(q):
    pl.append(list(map(int, input().split())))

parent = [-1 for _ in range(n)]
child = [[] for _ in range(n)]
parent[0] = 0
point = [0] * n


def makeTree():
    global parent, neighbor, child
    queue = [[0, 0]]
    while len(queue) > 0:
        now = queue.pop(0)

        for neiv in neighbor[now[0]]:
            if parent[neiv] == -1:
                parent[neiv] = now[0]
                queue.append([neiv, now[1]])
                child[now[0]].append(neiv)


def calcPoint():
    global pl, parent, point
    for p in pl:
        point[p[0] - 1] += p[1]

    queue = child[0]
    while len(queue) > 0:
        now = queue.pop(0)
        point[now] += point[parent[now]]
        queue.extend(child[now])


makeTree()

calcPoint()

print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline 
sys.setrecursionlimit(10 ** 6) 
N,Q = map(int, input().split())

tree = [[] for _ in range(N)]

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

ans = [0] * N

for i in range(Q):
  p,x = map(int, input().split())
  ans[p - 1] += x
  
def dfs(cur, par):
  for chl in tree[cur]:
    ans[chl] += ans[cur]
    dfs(chl,cur)

dfs(0, -1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline 
sys.setrecursionlimit(10 ** 6) 
N,Q = map(int, input().split())

tree = [[] for _ in range(N)]

for i in range(N - 1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  if a > b:
    a,b = b,a
  elif a == b:
    continue
  tree[a].append(b)
  tree[b].append(a)

ans = [0] * N

for i in range(Q):
  p,x = map(int, input().split())
  ans[p - 1] += x
  
def dfs(cur, par):
  for chl in tree[cur]:
    ans[chl] += ans[cur]
    dfs(chl,cur)

dfs(0, -1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#138-d
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)



from collections import deque

def bfs(edges, u, p, cost):
    #cost:今までのコスト
    #root0から順に、costsを更新してゆく
    cost += costs[u]
    costs[u] = cost
    nodes = edges[u]
    for v in nodes:
        if v!=p:
            bfs(edges, v, u, cost)                


n,q = [int(i) for i in input().split()]
costs=[0]*n

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

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

for _ in range(q):
    u,value = [int(i) for i in input().split()]
    costs[u-1] += value 
    
bfs(edges, 0, -1, 0)
print(*costs)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
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] += [b]
  graph[b] += [a]

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

def dfs(u, pre):
  used[u] += 1
  if sum(used) == N:
    return
  for v in graph[u]:
    if v != pre:
      cnt[v] += cnt[u]
      dfs(v, u)
  return

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
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] += [b]
  graph[b] += [a]


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

def dfs(u, pre, c):
  used[u] += 1
  if sum(used) == N:
    return
  for v in graph[u]:
    if v != pre:
      cnt[v] += cnt[u]
      dfs(v, u, cnt[v])

  return

dfs(0, -1, cnt[0])
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
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] += [b]
  graph[b] += [a]


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

def dfs(u, pre, c):
  for v in graph[u]:
    if v != pre:
      cnt[v] += cnt[u]
      dfs(v, u, cnt[v])

dfs(0, -1, cnt[0])
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
# D - Ki
import sys
sys.setrecursionlimit(10**7)

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

# 各頂点に得点を持たせておく
point = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    point[p] += x

ans = [0] * N
def dfs(now, par, pnt):
    ans[now] += pnt + point[now]
    for gi in g[now]:
        if gi!=par:
            dfs(gi, now, ans[now])

dfs(0, 0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
# D - Ki
import sys
sys.setrecursionlimit(10**7)

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

# 各頂点に得点を持たせておく
point = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    point[p] += x

ans = [0] * N
def dfs(now, par, pnt):
    ans[now] += pnt + point[now]
    for gi in g[now]:
        if gi!=par:
            dfs(gi, now, ans[now])

dfs(0, 0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
# D - Ki
import sys
sys.setrecursionlimit(10**7)

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

def searchPar(now, par):
    parent[now] = par
    for gi in g[now]:
        if gi!=par:
            searchPar(gi, now)

def dfs(p, q):
    ans[p] += q
    for gi in g[p]:
        if parent[p]!=gi:
            dfs(gi, q)

# 各頂点の親を探す
parent = [0] * N
for i in range(N):
    searchPar(0, 0)

ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    dfs(p, x)
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*(10**5)+1)
def make_tree(node):
    global cnt
    cnt += 1
    for i in tree_list[node]:
        if i == tree_dic[node]["p"]:
            continue
        tree_dic[node]["c"].append(i)
        tree_dic[i]["p"] = node
        make_tree(i)

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

tree_dic = {} #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = {"p": -1, "c": [], "x": 0}

make_tree(0)

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

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

import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    tmp = tree_dic[i]["x"]
    if i != 0:
        tmp += x_list[tree_dic[i]["p"]]
    x_list[i] = tmp
    for j in tree_dic[i]["c"]:
        next_visit.put(j)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*(10**5)+1)
def make_tree(node):
    for i in tree_list[node]:
        if i != tree_dic[node]["p"]:
            tree_dic[node]["c"].append(i)
            tree_dic[i]["p"] = node
            make_tree(i)

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

tree_dic = {} #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = {"p": None, "c": [], "x": 0}

make_tree(0)

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

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

import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    tmp = tree_dic[i]["x"]
    if i != 0:
        tmp += x_list[tree_dic[i]["p"]]
    x_list[i] = tmp
    for j in tree_dic[i]["c"]:
        next_visit.put(j)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA


def dfs(G, v, p, counter, x):
    """G: graph, v: vertex, p: parent"""
    counter[v] += x
    # Loop for each child
    for c in G[v]:
        if c == p:
            continue  # Avoid multiple access to parent
        dfs(G, c, v, counter, x)


def calc_parent(G, v, p, parent):
    parent[v] = p
    for c in G[v]:
        if c == p:
            continue
        calc_parent(G, c, v, parent)


def main():
    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)

    parent = [-1] * N
    calc_parent(G, 0, -1, parent)
    counter = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        dfs(G, p, parent[p], counter, x)

    print(*counter)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q=map(int,input().split())
AB=[tuple(map(int,input().split())) for _ in range(N-1)]
k=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    k[p-1]+=x
q=deque([1])
ab=AB[:]
while q:
    t=q.popleft()
    tab=ab[:]
    for a,b in tab:
        if t==a:
            q.append(b)
            k[b-1]+=k[t-1]
            ab.remove((a,b))
        elif t==b:
            q.append(a)
            k[a-1]+=k[t-1]
            ab.remove((a,b))
print(*k)

Submission status: Time Limit Exceeded

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

n, q = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)] 
for i in range(1, n):
  a, b = map(int, sys.stdin.readline().split())
  graph[a].append(b)
  graph[b].append(a)

point = [0]*(n+1)
for i in range(q):
  p, x = map(int, sys.stdin.readline().split())
  point[p] += x

seen = [False]*(n+1)
counter = [0]*(n+1)
sum_point = 0

def dfs(v):
  
  global graph
  global seen
  global sum_point
  global counter
  
  seen[v] = True
  sum_point += point[v]
  
  for next_v in graph[v]:
    
    if seen[next_v]: 
      continue
    dfs(next_v)
  
  counter[v] = sum_point
  sum_point -= point[v]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
edges = {}
p = {}
done_nodes = set()
def dfs(target_node, keisyo_point):
    global p
    done_nodes.add(target_node)
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            #edges[next].pop(edges[next].index(target_node))
            #dfs(next, p[target_node])
            if next in done_nodes:
                pass
            else:
                dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    p = {e: 0 for e in range(1, n+1)}
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
edges = {}
p = {}
def dfs(target_node, keisyo_point):
    global p
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            edges[next].pop(edges[next].index(target_node))
            dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    p = {e: 0 for e in range(1, n+1)}
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

seen = [False]*(n+1)
counter = [0]*(n+1)
sum_point = 0

def dfs(v):
  
  global graph
  global seen
  global sum_point
  global counter
  
  seen[v] = True
  sum_point += point[v]
  
  for next_v in graph[v]:
    
    if seen[next_v]: 
      continue
    dfs(next_v)
  
  counter[v] = sum_point
  sum_point -= point[v]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
edges = {}
p = []
done_nodes = set()
def dfs(target_node, keisyo_point):
    global p
    done_nodes.add(target_node)
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            if next in done_nodes:
                pass
            else:
                dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    #edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    p = [0] * (n + 1)
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
n, q = map(int, input().split())

edges = [[] for _ in range(n)]
for _ in range(n - 1):
    frm, to = map(int, input().split())
    # 0-index
    edges[frm - 1].append(to - 1)
    edges[to - 1].append(frm - 1)

scores = [0] * n
for _ in range(q):
    v, s = map(int, input().split())
    scores[v - 1] += s


def dfs(frm, cur):
    if cur > 0:
        scores[cur] += scores[frm]
    for to in edges[cur]:
        if frm != to:
            dfs(cur, to)


dfs(-1, 0)
print(" ".join([str(w) for w in scores]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]


class Node:
    def __init__(self, val):
        self.val = val
        self.child_list = []
        self.cnt = 0

class my_tree:
    def __init__(self, tree_list):
        self.node_list = []

        for i in range(N):
            self.node_list.append(Node(i+1))

        for a, b in tree_list:
            a, b = int(a), int(b)

            child_node = self.node_list[b-1]
            parent_node = self.node_list[a-1]
            self.node_list[a-1].child_list.append(child_node)
            self.node_list[b-1].child_list.append(parent_node)

    def adding(self, query_list):
        for a, data in query_list:
            a, data = int(a), int(data)
            self.node_list[a-1].cnt += data

        stack = deque([self.node_list[0]])
        parent_node_list = [self.node_list[0]]*(N + 1)

        while True:
            v = stack.pop()
            for child in v.child_list:
                if child != parent_node_list[v.val -1]:
                    child.cnt += v.cnt
                    parent_node_list[child.val -1] = v
                    stack.append(child)

            if not stack:
                break


ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

def solve():
    import sys
    sys.setrecursionlimit(2*10**5)

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

    tree = [[] for _ in range(N)]  # 木構造
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)

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

    def dfs(a, p):
        """
        a:対象番号
        p:親番号
        """
        for b in tree[a]:
            if b == p: continue
            anss[b] += anss[a]
            dfs(b, a)

    dfs(0, -1)

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


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(50000000)

class check():
    def __init__(self):
        readline=sys.stdin.readline
        n,q=map(int, readline().rstrip().split())
        self.tree=[[] for i in range(n)]
        self.ans=[0]*n
        for i in range(n-1):
            a,b=map(int, readline().rstrip().split())
            a-=1
            b-=1
            self.tree[a].append(b)
            self.tree[b].append(a)
        for i in range(q):
            p,x=map(int, readline().rstrip().split())
            p-=1
            self.ans[p]+=x
    def do(self,root,next):
        if root >= 0:
            self.ans[next]+=self.ans[root]
        for a in self.tree[next]:
            if a==root:
                continue
            self.do(next,a)
    def answer(self):
        print(" ".join(map(str,self.ans)))

def resolve():
    readline=sys.stdin.readline

    dfs=check()
    dfs.do(-1,0)
    dfs.answer()

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
n, q = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

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

def dfs(frm, cur):
    if cur > 0:
        cnt[cur] += cnt[frm]
    for to in edges[cur]:
        if frm != to:
            dfs(cur, to)

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

Submission status: Time Limit Exceeded

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


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

cnt = [0]*N
pre = [-1]*N
k = 0


def init(v=0, p=-1):
    global k
    pre[v] = k
    k += 1

    for u in G[v]:
        if u == p:
            continue
        init(u, v)


def dfs(v, x):
    cnt[v] += x
    for u in G[v]:
        if pre[v] > pre[u]:
            continue
        dfs(u, x)
    return


init()
for _ in [0]*Q:
    p, x = map(int, input().split())
    dfs(p-1, x)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(10**7)
def main(n,ab,px):
  g=[[]for _ in range(n)]
  for a,b in ab:
    g[a-1].append(b-1)
    g[b-1].append(a-1)
  ans=[0 for _ in range(n)]
  for p,x in px:
    ans[p-1]+=x  
  def dfs(seen,i):
    seen[i]=1
    for li in [li for li in g[i] if seen[li]==0]:
        ans[li]+=ans[i]
        dfs(seen,li)
  seen=[0 for _ in range(n)]
  dfs(seen,0)
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  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)]
  main(n,ab,px)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(10**7)
def main(n,ab,px):
  g=[[]for _ in range(n)]
  for a,b in ab:
    g[a-1].append(b-1)
    g[b-1].append(a-1)
  ans=[0 for _ in range(n)]
  for p,x in px:
    ans[p-1]+=x  
  def dfs(seen,i):
    seen[i]=1
    l=g[i]
    for li in [li for li in l if seen[li]==0]:
        ans[li]+=ans[i]
        dfs(seen,li)
  seen=[0 for _ in range(n)]
  dfs(seen,0)
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  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)]
  main(n,ab,px)

Submission status: Time Limit Exceeded

Solution code:
def main(n,ab,px):
  import sys
  sys.setrecursionlimit(10**7)
  g=[[]for _ in range(n)]
  for a,b in ab:
    g[a-1].append(b-1)
    g[b-1].append(a-1)
  ans=[0 for _ in range(n)]
  for p,x in px:
    ans[p-1]+=x  
  def dfs(seen,i):
    seen[i]=1
    l=g[i]
    for li in [li for li in l if seen[li]==0]:
      ans[li]+=ans[i]
      dfs(seen,li)
  seen=[0 for _ in range(n)]
  dfs(seen,0)
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  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)]
  main(n,ab,px)

Submission status: Time Limit Exceeded

Solution code:
def main(n,ab,px):
  import sys
  sys.setrecursionlimit(10**7)

  g=[[]for _ in range(n)]
  for a,b in ab:
    g[a-1].append(b-1)
    g[b-1].append(a-1)
  ans=[0]*n
  for p,x in px:
    ans[p-1]+=x
  
  def dfs(seen,i):
    seen[i]=1
    l=g[i]
    for li in [li for li in l if seen[li]==0]:
      ans[li]+=ans[i]
      dfs(seen,li)
  seen=[0]*n
  dfs(seen,0)
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  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)]
  main(n,ab,px)

Submission status: Time Limit Exceeded

Solution code:
def main(n,ab,px):
  g=[[]for _ in range(n+1)]
  for a,b in ab:
    g[a].append(b)
    g[b].append(a)

  import sys
  sys.setrecursionlimit(10**7)
  
  # 各頂点を根とした部分木に含まれる頂点を列挙
  d={i:[i] for i in range(1,n+1)}
  def dfs(seen,i):
    ret=[i]
    seen[i-1]=1
    l=g[i]
    for li in [li for li in l if seen[li-1]==0]:
      e=dfs(seen,li)
      for ei in e:
        ret.append(ei)
    d[i]=ret
    return ret
  seen=[0]*n
  s=dfs(seen,1)
  #print(d)
  ans=[0]*n
  for p,x in px:
    for di in d[p]:
      ans[di-1]+=x
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  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)]
  main(n,ab,px)

Submission status: Time Limit Exceeded

Solution code:
def main(n,ab,px):
  g=[[]for _ in range(n+1)]
  for a,b in ab:
    g[a].append(b)
    g[b].append(a)
  # 各頂点を根とした部分木に含まれる頂点を列挙
  d={i:[i] for i in range(1,n+1)}
  def dfs():
    todo=[[1]]
    while len(todo)>0:
      c=todo.pop()
      l=g[c[-1]]
      for li in set(l)-set(c):
        for ci in c:
          d[ci].append(li)
        ct=c.copy()
        ct.append(li)
        todo.append(ct)
  dfs()
  ans=[0]*n
  for p,x in px:
    for di in d[p]:
      ans[di-1]+=x
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  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)]
  main(n,ab,px)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def calc_parents(N, adj_nodes, root=0):
    parents = [-1 for _ in range(N)]
    frontier = [root]
    parents[root] = root
    while len(frontier) > 0:
        node = frontier.pop()
        for child in adj_nodes[node]:
            if parents[child] >= 0:
                continue
            frontier.append(child)
            parents[child] = node
    return parents


def sum_counts(N, parents, counter_roots):
    counter = [0 for _ in range(N)]
    for node in range(N):
        current_node = node
        parent_node = parents[current_node]
        s = counter_roots[current_node]
        while current_node != parent_node:
            current_node = parent_node
            parent_node = parents[current_node]
            s += counter_roots[current_node]
        counter[node] += s
    return counter


def main():
    N, Q = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    parents = calc_parents(N, adj_nodes)
    counter_roots = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = list(map(int, input().split(' ')))
        p -= 1
        counter_roots[p] += x
    counter = sum_counts(N, parents, counter_roots)
    print(' '.join(map(str, counter)))


if __name__ == '__main__':
    main()