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 collections as C
n, q = map(int,input().split())

g = C.Counter([])
p = C.Counter([])
for i in range(n-1):
	a,b = map(int,input().split())
	if a not in g.keys():
		g[a] = [b]
	elif a in g.keys():
		g[a].append(b)

for i in range(q):
	a,b = map(int,input().split())
	if a not in p.keys():
		p[a] = b
	elif a in p.keys():
		p[a] += b

ans = [0 for _ in range(n)]
que = [0]
i = 1
while i > 0:

	if i in p.keys():
		ans[i-1] += p[i]
	if i in g.keys():
		for j in g[i]:
			ans[j-1] = ans[i-1]
			que.append(j)
	i = que.pop()


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Aug 18 21:19:43 2019
ABC138D
@author: maezawa
"""

n, q = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    graph[ai].append(bi)
    graph[bi].append(ai)
    
parent = [[] for _ in range(n+1)]
child = [[] for _ in range(n+1)]
current = 1
while current <= n:
    for j in graph[current]:
        if current in child[j]:
            continue
        child[current].append(j)
    current += 1
#print(child)
parray = [-1]*(n+1)
parray[1] = 0
for i in range(1,n+1):
    for j in child[i]:
        parray[j] = i
#print(parray)
tpoint = [0]*(n+1)
for i in range(q):
    pi, xi = list(map(int, input().split()))
    tpoint[pi] += xi
tpmem = [-1]*(n+1)
tpmem[1] = tpoint[1]
for i in range(1, n+1):
    pi = 0
    j = i
    prej = j
    while True:
        if tpmem[j] != -1:
            pi += tpmem[j]
            tpmem[prej]=tpmem[j]
            break
        pi += tpoint[j]
        if parray[j] == -1:
            break
        prej = j
        j = parray[j]
    print(pi)
    tpmem[i] = pi

Submission status: Time Limit Exceeded

Solution code:
import math

node_len, ope_count = [int(x) for x in input().split()]

node_path = {}
node_weight = {}

for i in range(node_len-1):
    parent, child = input().split()

    # if i == 0:
    #     node_path[parent] = {
    #         "path": [parent],
    #         "child": [child]
    #     }
    #     node_weight[parent] = 0


    if parent not in node_path:
        node_path[parent] = {
            "path": [parent],
            "child": [child]
        }
        node_weight[parent] = 0
    else:
        node_path[parent]["child"] += [child]
    
    if child not in node_path:
        node_path[child] = {
            "path": [],
            "child": []
        }
        node_weight[child] = 0
        # if parent in node_path:
        node_path[child]["path"] = node_path[parent]["path"] + [child]
    else:
        for c in node_path[child]["child"]:
            node_path[c]["path"] = [parent] + node_path[c]["path"]
        node_path[child]["path"] = [parent] + node_path[child]["path"]

    


for i in range(ope_count):
    node_id, weight = input().split()
    node_weight[node_id] += int(weight)

for i in range(node_len):
    node_id = str(i + 1)
    value = sum([node_weight[id] for id in node_path[node_id]["path"]])
    print(value)

Submission status: Time Limit Exceeded

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

def upper(a,b):
  if gu[a] == {}:
    gl[a].add(b)
  else:
    gl[a].add(b)
    for l in gu[a]:
      upper(l, b)

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

for b in range(n):
  for a in gu[b]:
    upper(a,b)

#print(gu)
#print(gl)

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

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

Submission status: Time Limit Exceeded

Solution code:
np = input().split()
N = int(np[0])
Q = int(np[1])

connection_dictionary = {}  # key:id, value:child list
# 読み込んでグラフを作成
# ノード間のつながりができてから，親と子を決定する
node_list = [0 for _ in range(N)]  # nodeごとのadd number

for _ in range(N-1):
    ab = input().split()
    a = int(ab[0]) - 1
    b = int(ab[1]) - 1
    if a in connection_dictionary:
        new_list = connection_dictionary[a]
        new_list.append(b)
        connection_dictionary[a] = new_list
    else:
        connection_dictionary[a] = [b]

# ノードごとに足される数を保存する
for _ in range(Q):
    px = input().split()
    p = int(px[0])
    x = int(px[1])
    node_list[p-1] += x
# のーど1からノードにあるadd numberを足していく
# node 1 から親子関係を決定する
calc_list = [0]
while calc_list:
    calc_number = calc_list.pop(0)
    add_number = node_list[calc_number]
    if calc_number in connection_dictionary:
        child_list = connection_dictionary[calc_number]
        for child in child_list:
            node_list[child] += add_number
            calc_list.append(child)
# 出力
for node in node_list:
    print(node, end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def dfs(graph, start):
    stack = [start]
    visited = []
    while stack:
        label = stack.pop(0)
        if label not in visited:
            visited.append(label)
            stack = graph.get(label, []) + stack
    return visited
  
tree = defaultdict(list)
N,Q = map(int, input().split())

lst1 = [list(map(int, input().split())) for i in range(N-1)]
lst2 = [list(map(int, input().split())) for i in range(Q)]
for i in range(N):
  dict(tree)[i+1] = []
for i in lst1:
  tree[i[0]].append(i[1])
ans = [0] * N
for i in lst2:
  start = i[0]
  if (start == 1):
      ans = list(map(lambda x: x + i[1], ans))
  else:
    for j in list(dfs(dict(tree), start)):
      if (start <= j):
        ans[j-1] += i[1]
print(" ".join(list(map(str,ans))))

Submission status: Time Limit Exceeded

Solution code:
NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])
candidate_list = []
tree_dict = {}
#Make tree dict
for i in range(N-1):
    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])
    tree_dict[i+1] = {
                'count': 0,
                'has_trees': []
            }
    candidate_list.append((a,b))
tree_dict[N] = {
    'count': 0,
    'has_trees': []
    }
candidate_list.reverse()
 
for candidate in candidate_list:
    a = candidate[0]
    b = candidate[1]
    tree_dict[a]['has_trees'] += tree_dict[b]['has_trees'] + [b]
        
 
for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    tree_dict[p]['count'] += x
out_put_list = [0] * N
for k, v  in tree_dict.items():
    out_put_list[k-1] += v['count']
    for idx in v['has_trees']:
        out_put_list[idx-1] += v['count']
print(' '.join(map(str,out_put_list)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import numpy as np

N, Q = map(int, input().split())
E = [[int(i) for i in input().split()] for i in range(N-1)]
quest = [[int(i) for i in input().split()] for i in range(Q)]

neighborhood = {}
for e in E:
    neighborhood.setdefault(e[0], []).append(e[1])

children_tree = {}
for i in range(1, N+1):
    roots = [i]
    children = []
    while len(roots) != 0:
        temp = []
        for root in roots:
            c = neighborhood.get(root, 'None')
            if not c == 'None':
                temp.extend(c)
                children.extend(c)
        roots[:] = temp
    children_tree[i] = children

counter = np.zeros(N)
for q in quest:
    root = q[0]
    counter[root - 1] += q[1]
    childs = list(map(lambda x: x - 1, children_tree[root]))
    counter[childs] += q[1]

for c in counter:
    print(int(c), end=' ')

Submission status: Time Limit Exceeded

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

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

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

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

print(*res)

Submission status: Time Limit Exceeded

Solution code:
def get_subgraph(node):
  subgraph = [node]
  for i, j in edges:
    if node == i:
      subgraph.extend(get_subgraph(j))
  return subgraph

n, q = map(int, input().split())
edges = []
for i in range(n-1):
  e, f = map(int, input().split())
  edges.append((e, f))

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

counter = list(map(int, list('0'*n)))

subgraphs = []
for i in range(1, n+1):
  subgraphs.append(get_subgraph(i))

for p, x in tasks:
  for i in subgraphs[p-1]:
    counter[i-1] += x
print(' '.join(map(str, counter)))

Submission status: Time Limit Exceeded

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

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

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

def BFS(start,edges,N,c):
    roots=[[] for _ in range(N)]
    for a,b in edges:
        roots[a-1]+=[(b-1,c[b-1])]
    queue=[]
    queue.append(start)
    res[start] = c[start]
    while queue:
        label = queue.pop()
        for i,c in roots[label]:
            if res[i] == -1:
                res[i]= res[label]+c
                queue += [i]
    return res
print(*BFS(0,edges,N,c))

Submission status: Time Limit Exceeded

Solution code:


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

a = [0] * (N - 1)
b = [0] * (N - 1)

p = [0] * Q
x = [0] * Q

point = [0] * N

def kasan(n, y):
    z = 0
    for i in range(Q):
        
        if p[i] == n:
            z += x[i]
    for i in range(N - 1):
        if a[i] == n:
            kasan(b[i],y + z)
    
    point[n - 1] += y + z

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

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

kasan(1,0)

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n-1)]
l.sort()
# print(l)

lq = [list(map(int, input().split())) for _ in range(q)]
lq.sort()
lq_new = []
for i in range(q):
    if i == 0:
        lq_new = [lq[0]]
    else:
        if lq[i][0] == lq[i-1][0]:
            lq_new[-1][1] += lq[i][1]
        else:
            lq_new.append(lq[i])
lq = lq_new

ch = [[] for _ in range(n)]
ad = [[] for _ in range(n)]

for i in range(n-1):
    a, b = l[i][0]-1, l[i][1]-1
    ch[a].append(b)
    ad[b].append(a)
    for x in ad[a]:
        ch[x].append(b)
        ad[b].append(x)

# print(ch)
# print(ad)

ans = [0 for _ in range(n)]
for i in range(len(lq)):
    p, x = lq[i][0]-1, lq[i][1]
    ans[p] += x
    for j in ch[p]:
        ans[j] += x

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

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
par=[-1 for i in range(n+1)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す
p=[-1 for i in range(n+1)]
pp=[[] for i in range(n+1)]
p[1]=0
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    x,y=a,b
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
        x,y=y,x
    par[a]+=par[b]
    par[b]=a
    p[b]=x
    pp[x].append(b)
    
    return True
ll=[]
for i in range(n-1):
    a=[int(j) for j in input().split()]
    ll.append(a)
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

l=[0 for i in range(n+1)]
for i in range(q):
    r=[int(j) for j in input().split()]
    l[r[0]]+=r[1]

from collections import deque
qu=deque([1])

i=0
while qu:
    qq=qu.popleft()
    l[qq]+=l[p[qq]]
    for j in pp[qq]:
        qu.append(j)


print(*l[1:])

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**6)
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


point_root = [0] * N
query = [None]
for i in range(Q):
    p,x = map(int, input().split())
    point_root[p-1] += x 
point_root = tuple(point_root)
ans = [0] * N
visited = [False] * N

def solve(node, point):
    
    ans[node] += point



    if es.get(node, None) != None:
        for i in es[node]:
            solve(i, point+point_root[i])
solve(0, point_root[0])
print(*ans)

Submission status: Time Limit Exceeded

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

operate = []
for _ in range(q):
    operate.append(tuple(map(int, input().split())))

for p, x in operate:
    que = deque([])
    que.append(p-1)

    while que:
        t = que.popleft()
        count[t] += x
        sakis = connect[t]
        for saki in sakis:
            que.append(saki)
    
for c in count:
    print(c, end = ' ')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, q = (int(_) for _ in input().split())  
arr = np.array([[1 if i == j else 0 for i in range(n)] for j in range(n)])
output = np.array([0 for i in range(n)])
ab = []
for i in range(n-1):
  a, b = (int(_) for _ in input().split()) 
  ab.append([a, b])
  
for x in reversed(ab):
  a = x[0]
  b = x[1]
  arr[a-1] = arr[a-1] | arr[b-1]

for i in range(q):
  p, q = (int(_) for _ in input().split()) 
  output += arr[p-1] * q
    
print(' '.join([str(x) for x in output]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
tree = [list(map(int, input().split())) for i in range(N-1)]
process =  [list(map(int, input().split())) for i in range(Q)]
 
def next_node(node_num):
  next_nodes = []
  for edge in tree:
    if edge[0] == node_num:
      next_nodes.append(edge[1])
  return next_nodes
 
def all_nodes(num):
  x = [] 
  add_nodes = next_node(num)
  for j in range(N):
    for i in add_nodes:
      add_nodes += next_node(i) 
      x += add_nodes
      add_nodes = []
  return x
 
 
def add(score, procedure):
  "procedure = [p, x]"
  score[procedure[0]-1] += procedure[1]
  for n in all_nodes(procedure[0]):
    score[n-1] += procedure[1]
  return score
 
 
score = [0]*N
for procedure in process:
  add(score, procedure)

for s in score:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
#入力n,q,の受け取り
n,q = map(int, input().split())

#ab[i]には頂点iにつながる頂点たちが列挙されている
#ただし、最後の数字は各頂点以下に加えるxの値
ab = [0]*n
for i in range(n):
    ab[i] = []
for i in range(n-1):
    inp = list(map(int, input().split()))
    inp.sort()
    ab[inp[0]-1].append(inp[1])
for i in range(n):
    ab[i].append(0)

#入力p,xの受け取り
for i in range(q):
    px = list(map(int, input().split()))
    ab[px[0]-1][-1] += px[1]

#あとは答えを出して行って終わり
for i in range(n):
    len_ = len(ab[i])-1
    for j in range(len_):
        ab[ ab[i][j]-1 ][-1] += ab[i][-1]
ans = [0]*n
for i in range(n):
    ans[i] = str(ab[i][-1])
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def resolve():
    n, q = map(int, input().split())
    ab = sorted(list(list(map(int, input().split())) for _ in range(n - 1)))
    pq = list(list(map(int, input().split())) for _ in range(q))
    d = defaultdict(list)
    counters = [0] * n
    child_nodes = [[0]] * n
    for a, b in ab:
        d[a].append(b)
    for p, q in pq:
        child = child_nodes[p - 1] if not child_nodes[p - 1] else d[p]
        nodes = [p] + child
        while any([c in d for c in child]):
            new_nodes = []
            for c in child:
                if not child_nodes[c - 1]:
                    new_nodes += child_nodes[c - 1]
                elif c in d:
                    new_nodes += d[c]
            child = new_nodes
            nodes += new_nodes
        child_nodes[p - 1] = nodes
        for n in nodes:
            counters[n - 1] += q
    print(" ".join([str(c) for c in counters]))


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n, q =  map(int, raw_input().split())
graph = dict()
operation = [0 for i in range(q)]
for i in range(n-1):
    a, b = map(int, raw_input().split())
    if a in graph.keys():
        graph[a].add(b)
    else:
        graph[a] = set([b])
    if b in graph.keys():
        graph[b].add(a)
    else:
        graph[b] = set([a])

for i in range(q):
    operation[i] = [int(j) for j in raw_input().split()]

values = [0 for i in range(n)]

def dfs(graphx, vertex, check, value):
    check[vertex-1] = True
    values[vertex-1] += value
    for v in graph[vertex]:
        if check[v - 1] == True:
            continue
        dfs(graphx, v, check, value)


for i in range(q):
    check_list = [False for j in range(n)]
    ver = operation[i][0]
    for v in graph[ver]:
        if v < ver:
            check_list[v-1] = True
    dfs(graph, operation[i][0], check_list, operation[i][1])

mapped_values = map(str, values)

result = ""
for i in range(n):
    result += mapped_values[i]
    if i < n - 1:
        result += " "

print(result)

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 = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi)
    graph[bi - 1].append(ai)

# print("#", graph)

cnttab = [0] * N
for j, (pj, xj) in enumerate(px):
    cnttab[pj - 1] += xj

# print("#", cnttab)


ans = [None] * N
ans[0] = cnttab[0]
# from collections import deque
# q = deque([(1, None, ans[0])])

def mypopleft(q, idx):
    return q[idx], (idx + 1)

q = [(1, None, ans[0])]
idx = 0
while len(q) > idx:
    (src, prev, score), idx = mypopleft(q, idx)
    for dst in graph[src - 1]:
        if dst == prev: continue
        ans[dst - 1] = score + cnttab[dst - 1]
        if len(graph[dst - 1]) > 1:
            q.append((dst, src, ans[dst - 1]))

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

Submission status: Time Limit Exceeded

Solution code:
inputNumN = list(map(int, input().split()))
N = inputNumN[0]
Q = inputNumN[1]

AB = {}
for i in range(N - 1):
    inputNumAB = list(map(int, input().split()))
    if not AB.get(inputNumAB[0]):
        AB[inputNumAB[0]] = []
    AB[inputNumAB[0]].append(inputNumAB[1])

PQ = {}
for i in range(Q):
    inputNumPQ = list(map(int, input().split()))
    if not PQ.get(inputNumPQ[0]):
        PQ[inputNumPQ[0]] = 0
    PQ[inputNumPQ[0]] += inputNumPQ[1]
PQ = sorted(PQ.items())

result = [0] * N

for pq in PQ:
    result[pq[0] - 1] += pq[1]

for A, B in AB.items():
    for b in B:
        result[b - 1] += result[A - 1]

for r in result:
    print(r, end=' ')

Submission status: Time Limit Exceeded

Solution code:
#import pysnooper
import os,re,sys,operator,math,heapq,string
from collections import Counter,deque
from operator import itemgetter
from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
from copy import deepcopy

setrecursionlimit(10**6)

def rec(pp,xx):
    for i in range(n):
        if gragh[pp][i]:
            cnt[i]+=xx
            if tree[i]:
                continue
            rec(i,xx)
    return
n,q=map(int,stdin.readline().rstrip().split())
gragh=[[0]*n for _ in range(n)]
cnt=[0]*n
tree=[0]*n
for i in range(n-1):
    a,b=map(int,stdin.readline().rstrip().split())
    tree[a-1],tree[b-1]=0,1
    gragh[a-1][b-1]=1
for i in range(q):
    p,x=map(int,stdin.readline().rstrip().split())
    cnt[p-1]+=x
    rec(p-1,x)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


#深さ優先探索
def dfs(pt,v):
    n=len(pt)
    d=[-1]*n
    check_visited = [False]*n
    check_visited[v] = True
    S = [v]
    d[v] = 0
    while S:
        v1 = S.pop()
        for i in pt[v1]:
            if check_visited[i] == False:
                check_visited[i] = True
                d[i] = d[v1] + 1
                S.append(i)
    return d


pt = [[] for _ in range(N)]
for i in range(N-1):
    pt[a[i]].append(b[i])
    pt[b[i]].append(a[i])
d = dfs(pt,0)

parent = defaultdict(list)
for i in range(N-1):
    if d[a[i]]>d[b[i]]:
        parent[a[i]].append(b[i])
    else:
        parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(N):
    now = i
    ans = 0
    while now != 0:
        ans += val[now]
        now = parent[now][0]
    print(val[0]+ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

p = [0]*q
x = [0]*q

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

a,b = (list(x) for x in zip(*sorted(zip(a, b))))
p,x = (list(y) for y in zip(*sorted(zip(p,x))))


score = [0]*n

def down_tree(parent, add_score, q_start, n_start):
    global score
    for i in range(q_start, q):
        if p[i]-1 == parent:
            add_score += x[i]
        if p[i]-1 >parent:
            q_start = i
            break
    for i in range(n_start, n-1):
        if a[i]-1 == parent:
            down_tree(b[i]-1, add_score, q_start, i)
        if a[i]-1 > parent:
            break

    score[parent] += add_score

    return 0

down_tree(0, 0, 0, 0)

print(*score)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(N-1)]
m = [list(map(int,input().split())) for _ in range(Q)]
ll = [0]*N
bb = [[i] for i in range(1,N+1)]
for i in l:
    bb[i[0]-1].append(i[1])
for i in m:
    ll[i[0]-1] += int(i[1])
ans = [0]*N
# print("bb=",bb)
# print("ll=",ll)
for i in range(N):
    for k in bb[i]:
        if k == i+1:
            ans[i] += ll[i]
        else:
            ll[k-1] += ll[i]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
A = [set([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    A[a].add(b)
    A[b].add(a)
S = [1]
while S:
    a_1 = S[0]
    for a_2 in A[a_1]:
        A[a_2] -= {a_1}
        S += a_2,
    S.pop(0)
C = [0]*(n+1)
for _ in range(q):
    p_1, x = map(int, input().split())
    C[p_1] += x
    T = [p_1]
    while T:
        p_1 = T[0]
        for p_2 in A[p_1]:
            C[p_2] += x
            T += p_2,
        T.pop(0)
print(*C[1:])

Submission status: Time Limit Exceeded

Solution code:
N,Q = (int(i) for i in input().split())
X = []
for i in range(N-1):
    Y = [int(n) for n in input().split()]
    X.append(Y)
X = sorted(X, key=lambda x:x[1])
Z = [] 
for i in range(N):
    Z.append(0)
    
for i in range(Q):
    Z_1,Z_2 = (int(i) for i in input().split())
    Z[Z_1-1] = Z[Z_1-1] + Z_2

#print(X)
#print(Z)


ans=[Z[0]]

for i in range(1,N):
    ans.append(Z[i])
    for n in range(len(X)):
        if X[n][1] == i+1:
            ans[i] += ans[X[n][0]-1]
            A = n+1
        else:
            for i in range(A):
                X.pop(0)
            break

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
import math
from datetime import datetime


class TreeNode:
    def __init__(self):
        self.val = 0
        self.vertex = []
trees = []
def make_trees(n, A, B):
    global trees
    trees = []
    for i in range(n):
        trees.append(TreeNode())
    for i in range(len(A)):
        a = A[i]-1
        b = B[i]-1
        trees[a].vertex.append(b)
    return trees

def dfs(node: TreeNode, x: int):
    if node:
        node.val += x
        for i in node.vertex:
            dfs(trees[i], x)


def sol(n, q, A, B, P, X):
    make_trees(n, A, B)
    for i in range(len(P)):
        p = P[i]-1
        x = X[i]
        t = trees[p]
        # dfs, give point x
        dfs(t, x)
    #
    return " ".join([str(t.val)  for t in trees])
    #return n, q, A, B, P, X



do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    print(parsed_lines)
    n = int(parsed_lines[0][0])
    q = int(parsed_lines[0][1])
    A = []
    B = []
    P = []
    X = []
    for i in range(1, n-1+1):
        a = int(parsed_lines[i][0])
        b = int(parsed_lines[i][1])
        A.append(a)
        B.append(b)
    for i in range(n, 1+n+q-1):
        p = int(parsed_lines[i][0])
        x = int(parsed_lines[i][1])
        P.append(p)
        X.append(x)

    # S = parsed_lines[1][0]
    # return n, k, S
    return n, q, A, B, P, X


if not do_submit:
    n, q, A, B, P, X = input_parse("""
    4 3
    1 2
    2 3
    2 4
    2 10
    1 100
    3 1
    """)
    print(sol(n, q, A, B, P, X))

    n, q, A, B, P, X = input_parse("""
        6 2
        1 2
        1 3
        2 4
        3 6
        2 5
        1 10
        1 10
    """)
    print(sol(n, q, A, B, P, X))

else:
    # n = int(input().strip())
    # q = int(input().strip())
    n, q = list(map(int, input().split()))
    A = []
    B = []
    P = []
    X = []
    for i in range(n-1):
        a, b = list(map(int, input().split()))
        # a = int(input().strip())
        # b = int(input().strip())
        A.append(a)
        B.append(b)
    for i in range(q):
        p, x = list(map(int, input().split()))
        # p = int(input().strip())
        # x = int(input().strip())
        P.append(p)
        X.append(x)
    print(sol(n, q, A, B, P, X))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():

    N, Q = [int(x) for x in input().split()]
    counter = {key:0 for key in range(1, N+1)}
    parent_dict = dict()
    child_data = defaultdict(list)
    child_data[1] = [1]

    # 要は木構造っぽいものを作りたいが、再起関数だと処理時間で死んだ
    # なので、親一覧 + 自分のリストを作成する
    for _ in range(N - 1):
        a, b = [int(x) for x in input().split()]
        parent_dict[b] = a
        child_data[b].append(b)
        temp = b
        while temp in parent_dict:
            temp = parent_dict[temp]
            child_data[temp].append(b)

    # 親一覧 + 自分のリストから答えを出す   
    for _ in range(Q):
        p, x = [int(x) for x in input().split()]
        for key in child_data[p]:
            counter[key] += x

    print(" ".join([str(val) for key, val in sorted(counter.items())]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#ABC138D
import sys
sys.setrecursionlimit(100000)

tmp = input().split()
n,q = list(map(lambda a: int(a), tmp))

apex=[]
node=[]

node=[]

for i in range(0,n+1):
	node.append([])
	apex.append(0)

for i in range(1,n):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	node[hoge[0]].append(hoge[1])

for i in range(1,q+1):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	apex[hoge[0]]+=hoge[1]

#print(node)
#print(apex)

def calc(j):
	for i in node[j]:
		apex[i]+=apex[j]
		calc(i)

calc(1)
#print(apex)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

link = [None] * N 
for _ in range(N-1):
    a, b = map(int, input().split())
    if link[a-1] is None:
        link[a-1] = [b]
    else:
        link[a-1].append(b)

states = [0] * N
stack = deque()


def dfs(x):
    p = stack.popleft()

    # Add score
    states[p-1] += x
    # Search nexts
    nexts = link[p-1]
    if nexts is None:
        return
    for next_node in nexts:
        stack.append(next_node)


def update(p, x):
    stack.append(p)
    while stack:
        dfs(x)


for _ in range(Q):
    p, x = map(int, input().split())
    update(p, x)

# Output
print(' '.join(map(str, states)))

Submission status: Time Limit Exceeded

Solution code:
line1 = input().split()
n = int(line1[0])
q = int(line1[1])

sahen = [0 for num in range(n)]

for num in range(n-1):
  inp =input().split()
  sahen[num] = int(inp[0])

j = [0 for num in range(q)]
for num in range(q):
  inpt =input().split()
  j[num] = [int(inpt[0]),int(inpt[1])]

result = [0 for num in range(n)]

for num2 in j:
  a1 = num2[0]
  a2 = num2[1]
  if (a1 in sahen):
    for num in range(a1-1,n):
      result[num] += a2
  else:
    result[a1-1] += a2

print(*result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,q = map(int,input().split())
lst = {i+1:[] for i in range(n)}
for _ in range(n-1):
  l,r = map(int,input().split())
  lst[l].append(r)
counter=[0 for _ in range(n)]

for _ in range(q):
  p,x = map(int,input().split())
  temp = [p]
  while len(temp)!=0:
    search_num = temp.pop()
    counter[search_num-1]+=x
    temp+=lst[search_num]
    
ans = ""
for i in counter:
  ans += str(i)+" "
ans = ans[:-1]
print(ans)