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:
# coding: utf-8
from collections import defaultdict
import sys,time

d = defaultdict(list)

n, q = map(int, input().split())
ans = [0]*n

for _ in range(n-1):
    a,b = map(int, input().split())
    d[a].append(b)
    
#print(ans, d)

for i in range(q):
    p, x = map(int, input().split())
    #print(p, x)
    queue = [p]
    while True:
        #print("queue", queue)
        index = queue.pop(0)
        ans[index-1] += x
        tmp_list = d[index]
        if len(tmp_list) != 0:
            #print("tmp_list", tmp_list)
            #print("ans", ans)
            for tmp_d in tmp_list:
                queue.append(tmp_d)
                #print(ans)
        if len(queue) == 0:
            break
        #print(ans)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def solve():
	N, Q = MAP()
	ab = [LIST() for _ in range(N-1)]
	tree = defaultdict(list)
	par = [-1]*N
	par[0] = 0
	for a, b in ab:
		tree[a-1].append(b-1)
		tree[b-1].append(a-1)
	search = []
	searched = [0] * N
	searched[0] = 1
	for child in tree[0]:
		par[child] = 0
		search.append(child)

	while search:
		x = search.pop(0)
		for child in tree[x]:
			if searched[child] == 0:
				par[child] = x
				searched[x] = 1
				search.append(child)

	# def parent(n):
	# 	for child in tree[n]:
	# 		if par[child] == -1:
	# 			par[child] = n
	# 			parent(child)
	# parent(0)
	# print(par)
	px = [LIST() for _ in range(Q)]

	counter = defaultdict(int)  # まとめる
	for p, x in px:
		counter[p-1] += x

	ans = [-1] * N  # 答え入れる
	ans[0] = counter[0]

	search = []
	searched = [0] * N
	searched[0] = 1
	for child in tree[0]:
		par[child] = 0
		search.append(child)

	while search:
		x = search.pop(0)
		ans[x] = counter[x] + ans[par[x]]
		for child in tree[x]:
			if searched[child] == 0:
				par[child] = x
				searched[x] = 1
				search.append(child)

	# def DFS(n):
	# 	if n != 0:
	# 		ans[n] = counter[n] + ans[par[n]]
	# 	for child in tree[n]:
	# 		if ans[child] == -1:
	# 			DFS(child)

	# DFS(0)
	print(*ans, sep=" ")

if  __name__ == "__main__":
	solve()

Submission status: Time Limit Exceeded

Solution code:
N,Q =map(int,input().split())
A = [list(map(int,input().split())) for i in range(N-1)]
C = [list(map(int,input().split())) for i in range(Q)]
A.sort()
C.sort()
lists = [0 for _ in range(N)]
try:
    for k in range(N):
        lists[C[k][0]-1] += C[k][1]
except:
    pass
try:
    for k in range(N):
        lists[A[k][1]-1] +=lists[A[k][0]-1]
except:
    pass
print(' '.join(map(str,lists)))

Submission status: Time Limit Exceeded

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

trees = {}
for _ in range(N - 1):
    id1, id2 = map(int, input().split())
    if id1 not in trees:
        trees[id1] = []
    trees[id1].append(id2)

values = {}
for _ in range(Q):
    nid, val = map(int, input().split())
    if nid not in values:
        values[nid] = 0
    values[nid] += val

counters = {}
stack = [[1, 0]] # id, value from parent
current_val = 0
while len(stack) > 0:
    myid, parent_val = stack.pop()
#     if myid not in counters:
#         counters[myid] = 0
    
    value_add = 0
    if myid in values:
        value_add = values[myid]
    
    counters[myid] = parent_val + value_add
    if myid in trees:
        for cid in trees[myid]:
            stack.append([cid, parent_val + value_add])

ret = []
for myid in range(1, N + 1):
    if myid not in counters:
        ret.append(str(0))
    else:
        ret.append(str(counters[myid]))
        
print(' '.join(ret))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
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)]

chil = [[] for _ in range(N+1)]
count = [0]*(N+1)

for ab in AB:
    chil[ab[0]].append(ab[1])
    chil[ab[1]].append(ab[0])

def cleanse(fromN, toN):
    chil[toN].remove(fromN)
    if len(chil[toN])==0:
        return
    for node in chil[toN]:
        cleanse(toN, node)

for node in chil[1]:
    cleanse(1, node)

def addition(fromN, toN):
    count[toN] += count[fromN]
    if len(chil[toN])==0:
        return
    for node in chil[toN]:
        addition(toN, node)
        
for px in PX:
    count[px[0]] += px[1]

for node in chil[1]:
    addition(1, node)

print(*count[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ab = dict([list(map(int, input().split()))[::-1] for i in range(n-1)])
px = [list(map(int, input().split())) for i in range(q)]
p = [0 for i in range(n)]
for i in px:
  p[i[0]-1] += i[1]
s = ""
for i in range(n):
  a = i+1
  v = 0
  while True:
    v += p[a-1]
    if a == 1:
      break
    a = ab[a]
  s += str(v) + " "
print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, q = map(int, input().split())
child_dict = defaultdict(list)
value_dict = defaultdict(lambda: 0)
rank_dict = defaultdict(lambda: 0)
for _ in range(n - 1):
    a, b = map(int, input().split())
    child_dict[a].append(b)
    rank_dict[b] += rank_dict[a] + 1

for _ in range(q):
    c, d = map(int, input().split())
    value_dict[c] += d
from collections import deque
stack = deque()
top = [k for k, v in rank_dict.items() if v == 0][0]
stack.append(top)
while stack:
    top_ = stack.pop()
    for child in child_dict[top_]:
        value_dict[child] += value_dict[top_]
    stack.extend(child_dict[top_])
ans = [value_dict[i] for i in range(1 ,n+1)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
a = []
for i in range(n-1):
    a.append((input()))
b = []
for j in range(q):
    b.append((input()))
    
aws = []
for k in range(n):
    aws.append(0)
    
def tree(t_num,point):
    aws[t_num - 1] +=  point
    for an in a:
        if t_num == int(an.split()[0]):
            tree(int(an.split()[1]),point)
            
for bn in b:
    t_num = int(bn.split()[0])
    point = int(bn.split()[1])
    tree(t_num,point)
    
for o in aws:
    print(o, end=" ")

Submission status: Time Limit Exceeded

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

class Node:
    def __init__(self, root):
        self.root = root
        self.children = []
        self.val = 0

    def set_root(self, root_node):
        self.root = root_node

    def add_child(self, child_node):
        self.children.append(child_node)
        if self.root is not None:
            self.root.add_child(child_node)

nodes = [Node(None)] * n

for i in range(1, n):
    a, b = map(int, input().split())
    a_node = nodes[a - 1]
    nodes[b - 1] = Node(a_node)
    a_node.add_child(nodes[b - 1])

for j in range(q):
    p, x = map(int, input().split())
    node = nodes[p - 1]
    node.val += x
    children = node.children
    for child in children:
        child.val += x

res = []
for node in nodes:
    res.append(str(node.val))
print(" ".join(res))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,q = map(int,input().split())
graph = [[] for i in range(n)]
cnt = [0] * n

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

for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    cnt[p] += x
    que = deque(graph[p])
    while que:
        c = que.popleft()
        cnt[c] += x
        que += deque(graph[c])       

print(str(cnt).replace('[','').replace(']','').replace(',',''))

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[list(map(int,input().split())) for i in range(b)]
e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[]for i in range(a)]
n=0
i=0
f=[0 for i in range(a)]
h=[]
while n<a:
  n+=1
  m=float("inf")
  for j,k in enumerate(e[i]):
    if f[i]==k:
      m=j
    else:
      f[k]=i
  if m!=float("inf"):
    e[i].pop(m)
  h=h+(e[i])
  g[i]=g[i]+e[i]
  if len(h)!=0:
    i=h.pop()


k=[e[i]+[i]for i in range(a)]
def s(i,g):
  if g[i]==[]:
    return []
  else:
    global k
    for j in g[i]:
      k[i]=k[i]+s(j,g)
    return g[i]
    
  
s(0,g)
h=[0 for i in range(a)]
for i in d:
  for j in k[i[0]-1]:
    h[j]+=i[1]
  
print(" ".join(map(str,h)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
 
def search(i):
    global edge, child, visit
    work= {i}
    visit[i]= True
    #
    for e in edge[i]:
        if visit[e]: continue
        work|= search(e)
    #
    child[i]= work
    return work
 
import sys
 
n,q = [ int(x) for x in sys.stdin.readline().strip().split() ]
n1= n-1
sys.setrecursionlimit(10**6)
#
edge= [ [] for _ in range(n) ]
for i in range(n1):
    a,b = [ int(x)-1 for x in sys.stdin.readline().strip().split() ]
    edge[a].append( b )
    edge[b].append( a )
#
 
visit= [ False for _ in range(n) ]
child= [ set() for _ in range(n) ]
child[0]= { i for i in range(n) }
visit[0]= True
for v in edge[0]: search(v)
#
query= dict()
for i in range(q):
    p,x= [ int(x) for x in sys.stdin.readline().strip().split() ]
    query[p-1]= query.get(p-1,0) + x
#
score= [ 0 for _ in range(n) ]
for p,x in query.items():
    for v in child[p]: score[v]+= x
#
for s in score: print( s,end= " " )

Submission status: Time Limit Exceeded

Solution code:
class TreeObj:
    def __init__(self):
        self.value = 0
        self.childs = []

    def getValue(self):
        return self.value

    def setValue(self, v):
        self.value = v

    def getChilds(self):
        return self.childs

    def addChild(self, node):
        self.childs.append(node)


def appender(tree, v):
    tree.setValue(tree.getValue()+v)
    for child in tree.getChilds():
        appender(child, v)


def main():
    N, Q = list(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)]

    root = TreeObj()  # 1
    trees = {1: root}   # 1
    for a, b in AB:
        if (a not in trees):
            trees[a] = TreeObj()

        tree = trees[a]
        if (b not in tree.getChilds()):
            child = TreeObj()
            trees[b] = child
            tree.getChilds().append(child)

        tree = None

    for p, x in PX:
        tree = trees[p]
        appender(tree, x)

    tmp = [str(trees[key].getValue()) for key in trees.keys()]
    print(' '.join(tmp))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue

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

P = []
X = []
for _ in range(Q):
    p,x = map(int,input().split(" "))
    P.append(p)
    X.append(x)

ans = [0]*N
q = queue.LifoQueue()
q.put(1)
while q.empty() != True:
    d = q.get()
    tmp_b = []
    for a,b in zip(A,B):
        if d == a:
            tmp_b.append(b)
            q.put(b)

    for p,x in zip(P,X):
        if d == p:
            ans[p-1] += x

    for b in tmp_b:    
        ans[b-1] += ans[d-1]
text = ""

for t in ans:
    text += "{} ".format(t)

print(text[:-1])

Submission status: Time Limit Exceeded

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

ans = [0] * n

def dfs(cur, pre, point):
    point += d2[cur]
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#ABC138D
import copy
import sys
import math

sys.setrecursionlimit(100000)

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

a=[]
b=[]
apex=[]
node=[]

apex.append(0)

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

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

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:
n, q = map(int, input().split())
tl = [list() for _ in range(n)]
ab = [None] * (n-1)
ans = [0] * n

for i in range(n-1):
    ab[i] = tuple(map(int, input().split()))

ab.sort(reverse=True)

for a, b in ab:
    a -= 1
    b -= 1
    tl[a].append(b)
    tl[a].extend(tl[b])

for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x
    if len(tl[p-1]) > 0:
        for num in tl[p-1]:
            ans[num] += x

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

Submission status: Time Limit Exceeded

Solution code:
#from collections import deque

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

a = [0] * (n-1)
b = [0] * (n-1)
info = [[] for _ in range(n)]

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

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


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

plus = [0] * n

for j in range(q):
    plus[p[j]] += x[j]

state = [0] * n
state[0] = 1
cur = [0]

child = [[] for _ in range(n)]
par = [0] * n

ranklist = [[1]]

#print(cur)
#print(info)

while cur != []:
    cur2 = []
    ranklist.append([])
    for obj in cur:
        for obj2 in info[obj]:
            if state[obj2] == 0:
                state[obj2] = 1
                #child[obj].append(obj2)
                par[obj2] = obj
                cur2.append(obj2)
                ranklist[-1].append(obj2)
    cur = cur2[:]

ans = [0] * n
ans[0] = plus[0]

for l in ranklist:
    for t in l:
        ans[t] = ans[par[t]] + plus[t]

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

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,0] for num in range(q)]
result = [0 for num in range(n)]

for num in range(q):
  inpt =input().split()
  if (int(inpt[0]) in sahen):
    for num in range(int(inpt[0])-1,n):
      result[num] += int(inpt[1])
  else:
    result[int(inpt[0])-1] += int(inpt[1])

print(*result)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n, m= map(int, input().split())

links = []

sums = [0] * (n + 1)

for _ in range(n - 1):
  a, b= map(int, input().split())
  heapq.heappush(links, [a,b])

uppers = [[x] for x in range(n + 1)]
oya = {}
for l in links:
  # uppers[l[0]].append(l[1])
  oya[l[1]] = l[0]
  up = l[0]
  while True:
    if up not in oya:
      # print(up)
      uppers[up].append(l[1])
      break
    else:
      uppers[up].append(l[1])
      up = oya[up]
# print(uppers)
# print(oya)

for _ in range(m):
  p, x = map(int, input().split())
  for up in uppers[p]:
    sums[up] += x

print(*sums[1:])

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
ans = [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])

# print("bb=",bb)
# print("ll=",ll)
for i in range(N):
    for k in range(len(bb[i])):
        if k == 0 :
            ans[i] += ll[i]
        else:
            ll[bb[i][k]-1] += ll[i]
print(*ans)

Submission status: Time Limit Exceeded

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

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

#print(edges)

task = [[] for _ in range(N+1)]
for i in range(Q):
    p, x = map(int, input().split())
    task[p].append(x)

#rint(task)

task_sum = [[] for _ in range(N+1)]
for i in range(N+1):
    task_sum[i].append(sum(task[i]))

#print('task_sum:', task_sum)

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

#print(cnt)

#最初はdfs(1, -1, task_sum[1])

def dfs(v, p, cost):
        
    for nv in edges[v]:
        if nv == p:
            continue
        
        dfs(nv, v, cost+task_sum[nv])

    cnt[v].append(cost)

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

#print(cnt)
for i in range(1, N+1):
    print(int(sum(cnt[i][0])), end=' ')

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(10000000)

n, q = map(int, input().split())
g = []
o = []
counter = []
for i in range(n+1):
  counter.append(0)
  o.append(0)
  g.append([])

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]
  flag = False
  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:
n, q = map(int, input().split())
a = []
b = []
hens = []
for i in range (n-1):
  t_a, t_b = map(int, input().split())
  a.append(t_a-1)
  b.append(t_b-1)
  hens.append([t_a-1, t_b-1])
p = []
x = []
for i in range (q):
  t_p, t_x = map(int, input().split())
  p.append(t_p-1)
  x.append(t_x)
c = [0 for i in range(n)]
tree = [[None, [], False] for i in range(n)]
tree[0][2] = True

while(len(hens) >= 1):
  for hen in hens[:]:
    if tree[hen[0]][2] == True:
      tree[hen[0]][1].append(hen[1])
      tree[hen[1]][0] = hen[0]
      tree[hen[1]][2] = True
    elif tree[hen[1]][2] == True:
      tree[hen[1]][1].append(hen[0])
      tree[hen[0]][0] = hen[1]
      tree[hen[0]][2] = True
    hens.remove(hen)
"""
while(1):
  for hen in range(n-1):
    if tree[a[hen]][2] == True:
      tree[a[hen]][1].append(b[hen])
      tree[b[hen]][0] = a[hen]
      tree[b[hen]][2] = True
    elif tree[b[hen]][2] == True:
      tree[a[hen]][1].append(a[hen])
      tree[a[hen]][0] = b[hen]
      tree[a[hen]][2] = True
  finish = True
  for peak in tree:
    if peak[2] == False:
      finish = False
      break
  if finish == True:
    break
"""

def calc(p, x, ret):
  if len(tree[p][1]) == 0:
    ret[p] += x
  else:
    for child in tree[p][1]:
      ret = calc(child, x, ret)
    ret[p] += x
  return ret

ans = [0 for i in range(n)]
for i in range(q):
  t_c = calc(p[i], x[i], [0 for i in range(n)])
  ans = list(map(lambda x,y: x+y, ans, t_c))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

sys.setrecursionlimit(100000)
def calc(p, x, li, ans):
    ans[p] += x
    l = len(li[p])
    for i in range(l):
        calc(li[p][i], x, li, ans)


n, q = na()
li = [[] for i in range(n)]
ans = [0 for k in range(n)]

for i in range(n-1):
    a, b = na()
    li[a-1].append(b-1)

for j in range(q):
    p, x = na()
    calc(p-1, x, li, ans)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

plus_dic = defaultdict(int)
AB_lst = [list(map(int, input().split())) for _ in range(N - 1)]
AB_lst = sorted(AB_lst, key=lambda x: x[1])
PX_lst = [list(map(int, input().split())) for _ in range(Q)]

for p, x in PX_lst:
    plus_dic[p] += x

out_lst = [0] * (N + 1)
out_lst[1] = plus_dic[1]

for a, b in AB_lst:
    out_lst[b] = plus_dic[b] + out_lst[a]

print(*out_lst[1:])

Submission status: Time Limit Exceeded

Solution code:
N,Q =map(int,input().split())
A = sorted([list(map(int,input().split())) for i in range(N-1)])
C = sorted([list(map(int,input().split())) for i in range(Q)])
lists = [0 for _ in range(N)]
try:
    for k in range(N):
        lists[C[k][0]-1] += C[k][1]
except:
    pass
try:
    for k in range(N):
        lists[A[k][1]-1] +=lists[A[k][0]-1]
except:
    pass
print(' '.join(map(str,lists)))

Submission status: Time Limit Exceeded

Solution code:
import sys
 
sys.setrecursionlimit(200000000)
 
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)]
 
l = [[] for i in range(n+1)]
for pi in ab:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])

l_2 = [0 for i in range(n+1)]
for p, x in px:
    l_2[p] += x
'''
def dfs(graph, start, oya):
    if start != 1:
        graph[start].remove(oya)
    if len(graph[start]) == 0:
        return
    else:
        for i in graph[start]:
            dfs(graph, i, start)
 
dfs(l, 1, 1)
'''
 
def dfs_2(graph, start, ans, oya, x, l_2):
    ans[start] += x
    if len(graph[start]) == 1 and start == oya:
        return
    else:
        for i in graph[start]:
            if i != oya:
                dfs_2(graph, i, ans, start, x+l_2[i], l_2)
 
ans = [0 for i in range(n+1)]
dfs_2(l, 1, ans, 0, l_2[1], l_2)
        
for i in range(1, n+1):
    print(ans[i], end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def s_list(): return list(input())
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def num__grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]#NumberGrid
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]

n, q = wi()
ab = mi(n - 1)
px = mi(q)
numdict = {}
for i in range(n + 1):
    numdict[i] = []

parli = [0 for i in range(n + 1)]
parli[1] = 1
for i in range(n - 1):
    if parli[ab[i][0]] == 0:
        parli[ab[i][0]] = 1
    else:
        numdict[ab[i][0]].append(ab[i][1])
    if parli[ab[i][1]] == 0:
        parli[ab[i][1]] = 1
    else:
        numdict[ab[i][1]].append(ab[i][0])

numli = [0 for i in range(n + 1)]

plsdict = defaultdict(int)
for i in range(q):
    plsdict[px[i][0]] += px[i][1]

for i in range(1, n + 1):
    numli[i] += plsdict[i]



queue = deque()
queue.append(1)
while queue != deque():
    po = queue.popleft()
    for kk in numdict[po]:
        queue.append(kk)
        numli[kk] += numli[po]

for i in range(1, n + 1):
    print(numli[i],"" , end="")

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 = 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
global vis
vis = 0

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


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

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
tree = [[int(i) for i in input().split()] for i in range(n-1)] 
px = [[int(i) for i in input().split()] for i in range(q)] 
calc_tree = [[] for i in range(n)]

for i in range(n)[::-1]:
  if calc_tree[i] == []:
    
    tmp = [i+1]
  
    for j in range(n-1)[::-1]:
      if tree[j][1] in tmp:
        tmp.append(tree[j][0])
    calc_tree[i] = tmp
    for j in range(1,len(tmp)):
      if calc_tree[j] == []:
        for k in range(j,len(tmp)):
          calc_tree[tmp[j]-1].append(tmp[k])
  
    calc_tree[i] = (tmp)


ans = [0] * n
  
for i in px:
  for j in range(n):
    if i[0] in calc_tree[j]:
      ans[j] += i[1]
    
for i in ans:
  print(i,end=' ')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, q = map(int, input().split())
#g = np.zeros((n+1,n+1))

#ans = np.zeros((n)) #Do not Foget -1

g = [[0 for i in range(n+1)] for j in range(n+1)]
ans = [0] * n #np.zeros(n) #Do not Foget -1

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

#for i in range(n+1):
#    print(g[0])


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

    stack = []
    ans[q-1] += x
    for i in range(n+1):
        if g[q][i] == 1:
            stack.append(i)

    while len(g) > 0:
        if len(stack) <= 0:
            break
        p = stack.pop(-1)
        #print(p)
        ans[p-1] += x
        for i in range(n+1):
            if g[p][i] == 1:
                stack.append(i)

ans_str = str(ans)
ans_str = ans_str.replace('[','').replace(']','').replace(',','')
print(ans_str)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
tree_list = []
count_list = [0]*N

def make_tree(a,b):
  if len(tree_list) == 0:
    tree_list.append([a,b])
    tree_list.append([b])
  else:
    for i in range(len(tree_list)):
      if a in tree_list[i]:
        tree_list[i].append(b)
      if i == len(tree_list)-1:
        tree_list.append([b])
def count(num,x):
  for i in tree_list[num]:
    count_list[i-1] +=x
for i in range(N-1):
  a,b = map(int,input().split())

  make_tree(a,b)
for i in range(Q):
  p,x = map(int,input().split())
  tree_num = tree_list[0].index(p)
  count(tree_num,x)
count_list = [str(i) for i in count_list]
print(" ".join(count_list))

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
a = []
p = []
x = [0]*(N)
A = [0]*(N)

for i in range(N-1):
    t=list(map(int,input().split()))
    if t[0]>t[1]:
        swap = t[1]
        t[1] = t[0]
        t[0] =swap
    a.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=list(map(int,input().split()))
    p.append((int(t[0]),int(t[1])))

a =sorted(a, key=lambda x: x[0])
p =sorted(p, key=lambda x: x[0])

#print(a)
for i in range(Q):
    x[p[i][0]-1] += p[i][1]
for i in range(N):
    A[i] = x[i]
for i in range(N-1):
    La = a[i][0]-1
    Lb = a[i][1]-1

    A[Lb] = A[La]+x[Lb]

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

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split(" "))
ab=[list(map(int,input().split(" "))) for i in range(N-1)]
px=[list(map(int,input().split(" "))) for i in range(Q)]

cnt=[0 for i in range(N)]
for q in range(Q):
#    che=[False for i in range(N)]
#    che[px[q][0]-1]=True
    che=[px[q][0]-1]
    cnt[px[q][0]-1]+=px[q][1]
    for i in range(N-1):
        if ab[i][0]-1 in che:
            che.append(ab[i][1]-1)
            cnt[ab[i][1]-1]+=px[q][1]

print(" ".join(repr(i) for i in cnt))