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:
# ★頂点1からdfsを始めればよいので、 自分の親はどれで子はどれなのか分からなくてもできる！

# 再帰関数の呼び出し回数が多くなる時はこれが必要！！無いとruntime errorになる。
import sys
sys.setrecursionlimit(200000+10)

# 木の深さ優先探索
def add_edge(u, v):
	G[u].append(v)
	G[v].append(u)

def dfs(vertex):
	global counters
	global visited

	visited[vertex] = True


	for v in G[vertex]:
		if visited[v]: 
			#探索済み
			pass
		else:
			# 子のに自分の値を足す
			counters[v] += counters[vertex]
			dfs(v)


n, n_query =  list(map(int, input().split() ))

edges = [list(map(int, input().split())) for _ in range(n-1)]
visited = [False] * n
counters = [0] * n

G = [[] for _ in range(n)] #グラフの隣接リスト表現
for edge in edges:
	add_edge(edge[0]-1, edge[1]-1)

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

dfs(0)

#for i in range(n):
#	print(counters[i], end=" ")

x = map(str, counters)
print (" ".join(x))

Submission status: Time Limit Exceeded

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

N, Q = LI()
AB = []
PX = []
for i in range(N-1):
    AB.append(LI())

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

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


"""

AB = sorted(AB, key=lambda x: x[1], reverse=True)

perr('AB')
perr(AB)
d = {}
for a, b in AB:
    # abの頂点若い方に足していく
    if a not in d.keys():
        d[a] = []
    if b not in d.keys():
        d[a].append(b)
    else:
        d[a].append(b)
        d[a].extend(d[b])

perr('d')
perr(d)

ans = [0 for _ in range(N)]
for p, x in PX:
    perr('px')
    perr([p, x])
    ans[p-1] += x
    if p not in d.keys():
        continue
    for i in d[p]:
        perr('i')
        perr(i)
        ans[i-1] += x

perr('ans')
perr(ans)
for a in ans:
    print(a, end=' ')

Submission status: Time Limit Exceeded

Solution code:
def bfs(graph, start, weight):
	queue = [start]
	while queue:
		label = queue.pop(0)
		cnt[label-1] += weight
		queue += graph.get(label,[])

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

cnt = [0 for i in range(n)]
dic = {}
for i in range(n-1):
	if a[i][0] not in dic:
		dic[a[i][0]] = [a[i][1]]
	else:
		dic[a[i][0]].append(a[i][1])

for i in range(q):
	bfs(dic, b[i][0], b[i][1])
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000000)


class Graph:

  def __init__(self, N):
    self.V = {}
    self.E = {}

    for i in range(N):
      self.V[i + 1] = 0
      self.E[i + 1] = {}

  def add_edge(self, u, v, w):
    self.E[u][v] = w


def walk(G, result, u, current_value=0):
  current_value += G.V[u]
  result[u - 1] = current_value
  for v in G.E[u]: walk(G, result, v, current_value)


def calc(N, G):
  result = [0] * N

  walk(G, result, 1, 0)

  return result


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

G = Graph(N)

for _ in range(N - 1):
  a, b = map(int, input().strip().split())
  G.add_edge(a, b, 0)

for _ in range(Q):
  p, x = map(int, input().strip().split())
  G.V[p] += x

result = calc(N, G)

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

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

class Node:
    def __init__(self, num):
        self.num = num
        self.children = set()
        self.all_children = set()
        self.count = 0

    def add_child(self, child):
        self.children.add(child)

    def search_all_children(self):
        all_children = []
        for child in self.children:
            all_children += child.search_all_children()
        self.all_children = list(set(all_children))
        all_children.append(self)
        return list(set(all_children))

    def counter(self, amount):
        for child in self.all_children:
            child.count += amount
        self.count += amount


def add(nodes, ab, top):
    if not ab:
        return
    child = set()
    xy = deepcopy(ab)
    for c in ab:
        if c[0] == top:
            nodes[c[0]-1].add_child(nodes[c[1]-1])
            child.add(c[1])
            xy.remove(c)
        elif c[1] == top:
            nodes[c[1]-1].add_child(nodes[c[0]-1])
            child.add(c[0])
            xy.remove(c)
    for i in child:
        add(nodes, xy, i)


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)]
nodes = [Node(i+1) for i in range(n)]

add(nodes, ab, 1)
for node in nodes:
    node.search_all_children()
for q in px:
    nodes[q[0]-1].counter(q[1])
for node in nodes:
    print(node.count, end=' ')
print()

Submission status: Time Limit Exceeded

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

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

for i in range(Q):
  p, x = [int(i) for i in input().split()]
  for j in ndic[p].childs:
    j.counter += x
ans = ""
for k, v in ndic.items():
  ans += str(v.counter) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
ab = [[0 for i in range(n)] for j in range(n)]
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    ab[ai-1][bi-1] = 1
    ab[bi-1][ai-1] = 1
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)




#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] +=xi
sp = [float("inf") for i in range(n)]
sp[0] = px[0]

#訪問済
x = [0 for i in range(n)]
def f(v,p):
    x[v] = 1
    sp[v] = p + px[v]
    for di in d[v]:
        if x[di] == 0:
            f(di,sp[v])
f(0,0)
for i in range(n):
    print(sp[i])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(30000)

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

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

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


visited = [False]*n


def dfs(v):
    visited[v] = True
    for nv in tree[v]:
        if visited[nv]:
            continue
        cnt[nv] += cnt[v]
        dfs(nv)


dfs(0)
print(' '.join(map(str, cnt)))

Submission status: Time Limit Exceeded

Solution code:
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)]
        ab.sort()
        px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

if __name__ == '__main__':
        main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,Q = inputMap()
	ki = [[] for _ in range(N)]
	kiki = []
	ans = [0 for _ in range(N)]

	for i in range(N-1):
		a,b = inputMap()
		ki[a-1].append(b-1)

	for i,val in enumerate(ki):
		if len(val) == 0:
			kiki.append([])
			continue
		addd = val
		for vol in val:
			tmp = ki[vol]
			addd.extend(tmp)
		kiki.append(addd)

	for i in range(Q):
		p,x = inputMap()
		ans[p-1] += x
		for vol in kiki[p-1]:
			ans[vol] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,q = map(int,input().split())
graph = [[] for _ in range(n)]
connect = [[_] for _ 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)
    graph[b].append(a)

for i in range(n):
    que = deque(graph[i])
    while que:
        c = que.popleft()
        if c > i:
            connect[i].append(c)
            for j in graph[c]:
                if j > i and j not in connect[i]:
                    que.append(j)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline


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

edge=[[] for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    u-=1;v-=1
    edge[u].append(v)

res=[0]*n

def solve(p,x):
    que=[p]
    while que:
        p=que.pop()
        res[p]+=x
        for e in edge[p]:
            que.append(e)
    return


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

print(*res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


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


# In[13]:


class Node:
    def __init__(self, nb, data): #コンストラクタ
        self.nb = nb
        self.data = data #ノードがもつ数値
        self.parent = -1 # nodeがrootのとき-1、それ以外番号
        self.childs = [] # childになるnode classが入る
        
    def connect_childs(self, child_class_):
        self.childs.append(child_class_)
        
    def get_childs(self):
        return self.childs
    
    def sum_data(self, data):
        self.data += data


# In[33]:


nodes = [Node(_+1, 0) for _ in range(N)]


# In[34]:


for i in range(N-1):
    a, b = abs_[i]
    nodes[a-1].connect_childs(nodes[b-1])
    nodes[b-1].parent = a-1


# In[25]:


"""
def sum_x(node, x):
    node.data += x
    for child in node.childs:
        sum_x(child, x)
"""


# In[28]:


"""
for i in range(Q):
    p, x = pxs_[i]
    sum_x(nodes[p-1], x)
"""


# In[35]:


for i in range(Q):
    p, x = pxs_[i]
    nodes[p-1].data += x


# In[36]:


def sum_data_to_childs(node):
    data = node.data
    for child in node.childs:
        child.data += data
        sum_data_to_childs(child)


# In[37]:


sum_data_to_childs(nodes[0])


# In[38]:


datas = [str(nodes[_].data) for _ in range(N)]
print(' '.join(datas))


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:

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

ab = []

link = {} 

for i in range(N-1):

    a,b = map(int,input().split())

    if a-1 not in link : link[a-1] = []
    if b-1 not in link : link[b-1] = []


    link[a-1].append(b-1)
    link[b-1].append(a-1)



plus = [0] * N

for i in range(Q):

    p,x = map(int,input().split())

    plus[p-1] += x


Q = []

ans = [0] * N
end = set([])
p = [-1] * N
p[0] = 0

nowq = 0
Q.append(0)

end = end | set([0])


while nowq < N:

    nowpo = Q[nowq]
    #print (nowpo)
    ans[ nowpo ] = ans[p[ nowpo ]] + plus[nowpo]

    for i in link[nowpo]:

        if i not in end:

            Q.append(i)
            p[i] = nowpo
            #print (i,nowpo)


            end = end | set([i])


    nowq += 1

#print (Q,p,link)

for i in ans:
    print (i)

Submission status: Time Limit Exceeded

Solution code:
cnt = [0] * int(2 * 10e5 + 10)
li = [[] for _ in range(int(2 * 10e5 + 10))]
def f(a):
    global cnt, li
    for c in li[a]:
        cnt[c] += cnt[a]
        f(c)
def solve():
    global cnt, li
    n, q = map(int, input().split())
    for _ in range(n - 1):
        a, b = map(int, input().split())
        li[a].append(b)
    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p] += x
    f(1)
    print(*cnt[1 : n + 1])
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
class Node:
  def __init__(self, n):
    self.number = n
    self.children = []
    self.value = 0
def add_values(nodes, i, x):
  n = nodes[i]
  n.value += x
  for c in n.children:
    add_values(nodes, c, x)
n, q = map(int, input().split())
nodes = [Node(i) for i in range(0, n + 1)]
nodes[0] = None
for i in range(n - 1):
  a, b = map(int, input().split())
  nodes[a].children.append(b)
for _ in range(q):
  p, x = map(int, input().split())
  add_values(nodes, p, x)
print(' '.join(str(nodes[i].value) for i in range(1, n + 1)))

Submission status: Time Limit Exceeded

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

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

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

def dig(i,tmp):
    tmp += adds[i]
    ans[i] = tmp
    for v in tree[i]: dig(v,tmp)

ans = defaultdict(int)
tmp = 0
dig(1,tmp)

for i in range(1,N+1):
    print(ans[i], end=' ')
print()

Submission status: Time Limit Exceeded

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

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

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

y = [0]*n
for i in range(n) :
    y[i] += xlist[i]
    
    r = i
    while True :
        for j in range(n) :
            if hen[j][1] - 1 == r :
                r = hen[j][0] - 1
                y[i] += xlist[r]
                break
        if j == n-1 :
            break

c = str(y[0])
for i in range(1,n) :
    c += ' ' + str(y[i])

print(c)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
edge_from = [[] for _ in range(N)]
cnt = [0]*N
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 = [(0, 0)]
while q != []:
    p, x = q.pop(0)
    x += tmp[p] 
    cnt[p] += x
    for nx in edge_from[p]:
        q.append((nx, x))

for i in range(N):
    print(cnt[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
n, q = [int(x) for x in input().split() ]
count = [0 for x in range(n+1)]
tree = [[] for x in range(n+1)]
for i in range(1,n):
    arr = [int(x) for x in input().split()]
    tree[arr[0]].append(arr[1])
for i in range(q):
    arr = [int(x) for x in input().split()]
    temp= [arr[0]]
    visit = [0 for x in range(n+1)]
    visit[temp[0]] = 1
    count[temp[0]] += arr[1]
    while temp != []:
        visit[temp[0]] =1
        for x in tree[temp[0]]:
            count[x] += arr[1]
            if visit[x] == 0:
                temp.append(x)
        del temp[0]
        
for i in range(1,n+1):
    print(count[i], end=' ')
print()

Submission status: Time Limit Exceeded

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

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

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

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)
        return  0

    f(weights[0], 0)
    return ' '.join(map(str, ans))


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

from collections import deque

c = [0]*n
queue = deque()
for j in range(q):
  x, p = map(int, input().split())
  x = x-1
  #queue = deque()
  c[x] += p
  if g[x] == []:
    continue
  queue.append(x)
  while queue:
    y = queue.popleft()
    for y_ in g[y]:
      c[y_] += p
      if g[y_] == []:
        continue
      else:
        queue.append(y_)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import queue

tree = defaultdict(list)

N, Q = list(map(int, input().split()))
a, b = [0 for i in range(N-1)], [0 for i in range(N-1)]
ans = [0 for i in range(N)]
p, x = [0 for i in range(Q)], [0 for i in range(Q)]

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

for i in range(Q):
    p[i], x[i] = list(map(int, input().split()))
    ans[p[i]-1] += x[i]
    child_node = tree[p[i]]
    child_queue = queue.Queue()
    child_queue.put(child_node)
    while not child_queue.empty():
        nodes = child_queue.get()
        for child_node in nodes:
            ans[child_node-1] += x[i]
            if tree[child_node]:
                child_queue.put(tree[child_node])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# 4 3
# 1 2
# 2 3
# 2 4
# 2 10
# 1 100
# 3 1

n, q = list(map(int, input().split(" ")))
a = []
b = []
for i in range(n-1):
    j, k = list(map(int, input().split(" ")))
    a.append(j)
    b.append(k)

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


class Node:
    def __init__(self, id):
        self.id = id
        self.counter = 0
        self.linked = []

    def add_node(self, node):
        self.linked.append(node)

    def add_count(self, count):
        self.counter += count


# make node
tree = []
for i in range(n):
    tree.append(Node(i))

for j, k in zip(a, b):
    tree[j-1].add_node(tree[k-1])

for j, k in zip(p, x):
    tree[j-1].add_count(k)

# traverse
for i in tree:
    for j in i.linked:
        j.counter += i.counter

m = []
for i in tree:
    m.append(i.counter)

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

Submission status: Time Limit Exceeded

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

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

ans = [0] * n


for i in range(q):
    p, x = map(int,input().split())
    if (p == 1):
        for j in range(n):
            ans[j] += x
    else:
        br = {p}
        for j in range(n-1):
            if(ab[j][0] in br):
                br.add(ab[j][1])
        
        for k in br:
            ans[k-1] += x

[print(i,end=" ") for i in ans]
print()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6 + 1000)

par = [0]
words = lambda t : list(map(t, input().split()))
n,q = words(int)
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b = words(int)
    edges[a-1].append(b-1)

points = [0] * n
for i in range(q):
    p,x = words(int)
    points[p-1] += x

ans = [0] * n
def digTree(cur, sum_p):
    #print("debug: ", cur, sum_p)
    sum_pp = sum_p +  points[cur]
    ans[cur] = sum_pp
    for child in edges[cur]:
        digTree(child, sum_pp)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

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

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

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

def dfs(x, c, p):
	#print(x)
	ans[x] = c + queries[x]
	for v in adj[x]:
		if v != p:
			dfs(v, ans[x], x)
	return

dfs(0, 0, -1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


children = defaultdict(set)
parents = {}


def collect_children(mats):
  if not mats:
    return
  pp = set()
  for m in mats:
    if m != 1:
      pp.add(parents[m])
      children[parents[m]].update(children[m])
  collect_children(pp)


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

mats = []

for a, b in AB:
  children[a].add(b)
  parents[b] = a

for n in range(N):
  if not children[n + 1]:
    mats.append(n)

collect_children(mats)

sums = [0] * N
for p, x in PX:
  for c in children[p]:
    sums[c - 1] += x
  sums[p - 1] += x
print(" ".join(str(s) for s in sums))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n, q = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(n-1)]
pxpx = [list(map(int, input().split())) for _ in range(q)]

pxdict = {i:0 for i in range(1, 1+n)}
for p, x in pxpx :
    pxdict[p] += x

babadict = {b:a for a, b in abab}

@lru_cache(maxsize=10**5+1)
def counter(node) :
    if node == 1 :
        return pxdict[1]
    else :
        return pxdict[node]+counter(babadict[node])

for i in range(1, n+1) :
    print(counter(i))

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

plus = [0 for _ in range(N)]

for p,x in px:
        plus[p - 1] += x 

for a,b in ab:
        plus[b - 1] += plus[a - 1]
for p in plus:
        print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200000)

def resolve():
    N, Q = map(int, input().split())
    nodes = [[] for _ in range(N)]
    counter = [0] * (N)

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

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

    def send(numNode):
        for target in nodes[numNode]:
            counter[target] += counter[numNode]
            send(target)

    send(0)

    print(" ".join([str(n) for n in counter]))


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

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

G = defaultdict(lambda: defaultdict(int))

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

parents = [0] * (N + 1)
values = [0] * (N + 1)
values_sum = [-1] * (N + 1)

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

# solve
values_sum[1] = values[1]

queue = deque([1])
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if G[p][q] == 1 and values_sum[q] == -1:
            values_sum[q] = values_sum[p] + values[q]
            queue.append(q)

print(*values_sum[1:])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
ab=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*(n-1)]
pq=[list(map(int,input().split())) for _ in [0]*q]
for i in range(q):
    pq[i][0]-=1

graph=[[] for _ in [0]*n]
[graph[a].append(b) for a,b in ab if a<b]
[graph[b].append(a) for a,b in ab if a>b]

plus=[0 for _ in [0]*n]
for i,j in pq:
    plus[i]+=j

pos=[]
ans=[0 for _ in [0]*n]
temp=0
q=[0]
memo=[False for _ in [0]*n]
#memo[0]=True
while q:
    i=q.pop(-1)
    if memo[i]==False:
        pos.append(i)
        temp+=plus[i]
        ans[i]=temp
    memo[i]=True

    g=graph[i]
    for j in g:
        if memo[j]==False:
            q.append(j)
            break
    else:
        temp-=plus[pos[-1]]
        pos.pop(-1)
        if pos!=[]:
            q.append(pos[-1])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

N, Q = map(int, input().split())
children = [[i] for i in range(N)]  # 各頂点の持つ部分木の頂点の集合
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = np.zeros(N, dtype=np.int32)

for a, b in edges[::-1]:
    children[a-1] += children[b-1]

children = [list(set(child)) for child in children]

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

print(' '.join(list(map(str, counts))))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import defaultdict

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

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

G = Graph()

N, Q = getlist()
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a, b)
	G.add_edge(b, a)

plus = [0 for i in range(N + 1)]
for i in range(Q):
	p, x = getlist()
	plus[p] += x

#幅優先
q = queue.Queue()
val = 0
ans = [0 for i in range(N + 1)]
visit = [-1 for i in range(N + 1)]
visit[1] = 1
q.put(1)
while not q.empty():
	m = q.get()
	ans[m] += plus[m]
	visit[m] = 1
	for i in G.graph[m]:
		if visit[i] == -1:
			q.put(i)
			ans[i] += ans[m]

ans2 = []
for i in range(N):
	ans2.append(ans[i + 1])

print(" ".join(list(map(str, ans2))))

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

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())

# print(N, Q, A, B, P, X)

C = {}
for i in range(N - 1):
    a = A[i]
    b = B[i]
    if a > b:
        a, b = b, a
    if a not in C:
        C[a] = {'r': [b], 's': 0}
    else:
        C[a]['r'].append(b)
# print(C)

for i in range(Q):
    p = P[i]
    x = X[i]
    if p not in C:
        C[p] = {'r':[], 's': x}
    else:
        C[p]['s'] += x

# print(C)

for i in range(1, N):
    if i not in C:
        continue
    c = C[i]
    R = c['r']
    s = c['s']
    for r in R:
        if r not in C:
            C[r] = {'r': [], 's': s}
        else:
            C[r]['s'] += s

# print(C)

ans = []
for i in range(1, N + 1):
    c = C[i]
    ans.append(c['s'])

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

Submission status: Time Limit Exceeded

Solution code:
# #ABC138 D
n,q = list(map(int,input().split()))
from collections import defaultdict
 
dc = defaultdict(list)
dc[1] = []
for i in range(n-1):
    a,b = map(int,input().split())
    dc[b].append(a)
    dc[b].extend(dc[a])


counter = defaultdict(int)

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

for i in range(1,n+1):
    score = 0
    if  i in counter:
        score += counter[i] 
    if len(dc[i]) > 0:
        score += sum([counter[x] for x in dc[i]])
    print(score,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
ab = [[0 for i in range(n)] for j in range(n)]
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    ab[ai-1][bi-1] = 1
    ab[bi-1][ai-1] = 1
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)

#parentを返す
p = [0 for i in range(n)]
#訪問済
x = [0 for i in range(n)]
def f(v):
    x[v] = 1
    for di in d[v]:
        if x[di] == 0:
            p[di] = v
            f(di)
f(0)

#point
px = [0 for i in range(n)]

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

#sumpoint
sp = [float("inf") for i in range(n)]
sp[0] = px[0]

def g(v):
    if v == 0:
        return px[v]
    else:
        if sp[v] == float("inf"):
            point = px[v]+g(p[v])
            sp[v] = point
            return point
        else:
            return sp[v]
for i in range(n):
    if i ==0:
        print(px[0])
    else:
        print(g(i))