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
def main():
    n,q = map(int, input().split())

    ab= [list(map(int, input().split())) for _ in range(n-1)]
    px= [list(map(int, input().split())) for _ in range(q)]
    score = [0]*n

    for px_ in px:
        start = int(px_[0])
        child = []
        child.append(start)

        for ab_ in ab:
            if ab_[0] == start or ab_[0] in child:
                child.append(int(ab_[1]))
                
        for i in child:
            score[int(i)-1] += px_[1]

    print(' '.join([str(j) for j in score]))


if __name__ == '__main__' :
    main()

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 

ans = [0] * N
visited = [False] * N
ans[0] = point_root[0]
visited[0] = True
def solve(node, point):
    ans[node] = point
    visited[node] = True
    if all(visited) == True:
        print(*ans)
        exit()

    if es.get(node, None) != None:
        next_nodes = copy.deepcopy(es[node]) # これからポイントを足し行くやつら

        for i in next_nodes:
            solve(i, point+point_root[i])
solve(0, point_root[0])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PQ = [list(map(int,input().split())) for _ in range(Q)]
AB.sort()
PQ.sort()
l=[[] for _ in range(N)]
ans=[0]*N
for a,b in reversed(AB):
	l[a-1].append(b)
	l[a-1].extend(l[b-1])
for p,q in PQ:
	ans[p-1]+=q
	for i in l[p-1]:
		ans[i-1]+=q
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, Q = map(int,input().split())
edge_from = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge_from[a].append(b)
tmp = defaultdict(int)
for i in range(Q):
    p, x = map(int,input().split())
    tmp[p-1] += x
q = dict()
head = 0
tail = 1
q[0] = (0, 0)
while head < N:
    p, x = q[head]
    x += tmp[p]
    tmp[p] = x
    head += 1
    for nx in edge_from[p]:
        q[tail] = (nx, x)
        tail += 1
for i in range(N):
    print(tmp[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

N,Q = map(int,input().split())
AB_list = [list(map(int,input().split())) for i in range(N-1)]
target_list = [list(map(int,input().split())) for i in range(Q)]
#X_list = list(map(int,input().split()))
#X1_list = [int(input()) for i in range(N)]
#X2_list = [list(map(int,input().split())) for i in range(N)]
'''
target = 1
{
1 : {
value:0,
child:[2,3]
}
}

A_tree ={
    AB_list[0][0] :{
        'value': 0,
        'child': [AB_list[0][1]]
    }
}
'''

A_tree ={}
for i in range(0,N-1):
    #print(A_tree.get(AB_list[i][0]),i)
    if A_tree.get(AB_list[i][0]) and i != 0:
        A_tree.get(AB_list[i][0]).get('child').append(AB_list[i][1])
    else:
        A_tree[AB_list[i][0]] = {
            'value' : 0,
            'child' : [AB_list[i][1]],
        }

def recursivePlus(target,_value):
    if A_tree.get(target) is None:
        A_tree[target] = {
            'value' : _value,
            'child' : [],
        }
        return
    #print(A_tree.get(target))
    A_tree.get(target)['value'] += _value
    for c in A_tree.get(target)['child']:
        recursivePlus(c,_value)

for i in range(0,Q):
    recursivePlus(target_list[i][0],target_list[i][1])

for a in A_tree.items():
    print(a[1]['value'],end=' ')

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)

counters = {}
for _ in range(Q):
    nid, val = map(int, input().split())
    stack = [nid]
    while len(stack) > 0:
        myid = stack.pop()
        if myid not in counters:
            counters[myid] = 0
        counters[myid] += val
        if myid in trees:
            stack.extend(trees[myid])

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:
N, Q = map(int, input().split())

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

    if a not in tree_dict:
        tree_dict[a] = [b]
    else:
        tree_dict[a].append(b)

value_dict = {k:0 for k in list(set(ab_list))}

px_dict = {}
for i in range(Q):
    p, x = map(int, input().split())
    if p in px_dict:
        px_dict[p] += x
    else:
        px_dict[p] = x

for p, x in px_dict.items():
    kk_list = [p]
    while(1):
        k = kk_list[0]
        value_dict[k] += x
        if k in tree_dict:
            kk_list += tree_dict[k]
        kk_list.pop(0)
        if len(kk_list) == 0:
            break

print(' '.join([str(v) for k, v in value_dict.items()]))

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
for i in range(1, n+1):
    pi = 0
    j = i
    while True:
        pi += tpoint[j]
        if parray[j] == -1:
            break
        j = parray[j]
    print(pi)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
T = [[0, 0, []] for _ in range(N+1)] #counter, parent, children
E = sorted([list(map(int, input().split())) for _ in range(N-1)], key=lambda x:x[0])
for e in E:
  p = e[0] if e[0] in T[1][2] else e[1]
  if 1 in e:
    p = 1
  c = e[0]+e[1]-p
  T[c][1]=p
  while True:
    T[p][2].append(c)
    if p == 1:
      break
    p = T[p][1]
for _ in range(Q):
  p, x = map(int, input().split())
  T[p][0] += x
  for c in T[p][2]:
    T[c][0] += x
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)

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)]
ab = sorted(ab, reverse=True)
pq = [list(map(int,input().split())) for i in range(Q)]
tree = {}
ans = [0]*N

for pair in ab:
    if pair[0] not in tree:
        tree[pair[0]] = [pair[1]]
    else:
        tree[pair[0]].append(pair[1])
    if pair[1] in tree:
        for i in range(len(tree[pair[1]])):
            tree[pair[0]].append(tree[pair[1]][i])

for pair in pq:
    ans[pair[0]-1] += pair[1]
    if pair[0] in tree:
        for i in tree[pair[0]]:
            ans[i-1] += pair[1]
for i in ans:
    print(i, end=' ')

print()

Submission status: Time Limit Exceeded

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

# input
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)]

# solve
ans = [0] * N
tree = [[] for i in range(N)]
for i in range(N):
    tree[0].append(i)
for i in range(1, N):
    tree[i].append(i)
for i in range(N - 1):
    if ab[i][0] != 1:
        tree[ab[i][0] - 1].append(ab[i][1] - 1)

for i in range(Q):
    point = px[i][0]
    for j in tree[point - 1]:
        ans[j] += px[i][1]

# output
for i in range(N):
    if i == N - 1:
        print(ans[i])
    else:
        print(ans[i], end=' ')

Submission status: Time Limit Exceeded

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

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

ans = [0 for _ in range(n)]
visit = [False for _ in range(n)]

def rec(pos, val):
    val += cnt[pos]
    ans[pos] = val
    for to in edges[pos]:
        if not visit[to]:
            visit[to] = True
            rec(to, val)

visit[0] = True
rec(0, 0)
for x in ans[:-1]:
    print(x, end=' ')
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:


import sys
sys.setrecursionlimit(500000)

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


def search(n):
    global P,res,visited

    for l in L[n]:
        res[l]=res[n]+P[l]
        search(l)

N,Q=acinput()

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

for i in range(N-1):
    tmp=acinput()
    L[tmp[0]].append(tmp[1])

P=[0]*(N+1)
for i in range(Q):
    tmp=acinput()
    P[tmp[0]]+=tmp[1]

res=[0]*(N+1)
res[1]=P[1]
search(1)

print(" ".join(map(str,res[1:])))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
#n=6
#q=2
ab = [list(map(int, input().split())) for _ in range(n-1)]
#ab=[[1,2],[1,3],[2,4],[3,6],[2,5]]
px = [list(map(int, input().split())) for _ in range(q)]
#px=[[1,10],[1,10]]
#print(ab)
#print(px)
ans= [[0 for i in range(n)] for i in range(n)]
ans2= [0 for i in range(n)]
a=[]
for i in range(n):
    ans[i][i] = 1
for i in range(len(ab)):
    ans[ab[i][0]-1][ab[i][1]-1]+=1
    a.append(ab[i][0]-1)
a=set(a)
a=sorted(a, reverse=True)
#print(a)
for i in a:
    for j in range(i+1,n):
        if(ans[i][j]>0):
            for k in range(j,n):
                ans[i][k]+=ans[j][k]
for i in range(q):
    for j in range(n):
        ans2[j]+=px[i][1]* 1 if ans[px[i][0]-1][j] else 0
print(" ".join(list(map(str,ans2))))

Submission status: Time Limit Exceeded

Solution code:
line = input().split()
N = int(line[0])
Q = int(line[1])
g = {}
g2 = {}
for i in range(N-1):
    r = input().split()
    a = int(r[0])
    b = int(r[1])
    if not a in g:
        g[a] = [b]
    else:
        g[a].append(b)
    g[b] = []
    g2[b] = a
    tmpa = a
    while tmpa in g2:
        p = g2[tmpa]
        g[p].append(b)
        tmpa = p

suma = [0 for i in range(N)]
for i in range(Q):
    row = input().split()
    p = int(row[0])
    x = int(row[1])
    nodes = g[p]
    suma[p-1] += x
    for n in nodes:
        suma[n-1] += x


for i in range(0,N-1):
    print(suma[i], end=' ')
print(suma[N-1])

Submission status: Time Limit Exceeded

Solution code:
class Node:
  def __init__(self):
    self.counter = 0
    self.childs = []
  def add_child(self, node):
    self.childs.append(node)

N, Q = [int(i) for i in input().split()]
ndic = {}
for i in range(1, N+1):
  ndic[i] = Node()
for i in range(N-1):
  a, b = [int(i) for i in input().split()]
  ndic[a].add_child(ndic[b])

for i in range(Q):
  p, x = [int(i) for i in input().split()]
  stack = []
  stack.append(ndic[p])
  while(len(stack) > 0):
    node = stack.pop()
    node.counter += x
    for n in node.childs:
      stack.append(n)
ans = ""
for k, v in ndic.items():
  ans += str(v.counter) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(i) for i in input().split())
ab = [[int(i) for i in input().split()] for _ in range(n-1)]
child_dict = {}
for i in range(n-2,-1,-1):
    cur = child_dict.get(ab[i][0],set({}))
    cur.add(ab[i][1])
    child_dict[ab[i][0]] = cur
px = [[int(i) for i in input().split()] for _ in range(q)]

p = [0] * n

for j in range(q):
    rootidx = px[j][0]
    p[rootidx - 1] += px[j][1]
    if rootidx in child_dict.keys():
        for k in child_dict[rootidx]:
            p[k-1] += px[j][1]
            while k in child_dict.keys():
                for l in child_dict[k]:
                    p[l-1] += px[j][1]
                k = l
print(*p)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def calc_results(results, pvalue, i):
  results[i] = pvalue + values[i]
  if childrens[i] is None:
    return
  for j in childrens[i]:
    calc_results(results, results[i], j)
n, q = map(int, input().split())
values = [0] * (n + 1)
results = [0] * (n + 1)
childrens = [None] * (n + 1)
dc = [None for i in range(0, n + 1)]
for i in range(n - 1):
  a, b = map(int, input().split())
  if childrens[a] is None:
    childrens[a] = []
  childrens[a].append(b)
for _ in range(q):
  p, x = map(int, input().split())
  values[p] += x
calc_results(results, 0, 1)
print(*[results[i] for i in range(1, n + 1)])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
graph = {i:[] for i in range(N)}
G = {i:[] for i in range(N)}
ans = [0 for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  graph[a-1] += [b-1]
  graph[b-1] += [a-1]
stuck = [0]
log = [0 for i in range(N)]
log[0]=1
ls = [0]
while stuck:
  x = stuck.pop()
  A = graph[x]
  flag = True
  ki = []
  for a in A:
    if log[a]==0:
      stuck += [a]
      ki+=[a]
      log[a]=1
      flag = False
  for l in ls:
    G[l] += ki
  ls += ki
  if flag:
    ls.remove(x)
for i in range(Q):
  p, x = map(int,input().split())
  p = p-1
  for l in G[p]:
    ans[l] += x
  ans[p] += x
A = map(str, ans)
print(' '.join(A))

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self, index):
        self.count = 0
        self.fr = -1
        self.index = index


N, Q = map(int, input().split())
node = [Node(i) for i in range(N)]
for i in range(N - 1):
    fr, to = map(int, input().split())
    node[to - 1].fr = fr - 1

for i in range(Q):
    fr, c = map(int, input().split())
    node[fr- 1].count += c

for i in range(N):
    x = node[i].count
    next = node[i].fr
    while next != -1:
        x += node[next].count
        next = node[next].fr
    if not i == N:
        print(x, end=' ')
    else:
        print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, q = map(int, input().split( ))
Edg=[[] for i in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split( ))
    Edg[a].append(b)
Ans=[0 for i in range(n+1)]
P = [0 for i in range(n+1)]
for i in range(q):
    p, x = map(int, input().split( ))
    P[p]+=x
#print(*P)
Chld=[[] for i in range(n+1)]
for p in range(n+1):
    Task=deque()
    Task.append(p)
    while True:
        try:
            p_=Task.popleft()
            for child in Edg[p_]:
                Chld[p].append(child)
                Task.append(child)
        except:
            break
#print(Chld)
for p in range(n+1):
    tmp = P[p]
    Ans[p]+=tmp
    for c in Chld[p]:
            Ans[c]+=tmp

print(*Ans[1:])

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])
 
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, x):
    ans[start] += x
    if len(graph[start]) == 0:
        return
    else:
        for i in graph[start]:
            dfs_2(graph, i, ans, x)
 
ans = [0 for i in range(n+1)]
for p, x in px:
    dfs_2(l, p, ans, x)
        
for i in range(1, n+1):
    print(ans[i], end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
v = input()
v = [int(x.strip()) for x in v.split(" ")]
n = v[0]
q = v[1]

p = [[0]*2]*(n-1)
for i in range(n-1):
    v=input()
    p[i] = [int(x.strip()) for x in v.split(" ")]

c = [0] * n

def func(s, y):
    c[s] += y
    for i in range(len(p)):
        if p[i][0] == s+1:
            func(p[i][1]-1,y)
    return

x = [[0]*2]*q
for i in range(q):
    v=input()
    x[i] = [int(a.strip()) for a in v.split(" ")]
    func(x[i][0]-1,x[i][1])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import collections
import bisect
import fractions
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
mod=1000000007
pi=3.1415926535897932
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
# fractions.gcd(x,y)
def lcm(a,b): return a*b//fractions.gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def eof(t): print(t); exit()

def qul(p):
    if p in d:
        for j in d[p]:
            if j in d:
                if j not in l:
                    l.append(j)
                qul(j)
            else:
                l.append(j)
d={}
n,q=map(int,input().split())
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a]=[b]
w=[0]*(n+1)
for i in d:
    d[i].sort(reverse=True)
for i in range(q):
    p,x=map(int,input().split())
    w[p]+=x
for i in range(n,0,-1):
    l=[]
    qul(i)
    for j in l:
        w[j]+=w[i]
    #print(i,l)
print(*w[1:])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

sys.setrecursionlimit(200000)

n,q = (int(num) for num in input().split())
par = [i for i in range(n)]
nex = [[] for _ in range(n)]
ch = [0] * n
rank = [0] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    if a > b:
        a,b = b,a
    ab.append((a,b))
ab.sort(key = lambda x: x[0])
    
for item in ab:
    a = item[0]
    b = item[1]
    if rank[a] > rank[b]:
        nex[a].append(b)
        rank[a] = max(rank[a],rank[b])
    elif rank[a] < rank[b]:
        nex[b].append(a)
        rank[b] = max(rank[b],rank[a])
    elif a < b:
        nex[a].append(b)
        rank[a] += 1
    else:
        nex[b].append(a)
        rank[b] += 1
        
#print(par)
#print(nex)
#print(rank)

for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x
    
def calc(idx,nex,val,bias):
    val[idx] += bias
    if nex[idx] == []:
        return
    else:
        for i in nex[idx]:
            calc(i,nex,val,val[idx])
        
calc(0,nex,val,0)    
ans = ""    
for num in val:
    ans += str(num) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,q = map(int,input().split())
lst = []
for _ in range(n-1):
  lst.append(list(map(int,input().split())))
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
    for i in range(len(lst)):
      if lst[i][0] == search_num:
        temp.append(lst[i][1])
ans = " ".join([str(i) for i in counter])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,Q=list(map(int,input().split()))
a=[]
b=[]
for i in range(N-1):
	m,n=list(map(int,input().split()))
	a.append(m)
	b.append(n)
p=[]
x=[]
for i in range(Q):
	m,n=list(map(int,input().split()))
	p.append(m)
	x.append(n)


def trav(z):
	if z not in a:
		child[z-1].append(z)
		return([z])
	else:
		m=[z]
		for i in range(N-1):
			if a[i]==z:
				m=m+trav(b[i])
		child[z-1]=m
		return(m)

child=[]
for i in range(N):
	child.append([])
trav(1)

ans=[0]*N
for i in range(Q):
	for j in range(len(child[p[i]-1])):
		ans[child[p[i]-1][j]-1]+=x[i]

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

Submission status: Time Limit Exceeded

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

ct = [0] * (n + 1)
target = [[i] for i in range(n + 1)]

for _ in range(n - 1):
    a, b = map(int, input().split())
    for t in target:
        if a in t:
            t.append(b)

for _ in range(q):
    p, q = map(int, input().split())
    t = target[p]
    for ti in t:
        ct[ti] += q

print(*ct[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, q = map(int, input().split( ))
Edg=[[] for i in range(n+1)]
##
for i in range(n-1):
    a, b = map(int, input().split( ))
    Edg[a].append(b)
Ans=[0 for i in range(n+1)]
P = [0 for i in range(n+1)]
for i in range(q):
    p, x = map(int, input().split( ))
    P[p]+=x
#print(*P)
Chld=[[] for i in range(n+1)]
for p in range(n+1):
    Task=deque()
    Task.append(p)
    while True:
        try:
            p_=Task.popleft()
            for child in Edg[p_]:
                Chld[p].append(child)
                Task.append(child)
        except:
            break
#print(Chld)
for p in range(n+1):
    tmp = P[p]
    Ans[p]+=tmp
    for c in Chld[p]:
            Ans[c]+=tmp

print(*Ans[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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):
#    print('fromN:', fromN)
#    print('toN:', toN)
    chil[toN].remove(fromN)
    if len(chil[toN])==0:  # leaf
        return
    for node in chil[toN]:
        cleanse(toN, node)

#print(chil)

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

def addition(fromN, toN, value):
#    print('fromN:', fromN)
#    print('toN:', toN)
    count[toN] += value
    if len(chil[toN])==0:
        return
    for node in chil[toN]:
        addition(toN, node, value)

#print(chil)

for px in PX:
    count[px[0]] += px[1]
    for node in chil[px[0]]:
        addition(px[0], node, px[1])

print(*count[1:])

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)]
px.sort()

ans = [0]*(n+1)
for i in range(q):
  if px[i][0]==1:
    ans[1] += px[i][1]
    
  for j in range(n-1):
    if ab[j][1] == px[i][0]:
      ans[px[i][0]] += ans[ab[j][0]] + px[i][1]
      
for k in range(1,n+1):
  if ans[k]==0:
    for x in range(n-1):
      if ab[x][1] == k:
          ans[k] += ans[ab[x][0]]

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

Submission status: Time Limit Exceeded

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

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

M = [[0] * N for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    M[a-1][b-1] = M[b-1][a-1] = 1

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

ans = [0] * N

def setAnswer(parent, number, value):
    ans[number] = value

    for i in range(N):
        if i != parent and M[number][i] == 1:
            setAnswer(number, i, value + X[i])

setAnswer(0, 0, X[0])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

N,Q = map(int,input().split())
AB_list = [list(map(int,input().split())) for i in range(N-1)]
target_list = [list(map(int,input().split())) for i in range(Q)]
#X_list = list(map(int,input().split()))
#X1_list = [int(input()) for i in range(N)]
#X2_list = [list(map(int,input().split())) for i in range(N)]
'''
target = 1
{
1 : {
value:0,
child:[2,3]
}
}

A_tree ={
    AB_list[0][0] :{
        'value': 0,
        'child': [AB_list[0][1]]
    }
}
'''

A_tree ={}
for i in range(0,N-1):
    #print(A_tree.get(AB_list[i][0]),i)
    if A_tree.get(AB_list[i][0]) and i != 0:
        A_tree.get(AB_list[i][0]).get('child').append(AB_list[i][1])
    else:
        A_tree[AB_list[i][0]] = {
            'value' : 0,
            'child' : [AB_list[i][1]],
        }

def recursivePlus(target,_value):
    if A_tree.get(target) is None:
        A_tree[target] = {
            'value' : _value,
            'child' : [],
        }
        return
    #print(A_tree.get(target))
    A_tree.get(target)['value'] += _value
    for c in A_tree.get(target)['child']:
        recursivePlus(c,_value)

for i in range(0,Q):
    recursivePlus(target_list[i][0],target_list[i][1])

for a in A_tree.items():
    print(a[1]['value'],end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, Q = map(int,input().split())
edge_from = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge_from[a].append(b)
tmp = [0]*N
for i in range(Q):
    p, x = map(int,input().split())
    tmp[p-1] += x
q = [None]*N
head = 0
tail = 1
q[0] = (0, 0)
while head < N:
    p, x = q[head]
    x += tmp[p]
    tmp[p] = x
    head += 1
    for nx in edge_from[p]:
        q[tail] = (nx, x)
        tail += 1
for i in range(N):
    print(tmp[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

d = deque()
def f(tree, counter, arr, n):
  global d
  if not arr:
    return
  for pp in arr if type(arr) == list else arr.popleft():
    if isinstance(tree[pp], list):
      if tree[pp]:
        d.append(tree[pp])
    counter[pp] += n
  if d:
    return f(tree, counter, d, n)

def main():
  N, Q = na()

  tree = [[] for _ in range(N+1)]
  for _ in range(N-1):
    a, b = na()
    tree[a] += [b]

  counter = [0] * (N+1)
  for _ in range(Q):
    p, x = na()
    f(tree, counter, tree[p], x)
    counter[p] += x
  print(*counter[1:])

if __name__ == "__main__":
  import sys
  sys.setrecursionlimit(10000000)

  stdin = sys.stdin
  na = lambda: map(int, stdin.readline().split())
  main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]

neigh = {}

for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])

sortKey = sorted(neigh.keys(), reverse=True)

for i in range(len(sortKey)) :
    for j in range(i + i, len(sortKey)) :
        if sortKey[i] in neigh[sortKey[j]] :
            neigh[sortKey[j]] += neigh[sortKey[i]]
            break

ans = [0] * n
#print(neigh)
#print(neigh)

for i in range(q) :
    if px[i][0] in neigh :
        for e in neigh[px[i][0]] :
            ans[e - 1] += px[i][1]
    ans[px[i][0] - 1] += px[i][1]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:

N,Q = map(int,input().split())
edges = [[] for _ in range(200001)]
for n in range(N-1):
	a,b = map(int,input().split())
	edges[a-1].append(b-1)
#edges.sort()
#print(edges)

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

for n in range(N):
	print('{} '.format(counters[n]),end='')
	for e in edges[n]:
		counters[e] += counters[n]

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)

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


# make a function
def add(lst, p, x):
    if child[p] == []:
        lst[p] += x
    else:
        lst[p] += x
        for v in child[p]:
            add(lst, v, x)

## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    add(count, p, x)
    
print(' '.join(map(str, count)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000) 

class Node:
    def __init__(self, data): #コンストラクタ
        self.data = data 
        self.kodomo = []
        self.cnt = 0
        
def saiki(target,tasu,n):
  #target = array[]
  target.cnt += tasu
  for ko in target.kodomo:
    if ko<n:
      saiki(array[ko],tasu,n)
  
        
n, q = [int(i) for i in input().split()]
array=[]
 
for i in range(n):
  array.append(Node(i+1))
  
  
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  array[a-1].kodomo.append(b-1)
 
  
for i in range(q):
  x, tasu = [int(i) for i in input().split()]
  if x-1<n:
    saiki(array[x-1],tasu,n)
  
for i in range(n):
  if i != n-1:
    print(array[i].cnt, end =" ")
  else:
    print(array[n-1].cnt)

Submission status: Time Limit Exceeded

Solution code:
n, q = [int(i) for i in input().split()]
a = []
ans = [0 for i in range(n)]
for i in range(n-1):
    a.append([int(j) for j in input().split()])
for i in range(q):
    inp, inp2 = [int(j) for j in input().split()]
    aa = [inp]
    for j in range(len(a)):
        if a[j][0] in aa:
            aa.append(a[j][1])
    for j in aa:
        ans[j-1] += inp2
print(" ".join([str(i) for i in ans]))