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:
def bubunki(akan):
    for l in range(n-1) :
        if(a[l] == akan) :
            z[b[l]] += x[k]
            bubunki(b[l]) 
    return 



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

a = []
b = []
p = [] 
x = []
z = [0] * (n+1)

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

for j in range(q) :
    p1,x1 = map(int,input().split())
    p.append(p1)
    x.append(x1)


for k in range(q) :

    z[p[k]] += x[k]

    bubunki(p[k])        

s = ""
for l in range(1,n+1) :
    s +=  str(z[l]) + " "
    
print(s)

Submission status: Time Limit Exceeded

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

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

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

def make_level(index, lev, pp):
    l = 0
    level[index] = lev
    parent[index] = pp
    for next in tree[index]:
        #print("index {0} search {1}".format(index, next))
        # 逆走はしない
        if level[next] != -1:
            #print("CANNOT MOVE to {0}".format(next))
            continue
        # 子供に親を設定
        parent[next] = index
        cost[next] += cost[index]
        curparent = index
        make_level(next, lev + 1, index)

make_level(1, 0, -1)

res = list(map(str, cost))
print(" ".join(res[1:n+1]))

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

if  __name__ == "__main__":
	solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

class Node(object):
    def __init__(self):
        self.value = 0
        self.children_id = []

    def set_child(self, child_id):
        self.children_id.append(child_id)

    def add_number(self, n):
        self.value += n
        for child_id in self.children_id:
            nodes[child_id].add_number(n)

    def get_value(self):
        return self.value

N, Q = map(int, sys.stdin.readline().rstrip().split())

nodes = []
for i in range(N + 1):
    nodes.append(Node())

for j in range(N - 1):
    parent, child = map(int, sys.stdin.readline().rstrip().split())
    nodes[parent].set_child(child)

for _ in range(Q):
    parent, number = map(int, sys.stdin.readline().rstrip().split())
    nodes[parent].add_number(number)

res = []
for k in range(1, N + 1):
    res.append(nodes[k].get_value())

print(*res, sep=' ')

Submission status: Time Limit Exceeded

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

def make_tree(a,b):
  if len(tree_list) == 0:
    tree_list.append([a,b])
    tree_list.append([b])
  else:
    for i in range(len(tree_list)):
      if a in tree_list[i]:
        tree_list[i].append(b)
      if i == len(tree_list)-1:
        tree_list.append([b])
def count(num,x):
  for i in tree_list[num]:
    count_list[i-1] +=x
for i in range(N-1):
  a,b = map(int,input().split())
  if a not in top_list:
    top_list.append(a)
  if b not in top_list:
    top_list.append(b)
  make_tree(a,b)
for i in range(Q):
  p,x = map(int,input().split())
  tree_num = top_list.index(p)
  count(tree_num,x)
count_list = [str(i) for i in count_list]
print(" ".join(count_list))

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
n, q = map(int, input().split())
ab = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]

ad_list = [deque([]) for _ in range(n)]
for a, b in ab:
  ad_list[a].append(b)

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

def dfs(v, x, ad):
  count[v] += x
  while ad[v]:
    if len(ad[v]) == 0:
      break
    ad_v = ad[v].pop()
    dfs(ad_v, x, ad)
    
for p, x in px:
  ad = copy.deepcopy(ad_list)
  dfs(p-1, x, ad)

print(*count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = {}
for i in range(N):
    edge_map[i] = deque([])

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0 for i in range(N)]

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

def dfs_res(idx, parent, diff):
    global res_list
    global counters
    if calculated[i]:
        return res_list[idx]
    res = counters[idx] + diff
    res_list[idx] = res
    calculated[idx] = True
    for child in edge_map[idx]:
        if child == parent:
            continue
        dfs_res(child, idx, res)
    return

dfs_res(0, None, 0)

ans = ""
for res in res_list:
    ans += str(res) + " "
print(ans)