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 -*-

import sys
sys.setrecursionlimit(1000000)

def readInts():
  return [int(s) for s in input().split(" ")]

def visit(edges, ans, points, visited, n, acc):
  if visited[n]:
    return
  visited[n] = True
  ans[n] = acc + points[n]

  for k in edges[n]:
    if not visited[k]:
      visit(edges, ans, points, visited, k, ans[n])
  return

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

  edges = {}
  for n in range(N-1):
    a, b = readInts()
    a -= 1
    b -= 1
    if not a in edges:
      edges[a] = []
    if not b in edges:
      edges[b] = []
    edges[a].append(b)
    edges[b].append(a)

  points = [0 for _ in range(N)]
  for q in range(Q):
    p, x = readInts()
    points[p - 1] += x

  visited = [False for _ in range(N)]
  ans = [0 for _ in range(N)]
  visit(edges, ans, points, visited, 0, 0)

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

if __name__ == "__main__":
  main()

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 != []:
        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(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 calc(N, G):
  result = [0] * N

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

  walk(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:
class Node(object):

    def __init__(self, n):
        self.n = n
        self.link = []
        self.counter = 0

    def add(self, node):
        self.link.append(node)

    def prop(self, parent):
        for node in self.link:
            if node.n == parent:
                continue
            node.counter += self.counter
            node.prop(self.n)


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

nodes = [Node(n) for n in range(N + 1)]

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

for _ in range(Q):
    p, q = list(map(int, input().rstrip().split()))
    nodes[p].counter += q

nodes[1].prop(0)

print(' '.join([str(node.counter) for node in nodes[1:]]))

Submission status: Time Limit Exceeded

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

def sousa(Tree, parent, value):
  Tree[parent][0] += value
  for c in Tree[parent][1]:
    sousa(Tree, c, value)

N, Q = map(int, input().split())
T = [[0, []] for _ in range(N)]
E = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
for e in E:
  T[e[0]-1][1].append(e[1]-1)
for px in PX:
  sousa(T, px[0]-1, px[1])
ans_s = ""
for t in T:
  ans_s += "%d "%t[0]
print(ans_s)

Submission status: Time Limit Exceeded

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

tree = [[i] for i in range(N+1)]
points = [0] * N

for i in range(1, N):
  a, b = map(int, input().split())
  tree[a].append(b)
  for j in range(i):
    if a in tree[j]:
      tree[j].append(b)
      
for i in range(Q):
  p, x = map(int, input().split())
  for node in set(tree[p]):
    points[node-1] += x
    
for point in points:
  print(point, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
n, q = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

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

ans = [0] * n
searched = set()
def dfs(cur, c):
    c += cost[cur]
    ans[cur] = c
    searched.add(cur)
    for next in edge[cur]:
        if next not in searched:
            dfs(next, c)

dfs(0, 0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
def tree(edges,n,q):
    distance = [0]*(n+1)
    for _ in range(0,q):
        p,x = map(int,input().split())
        Q = queue.Queue()
        Q.put(p)
        distance[p] += x
        while (not Q.empty()):
            xx = Q.get()
            for i in range(0,len(edges[xx])):
                distance[edges[xx][i]] += x
                Q.put(edges[xx][i])
    return distance[1:]

def addEdge(edges,u,v):
    edges[u].append(v)
n,q = map(int,input().split())
edges = [[] for i in range(n+1)]
for _ in range(0,n-1):
    u,v = map(int,input().split())
    addEdge(edges,u,v)
print(*tree(edges,n,q))

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
    cnt[px[q][0]-1]+=px[q][1]
    for i in range(N-1):
        if che[ab[i][0]-1]==True:
            che[ab[i][1]-1]=True
            cnt[ab[i][1]-1]+=px[q][1]

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

Submission status: Time Limit Exceeded

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

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

a=[]
b=[]
apex=[]
a.append(0)
b.append(0)
apex.append(0)

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


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


#print(a,b)
#print(p,x)
#print(apex)

def calc(j):
	for i in range(0,n):
		if(a[i]==j):
#			print("bi:{} j:{}".format(b[i],j))
			apex[b[i]]+=apex[j]
			calc(b[i])

calc(1)

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

#print(apex[1:n+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(250000)
from collections import defaultdict

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

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

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

seen = set()
ans = [0 for _ in range(N + 1)]


def dfs(v, cnt):
    seen.add(v)
    cnt += val[v]
    ans[v] = cnt
    for next_v in nl[v]:
        if next_v not in seen:
            dfs(next_v, cnt)


dfs(1, 0)
c = [0 for _ in range(N + 1)]
print(' '.join([str(a) for a in ans[1:]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)
def Nodify(n):
    for i in graph[n]:
        if Tree[i]==-1:
            Tree[i]=n
            Nodify(i)
n,q=map(int,input().split())
graph=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
Tree=[-1]*n
Nodify(0)
counter=[0 for _ in range(n)]
for _ in range(q):
    p,x=map(int,input().split())
    counter[p-1]+=x
for i in range(n):
    y=i
    ret=counter[y]
    while y!=0:
        ret+=counter[Tree[y]]
        y=Tree[y]
    print(ret, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, q = map(int, input().split())
es = defaultdict(list)

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

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

score = defaultdict(int)
score[1] = added[1]

parent = {}
parent[1] = None
visiting = [1]
while visiting:
    v = visiting.pop()
    for neighbor in es[v]:
        if not neighbor in parent:
            parent[neighbor] = v
            score[neighbor] = added[neighbor] + score[v]
            visiting.append(neighbor)
print(" ".join([str(score[i]) for i in range(1, n+1)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

query = [0 for _ in range(N)]
ans = [[0] for _ in range(N)]

for p,x in px:
    query[p-1] = query[p-1] + x
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(b-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    val += query[v]
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
        
dfs(0,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(100000)

n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

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

def dfs(x, v, ans):
	ans[x] = ws[x] + v
	if len(ds[x]) > 0:
		for nxt in ds[x]:
			ans = dfs(nxt, ans[x], ans)
	return ans

ans = dfs(0, 0, ans)

#print(ws)
#print(ds)

for i in range(n):
	print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

lines = sys.stdin.readlines()
edges = list(map(lambda s:list(map(int, s.split(" "))), lines[:n-1]))
queries = list(map(lambda s:list(map(int, s.split(" "))), lines[n-1:]))

scores = [0] * (n+1)

for q in queries:
    scores[q[0]] += q[1]

queue = deque()
mark = [False] * (n+1)
mark[1] = True

for e in edges:
    queue.append(e)

while queue:
    e = queue.popleft()
    
    a = e[0]
    b = e[1]
    if mark[a]:
        scores[b] += scores[a]
        mark[b] = True
    elif mark[b]:
        scores[a] += scores[b]
        mark[a] = True
    else:
        queue.append(e)
        print()

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

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(4100000)

class Node():
    def __init__(self, val):
        self.val = val
        self.counter = 0
        self.child = []

if __name__ == '__main__':
    def inorder(node, val, toadd, combs):
        if combs.get(node.val):
            toadd += combs[node.val]
            return
        if node is None:
            return
        toadd.append(node)
        for child in node.child:
            inorder(child,val, toadd, combs)

    n,q = [int(i) for i in input().split()]
    a = [[int(i) for i in input().split()] for _ in range(n-1)]
    p = [[int(i) for i in input().split()] for _ in range(q)]
    nodes = {}
    for i in range(1,n+1):
        temp = Node(i)
        nodes[i] = temp
    for A,B in a:
        nodes[A].child.append(nodes[B])
    combs = {}
    for P,X in p:
        toadd = []
        inorder(nodes[P],X, toadd, combs)
        combs[P] = toadd
        for node in toadd:
            node.counter += X
    ans = ""
    for i in range(1,n+1):
        ans += str(nodes[i].counter) + " "
    print(ans)

Submission status: Time Limit Exceeded

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

    graph = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        if a not in graph: graph[a] = [b]
        else: graph[a].append(b)
        # if b not in graph: graph[b] = [a]
        # else: graph[b].append(a)

    ops = dict()
    for i in range(Q):
        p, x = map(int, input().split())
        if p not in ops: ops[p] = x
        else: ops[p] += x

    # print(graph)
    # print(ops)
    vals = [0 for _ in range(N)]
    for p in ops:
        v = ops[p]
        cur = [p]
        visited = set()
        while cur:
            temp = []
            for a in cur:
                vals[a-1] += v
                if a in graph:
                    for b in graph[a]:
                        if b not in visited:
                            temp.append(b)
                            visited.add(b)
            cur = temp

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


if __name__ == '__main__':
    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)]
ab.sort()
px.sort()


# connection = [[] for _ in range(N - 1)]
# ans = [[] for _ in range(N)]
plus = [0 for _ in range(N)]

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

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

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()
		tmp = kiki[p-1]
		ans[p-1] += x
		for vol in tmp:
			ans[vol] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import sys
sys.setrecursionlimit(10 ** 6)
N, Q = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  
res = [0] * (N + 1)
for _ in range(Q):
  p, x = map(int, input().split())
  res[p] += x
visited = [0] * (N + 1)
def dfs(n):
  global visited
  global res
  visited[n] = 1
  for o in e[n]:
    if visited[o] == 0:
      res[o] += res[n]
      dfs(o)
dfs(1)
sen = ""
for i in range(1, N + 1):
  sen += str(res[i])
  if i != N:
    sen += " "
print(sen)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000000)


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):
    self.E[u].append(v)


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

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

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

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

    f(weights[0], 0)
    for a in ans:
        print(a, end=' ')
    print()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N, Q = inpl()
neighbor = [[] for i in range(N)]
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)
X = [0] * N
for _ in range(Q):
    p, x = inpl()
    X[p-1] += x
result = [0] * N
def dfs(node, x, parent):
    x += X[node]
    result[node] = x
    for c in neighbor[node]:
        if c == parent:
            continue
        else:
            dfs(c,x,node)

dfs(0, 0, None)
print(' '.join(map(str,result)))

Submission status: Time Limit Exceeded

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

tree = [set([i]) for i in range(N+1)]
points = [0] * N

for i in range(1, N):
  a, b = map(int, input().split())
  tree[a].add(b)
  for j in range(i):
    if a in tree[j]:
      tree[j].add(b)
      
for i in range(Q):
  p, x = map(int, input().split())
  for node in tree[p]:
    points[node-1] += x

# print(tree)
    
for point in points:
  print(point, end=" ")

Submission status: Time Limit Exceeded

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

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

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

for _ in range(q):
    p, q = map(int, input().split())
    target = [p]
    while len(target):
        t = target.pop()
        ct[t] += q
        for nt in e[t]:
            target.append(nt)

print(*ct[1:])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
chi = [[0] * (N) for i in range(N)]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def update(node,value):
  if node-1<0 or len(l)<=node-1:
    return 0
  vl[node-1]+=value

  if len(l[node-1])==0:
    return 0

  for x in l[node-1]:
    update(x,value)

n,q=LI()

l=[[] for _ in range(n)]
vl=[0 for _ in range(n)]

for _ in range(n-1):
  a,b=LI()
  l[a-1].append(b)

l2=[0]*(n+1)
for _ in range(q):
  a,b=LI()
  l2[a]+=b

for i,x in enumerate(l2):
  if i==0:
    continue
  update(i,x)

print(' '.join([str(x) for x in vl]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
edge = [[] for i in range(N)]
val = [0 for i in range(N)]
decide = [0 for i in range(N)]
for i in range(N-1):
    a, b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
for i in range(Q):
    n, v = map(int,input().split())
    val[n-1] += v

queue = [0]
while queue:
    op = queue.pop(0)
    while edge[op]:
        a = edge[op].pop(0)
        if decide[a] == 0:
            val[a] += val[op]
            queue.append(a)
    decide[op] = 1
print(*val)

Submission status: Time Limit Exceeded

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


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

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


def recursive(p):
    for c in AB[p]:
        X[c] += X[p]
        recursive(c)


recursive(0)
print(" ".join(map(str, X)))

Submission status: Time Limit Exceeded

Solution code:
n, q = [int(i) for i in input().split()]
g = [[] for i in range(n)]

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

q = [[1, c[0]]]
while len(q) != 0:
    p = q.pop(0)
    for i in g[p[0]-1]:
        c[i-1] += p[1]
        q.append([i, c[i-1]])

print(*c)

Submission status: Time Limit Exceeded

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

score=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    update_n = [p-1]
    while update_n:
        current_n = update_n.pop(0)
        score[current_n] += x
        update_n += edge[current_n]
print(*score)

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[21]:


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


# In[22]:


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[32]:


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


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
res = []
tree = []
level = []
for i in range(210000):
    res.append(0)
    tree.append([])
    level.append(-1)

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

def make_level(index, lev):
    level[index] = lev
    for next in tree[index]:
        # 逆走はしない
        if level[next] != -1:
            continue
        make_level(next, lev + 1)
make_level(1, 0)
#print(level[0:10])

def do(index, lev, cost):
    res[index] += cost
    for next in tree[index]:
        if level[next] <= lev:
            continue
        do(next, lev + 1, cost)


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

res = list(map(str, res))
print(" ".join(res[1:n+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)

#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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, q = map(int, input().split())
es = {}

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

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

score = defaultdict(int)
score[1] = added[1]

parent = {}
parent[1] = None
visiting = [1]
while visiting:
    v = visiting.pop()
    for neighbor in es[v]:
        if not neighbor in parent:
            parent[neighbor] = v
            score[neighbor] = added[neighbor] + score[v]
            visiting.append(neighbor)
print(" ".join([str(score[i]) for i in range(1, n+1)]))

Submission status: Time Limit Exceeded

Solution code:
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)

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

visited = [True for _ in range(N+1)]
visited[1] = False
queue = [1]
Ans = [0]*(N+1)

for p,x in PX:
    Ans[p] += x

while len(queue) > 0:
    nextnode = queue.pop(0)
    for e in Edge[nextnode]:
        if visited[e]:
            visited[e] = False
            queue.append(e)
            Ans[e] += Ans[nextnode]
print(*Ans[1:],sep = " ")

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
a_list,b_list=[],[]
for i in range(N-1):
    a,b=map(int,input().split())
    a_list.append(a)
    b_list.append(b)    

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

ab_list=[(x,y) for x,y in zip(a_list,b_list)]
px_list=[(p,x) for p,x in zip(p_list,x_list)]

dic={}
for a,b in ab_list:
    dic[b]=[b]
    if a not in dic.keys():
        dic[a]=[a,b]
    else:
        dic[a].append(b)
    for key,item in dic.items():
        if a in item and b not in dic[key]:
            dic[key].append(b)  

counts=[0]*N
for p,x in px_list:
    l=dic[p]
    for i in l:
        counts[i-1]+=x
            
print(" ".join([str(x) for x in counts]))

Submission status: Time Limit Exceeded

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


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

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


def recursive(p):
    for c in AB[p]:
        X[c] += X[p]
        recursive(c)


recursive(0)
print(" ".join(map(str, X)))

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(1000000)

def inc(tree, point, p, x):
    # 自分
    point[p] += x
    if tree[p] == -1:
        return

    for child in tree[p]:
        inc(tree, point, child, x)


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

tree = [-1] * (N+1)
point = [0] * (N+1)

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

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

    inc(tree, point, p, x)

point.pop(0)
print(*point)

Submission status: Time Limit Exceeded

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

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

for i in range(q):
    p,x=map(int,stdin.readline().rstrip().split())
    cnt[p-1]+=x
    rec(p-1,x)
print(*cnt)