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:
from sys import setrecursionlimit
setrecursionlimit(10000000)
n, q = map(int, input().split())

ct = [0] * (n+1)
o = [0] * (n+1)
g = [[] for _ in range(n+1)]

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

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

def dfs(p, parent):
  ct[p] += o[p] + ct[parent]
  for i in g[p]:
    if i != parent:
      dfs(i, p)
dfs(1, 0)
print(*ct[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def input():
    return sys.stdin.readline()

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

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

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

# print(edge)
# print(counter)

visited = [False] * (N + 1)
visited[1] = True
ans = [0] * (N + 1)

def dfs(fro, p):
    visited[fro] = True
    now = counter[fro] + p
    for to in edge[fro]:
        if not visited[to]:
            dfs(to, now)
    ans[fro] = now
    return

dfs(1, 0)

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200005)

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

to = [[] for i in range(n)]


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

score = [0]*n

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


def down_tree(index, parent=-1):
    global score
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)
    return


down_tree(0)

for i in range(len(score)):
	print(score[i])

Submission status: Time Limit Exceeded

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

counter = [0] * (n+1)
o = [0] * (n+1)
g = [[] for _ in range(n+1)]

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

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

def dfs(p, parent):
  counter[p] += o[p] + counter[parent]
  for i in g[p]:
    if i != parent:
      dfs(i, p)
 
dfs(1, 0)
print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
N,Q = map(int,input().split())
to = [[] for _ in range(N+1)]
ans = [0 for _ in range(N+1)]

for _ in range(N-1):
    a,b=map(int,input().split())
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    px = list(map(int,input().split()))
    ans[px[0]] += px[1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200005)

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

to = [[] for i in range(n)]


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

score = [0]*n

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


def down_tree(index, parent=-1):
    global score
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)
    return


down_tree(0)

for i in range(len(score)):
	print(score[i])

Submission status: Time Limit Exceeded

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

counter = [0 for _ in range(n+1)]
o = [0 for _ in range(n+1)]
g = [[] for _ in range(n+1)]

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

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


def dfs(p, parent):
  counter[p] += o[p] + counter[parent]
  for i in g[p]:
    if i != parent:
      dfs(i, p)
 
dfs(1, 0)
print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
N,Q = list(map(int,input().split()))
to = [[] for _ in range(N+1)]
ans = [0 for _ in range(N+1)]

for _ in range(N-1):
    a,b=map(int,input().split())
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    px = list(map(int,input().split()))
    ans[px[0]] += px[1]

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

Submission status: Time Limit Exceeded

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

import collections
import sys
sys.setrecursionlimit(10000000)
n, q = map(int, input().split())

counter = [0 for _ in range(n+1)]
o = collections.defaultdict(int)
g = collections.defaultdict(list)

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

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


def dfs(p, parent):
  counter[p] += o[p] + counter[parent]
  for i in g[p]:
    if i != parent:
      dfs(i, p)
 
dfs(1, 0)
print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = 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)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


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

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]

print(*res_list)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = 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)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


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

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]


ans = " ".join([str(i) for i in res_list])
print(ans)

Submission status: Time Limit Exceeded

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

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

#入力

def dfs(pre,now,w):
    ans[now] += w
    for i in tree[now]:
        if i != pre:
            dfs(now,i,ans[now])

dfs(-1,0,0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N,Q = list(map(int,input().split()))
to = [[] for _ in range(N+1)]
ans = [0 for _ in range(N+1)]

for _ in range(N-1):
    ab=list(map(int,input().split()))
    to[ab[0]].append(ab[1])
    to[ab[1]].append(ab[0])
for _ in range(Q):
    px = list(map(int,input().split()))
    ans[px[0]] += px[1]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = 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)]

edge_map = {}
for i in range(N):
    edge_map[i] = deque([])

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


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

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]


ans = " ".join([str(i) for i in res_list])
print(ans)

Submission status: Time Limit Exceeded

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

import sys
import collections

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

counter = [0 for _ in range(n+1)]
o = collections.defaultdict(int)
g = collections.defaultdict(list)

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

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


queue = [1]
parents = []
while queue:
  p = queue.pop(-1)
  parents.append(p)
  counter[p] += o[p]
  for i in g[p]:
    if not i in parents:
      queue.append(i)
      counter[i] += counter[p]
 
print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
N, Q = map(int, input().split())

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

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

ans = [0] * N

def func(node,p_node):
    ans[node-1] += operations[node-1]
    if p_node != 0:
        connection[node-1].remove(p_node)
    for c_node in connection[node-1]:
        ans[c_node-1] += ans[node-1]
        func(c_node, node)

func(1, 0)

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

Submission status: Time Limit Exceeded

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

import sys
import collections

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

counter = collections.defaultdict(int)
o = collections.defaultdict(int)
g = collections.defaultdict(list)

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

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


queue = [1]
parents = []
while queue:
  p = queue.pop(0)
  parents.append(p)
  count = o[p]
  for i in g[p]:
    if not i in parents:
      queue.append(i)
    else:
      count += counter[i]
  counter[p] += count
 
for i in range(1, n+1):
  print(counter[i], end=' ')

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

if 'LOCAL' in os.environ:
    N = 2* 10** 5
    Q = 2 * 10 ** 5
    AB = [[i, i + 1] for i in range(1, N)]
    PX = [[i, 10] for i in range(Q)]
else:
    N, Q = LI()
    AB = []
    PX = []
    for i in range(N-1):
        #  AB.append(LI())
        AB.append(sorted(LI()))

    for i in range(Q):
        PX.append(LI())


"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？

カウントを若い順にやっていく
"""
AB = sorted(AB, key=lambda x: x[0])
perr('AB')
perr(AB)
d = {}
for i in range(N+1):
    d[i] = 0
for p, x in PX:
    if p not in d.keys():
        d[p] = 0
    d[p] += x

"""
根からスタートするとは？
1-5-3とかっていう組み合わせがあるため、dfsで根から辿っていく必要がある

"""
ans = [0 for _ in range(N)]
ans[0] = d[1]
def dfs(current_node, val, done_list):
    target_lines = [_ for _ in AB if current_node in _ and not any(n in done_list for n in _)]
    done_list.append(current_node)
    for line in target_lines:
        perr(line)
        if line[0] == current_node:
            new_node = line[1]
        else:
            new_node = line[0]
        ans[new_node-1] = val + d[new_node]
        dfs(new_node, ans[new_node-1], done_list)

dfs(1, d[1], [])
perr(ans)
for a in ans:
    print(a, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def main():
  N,Q = map(int,input().split())
  trees = [[] for _ in range(N+1)]
  values = [0 for _ in range(N+1)]
  
  for _ in range(N-1):
    parent,child = map(int,input().split())
    trees[parent].append(child)
    trees[child].append(parent)
  
  for _ in range(Q):
    node_num,value = map(int,input().split())
    values[node_num] += value
  
  def recursive_func(i,parent):
    for child in trees[i]:
      if child == parent:
        continue
      values[child] += values[i]
      recursive_func(child,i)
  
  recursive_func(1,-1)
  print(*values[1:])


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys
sys.setrecursionlimit(200000)
N, Q = map(int, input().split())

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

operations = defaultdict(int)
for i in range(Q):
    p,q =  map(int, input().split())
    operations[p] += q

ans = defaultdict(int)

def func(node,p_node):
    ans[node] += operations[node]
    if p_node != 0:
        connection[node].remove(p_node)
    for c_node in connection[node]:
        ans[c_node] += ans[node]
        func(c_node, node)

func(1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
      	if next == prev:
        	continue
      	else:
          dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

#初期のカウンター
ans=[0]*n

#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    [dfs(next, now) for next in g[now] if ((next != prev) and (not memo[next]))]
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

#初期のカウンター
ans=[0]*n
memo = [False for i in range(n)]

#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

#初期のカウンター
ans=[0]*n
memo = [False for i in range(n)]

#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())

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

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

def dfs2(i, parent):
    for j in trees[i]:
        if j == parent: continue
        values[j] += values[i]
        dfs2(j, i)

dfs2(1, -1)
print(*values[1:])

Submission status: Time Limit Exceeded

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

#=====================================
class Tree():
  def __init__(self):
    self.children = set()
    self.counter = 0

  def add_child(self, child):
    self.children.add(child)
  
  def reconstruct(self, root=None):
    if root in self.children:
      self.counter += root.counter
      self.children.remove(root)
    for child in self.children:
      child.reconstruct(self)
  
  def add_count(self, x):
    self.counter += x

#=====================================
def solve():
  n,q = [int(i) for i in input().split()]
  trees = [Tree() for i in range(n)]

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

  for _ in range(q):
    p,x = [int(i) for i in input().split()]
    trees[p-1].add_count(x)

  trees[0].reconstruct()
  
  print(*[trees[i].counter for i in range(n)])

#=====================================
if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

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

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

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

def dfs2(i, parent):
    for j in trees[i]:
        if j == parent: continue
        values[j] += values[i]
        dfs2(j, i)

dfs2(1, -1)
print(*values[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = list(map(int, input().split()))

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

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

def dfs2(i, parent):
    for j in trees[i]:
        if j == parent: continue
        values[j] += values[i]
        dfs2(j, i)

dfs2(1, -1)
print(*values[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

nodes = [[] for _ in range(N)]
values = [0 for _ in range(N)]

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

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

def dfs(i, p):
  for c in nodes[i]:
    if c != p:
      values[c] += values[i]
      dfs(c, i)

dfs(0, None)
print(*values)

Submission status: Time Limit Exceeded

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

#=====================================
class Tree():
  def __init__(self):
    self.root = None
    self.children = set()
    self.counter = 0

  def add_child(self, child):
    self.children.add(child)
  
  def reconstruct(self, root=None):
    if root in self.children:
      self.root = root
      self.children.remove(root)
    for child in self.children:
      child.reconstruct(self)
  
  def add_count(self, x):
    self.counter += x

  def recalc_count(self):
    if self.root:
      self.counter += self.root.counter
    for child in self.children:
      child.recalc_count()

#=====================================
def solve():
  n,q = [int(i) for i in input().split()]
  trees = [Tree() for i in range(n)]

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

  trees[0].reconstruct()

  for _ in range(q):
    p,x = [int(i) for i in input().split()]
    trees[p-1].add_count(x)

  trees[0].recalc_count()
  
  print(*[trees[i].counter for i in range(n)])

#=====================================
if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

#初期のカウンター
ans=[0]*n
memo = [False for i in range(n)]

#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = list(map(int, input().split()))
trees =  [ [] for i in range(n) ]
for i in range(n-1):
    a, b = list(map(int, input().split()))
    trees[a-1].append(b-1)
    trees[b-1].append(a-1)

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

def dfs2(i, parent):
    for j in trees[i]:
        if j == parent: continue
        values[j] += values[i]
        dfs2(j, i)

dfs2(0, -1)
print(*values)

Submission status: Time Limit Exceeded

Solution code:
n, q = [int(x) for x in input().split()]
vs   = []
us   = [1]
xs   = None
	
for _ in range(0, n + 1):
	vs.append([])
	xs = [0] * (n + 1)

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

for _ in range(0, q):
	p, x   = [int(x) for x in input().split()]
	xs[p] += x
	
for i in range(0, n):
	x = xs[us[i]]
	for v in vs[us[i]]:
		if v not in us:
			xs[v] += x
			us.append(v)

print(" ".join(str(x) for x in xs[1:]))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
import sys
sys.setrecursionlimit(20000)


def main():
    N, Q = map(int, input().split())
    # A = []
    # B = []
    countList = [0]*N
    treeEdge = [[] for i in range(N)]

    for i in range(N-1):
        Ai, Bi = map(int, input().split())
        Ai -= 1
        Bi -= 1
        treeEdge[Ai].append(Bi)
        treeEdge[Bi].append(Ai)

    for i in range(Q):
        pi, xi = map(int, input().split())
        countList[pi - 1] += xi

    countList = addCount(0, -1, treeEdge, countList)

    for ci in countList:
        print(ci, end=" ")

    print()
    return


def addCount(index, parent, treeEdge, countList):
    if parent == -1:
        pass
    else:
        countList[index] += countList[parent]

    nextlist = treeEdge[index]

    if not len(nextlist) > 0:
        return countList
    else:
        for child in nextlist:
            if not child == parent:
                countList = addCount(child, index, treeEdge, countList)
    return countList


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = [int(x) for x in input().split()]
vs   = []
us   = [1]
xs   = None
fs   = None
	
for _ in range(0, n + 1):
	vs.append([])
	xs = [0]     * (n + 1)
	fs = [False] * (n + 1)

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

for _ in range(0, q):
	p, x   = [int(x) for x in input().split()]
	xs[p] += x
	
while 0 < len(us):
	u     = us.pop(0)
	x     = xs[u]
	fs[u] = True
	for n in vs[u]:
		if fs[n] == False:
			xs[n] += x
			us.append(n)

print(" ".join(str(x) for x in xs[1:]))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

# class Node:
#     def __init__(self, idx):
#         self.idx = idx
#         self.v = 0
#         self.parent = None
#         # self.children = []
#
#     def make_tree(self, addval=0):
#         self.v += addval
#         keyidx = bisect_left(brs_keys, self.idx)
#         while keyidx < len(brs_keys) and brs_keys[keyidx] == self.idx:
#             ni = brs[keyidx][1]
#             node = nodes[ni]
#             # if not node.children:
#             #     self.children.append(node)
#             node.make_tree(self.v)
#             keyidx += 1
#         # for c in self.children:
#         #     c.make_tree(self.v)
#
#     def __str__(self):
#         return str(self.idx)


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

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

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

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


ans = [-1] * N


def tree(node_idx, addval):
    ans[node_idx] = nodes[node_idx] + addval
    keyidx = bisect_left(brs_keys, node_idx)
    while keyidx < len(brs_keys) and brs_keys[keyidx] == node_idx:
        ni = brs[keyidx][1]
        if ans[ni] < 0:
            tree(ni, ans[node_idx])
        keyidx += 1


tree(0, 0)

print(*[n for n in ans])

Submission status: Time Limit Exceeded

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

#=====================================
class Tree():
  def __init__(self):
    self.root = None
    self.children = set()
    self.counter = 0

  def add_child(self, child):
    self.children.add(child)
  
  def reconstruct(self, root=None):
    if root in self.children:
      self.root = root
      self.children.remove(root)
    for child in self.children:
      child.reconstruct(self)
  
  def add_count(self, x):
    self.counter += x

  def add_root_count(self):
    if self.root:
      self.counter += self.root.counter
    for child in self.children:
      child.add_root_count()

#=====================================
def solve():
  n,q = [int(i) for i in input().split()]
  trees = [Tree() for i in range(n)]

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

  trees[0].reconstruct()

  for _ in range(q):
    p,x = [int(i) for i in input().split()]
    trees[p-1].add_count(x)

  trees[0].add_root_count()
  
  print(*[trees[i].counter for i in range(n)])

#=====================================
if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
 
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)
 
 
n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
 
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v
 
ans=[0]*n
memo = [False for i in range(n)]
dfs(0,0)
 
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8


def main():
    N, Q = map(int, input().split())
    A = []
    B = []
    # P = []
    # X = []
    countList = [0]*N
    # print(N, Q)
    treeParent = [-1] * N
    treeParent[0] = 0
    treeChild = [[] for i in range(N)]

    for i in range(N-1):
        Ai, Bi = map(int, input().split())
        A.append(Ai)
        B.append(Bi)

    while -1 in treeParent:
        for i in range(N-1):
            ai = A[i]
            bi = B[i]
            if treeParent[ai-1] >= 0 >= 0 and treeParent[bi-1] >= 0:
                continue
            elif treeParent[ai-1] >= 0:
                treeParent[bi-1] = ai
                treeChild[ai-1].append(bi)
            elif treeParent[bi-1] >= 0:
                treeParent[ai-1] = bi
                treeChild[bi-1].append(ai)

    # print(treeParent)
    # print(treeChild)

    for i in range(Q):
        pi, xi = map(int, input().split())
        # P.append(pi)
        # X.append(xi)
        countList[pi - 1] += xi
        # countList = addCount(pi, xi, treeParent, treeChild, countList)

    # print(countList)
    # print(treeParent)
    countList = addCount(1, treeParent, treeChild, countList)

    for ci in countList:
        print(ci, end=" ")

    print()
    return


def addCount(index, treeParent, treeChild, countList):
    if treeParent[index-1] == 0:
        pass
    else:
        countList[index-1] += countList[treeParent[index-1]-1]

    nextlist = treeChild[index-1]
    # print(nextlist)

    if not len(nextlist) > 0:
        return countList
    else:
        for child in nextlist:
            countList = addCount(child, treeParent, treeChild, countList)
    return countList


if __name__ == "__main__":
    main()