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:
class node:
  count = 0
  def __init__(self, ID):
    self.id = ID

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

counts = [0] * N
seens = [False] * N
depth = [-1] * N
children = [[] for i in range(N)]

# root
depth[0] = 0

def dfs(root, x):
  if seens[root]: return
  counts[root] += x
  seens[root] = True
  for node in children[root]:
    dfs(node, x)

stack = []
for i in range(N-1):
  a, b = list(map(int, input().split(' ')))
  a -= 1
  b -= 1
  if depth[a] == -1 and depth[b] == -1: stack.append((a, b))
  elif depth[a] == depth[b]:
    children[a].append(b)
    children[b].append(a)
  else:
    p = -1
    c = -1
    if (depth[b] == -1 or depth[a] < depth[b]):
      p = a
      c = b
    else:
      p = b
      c = a
    depth[c] = depth[a] + 1
    children[p].append(c)

while stack:
  tap = stack.pop()
  a, b = tap
  if depth[a] == -1 and depth[b] == -1: stack.insert(0, (a, b))
  elif depth[a] == depth[b]:
    children[a].append(b)
    children[b].append(a)
  else:
    p = -1
    c = -1
    if (depth[a] > depth[b]):
      p = a
      c = b
    else:
      p = b
      c = a
    depth[c] = depth[a] + 1
    children[p].append(c)

for i in range(Q):
  r, x = list(map(int, input().split(' ')))
  seens = [False] * N
  dfs(r-1, x)

for i in range(N-1):
  print(counts[i], end=" ")
print(counts[N-1])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
parents={}
parents[1]=0
for _ in range(N-1):
    a,b=map(int,input().split())
    parents[b] = a
subtree=[[i] for i in range(N+1)]
for k,v in parents.items():
    n,m = k,v
    while m!=0:
        subtree[m].append(k)
        m=parents[m]
answers=[0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    for i in subtree[p]:
        answers[i-1] += x
print(*answers)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
A={}
# B={}
P=[]
X=[]
Parents=[[] for i in range(N)]
Daughters=[[]for i in range(N)]
Tree=[[]for i in range(N)]
Result=[0 for i in range(N)]
for i in range(N-1):
    a_, b_ = map(int, input().split())
    Parents[b_-1].append(a_)
    Daughters[a_-1].append(b_)
# print(A)
for i in range(N):
    Tree[i].extend([i+1])
    Tree[i].extend(Daughters[i])
    for d in Daughters[i]:
        Tree[i].extend(Daughters[d-1])

# print(Parents)
# print(Daughters)
# print(Tree)

for i in range(Q):
    p_, q_ = map(int, input().split())
    for tr in Tree[p_-1]:
        Result[tr-1]+=q_
    P.append(p_)
    X.append(q_)

Result=[str(i) for i in Result]
Result = ' '.join(Result)
print(Result)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit, stdin

setrecursionlimit(100000)


class Node:
    def __init__(self, num):
        self.num = num
        self.children = []
        self.value = 0

    def append(self, child):
        self.children.append(child)

    def add_value(self, value):
        self.value += value


def spam(nodes, dic1, dic2, flags, num):
    index = num - 1
    flags[index] = True
    node = nodes[index]
    nums = dic1.get(num, []) + dic2.get(num, [])
    nums = [x for x in nums if not flags[x - 1]]
    for n in nums:
        node.append(nodes[n - 1])
        spam(nodes, dic1, dic2, flags, n)


def ham(nodes, num, value):
    index = num - 1
    node = nodes[index]
    node.add_value(value)
    for n in node.children:
        ham(nodes, n.num, value)


def main():
    N, Q = [int(x) for x in stdin.readline().rstrip().split()]
    ab = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N - 1)]
    px = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(Q)]
    dic1 = {}
    dic2 = {}
    flags = [False for _ in range(N)]
    for a, b in ab:
        if a in dic1:
            dic1[a].append(b)
        else:
            dic1[a] = [b]
        if b in dic2:
            dic2[b].append(a)
        else:
            dic2[b] = [a]
    nodes = [Node(i + 1) for i in range(N)]
    spam(nodes, dic1, dic2, flags, 1)
    for p, x in px:
        ham(nodes, p, x)
    for n in nodes:
        print(n.value, end=' ')
    print('')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline

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:
n, q = map(int, input().split())
ed = dict([(i+1,set()) for i in range(n)]) #[[] for i in range(n)]
cd = dict([(i+1,set()) for i in range(n)]) #[[] for i in range(n)]
r = {i+1 for i in range(n)} #[i+1 for i in range(n)]
cnt = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    ed[a].add(b)
    ed[b].add(a)

st = [1]
while len(st) != 0:
    v = st.pop()
    d = ed[v] & r
    cd[v] = d
    for item in {i+1 for i in range(n)} - r:
        cd[item] = cd[item] | d
    r.remove(v)
    st += d

for i in range(q):
    p, x = map(int, input().split())       
    cnt[p-1] += x
    for item in cd[p]:
        cnt[item-1] += x
        
ans = ""
for c in cnt:
    ans += (str(c) + " ")

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

N,Q = map(int,input().split())
ab_list = [tuple(map(int,input().split())) for _ in range(N-1)]
px_list = [tuple(map(int,input().split())) for _ in range(Q)]

px_dict = {}
for i in range(N+1):
    px_dict[i] = 0

for p, x in px_list:
    px_dict[p] += x

ab_dict = {}
for i in range(N+1):
    ab_dict[i] = []

for a,b in ab_list:
    ab_dict[a].append(b)

scores = [0 for _ in range(N+1)] # 1子おおい

def add_cnt(v, score):
    # pxdictから持ってきてスコアを足す
    score += px_dict[v]
    # スコアを足さないこともある
    
    #今いる頂点に現在のスコアをめも
    scores[v] = score
    
    # 繋がっている頂点に今のスコアを投げる
    for b in ab_dict[v]:
        add_cnt(b,score)

add_cnt(1,0)

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

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
abL = [[int(x) for x in input().split()] for _ in range(N-1)]
tree = [[0]*(N+1) for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for a,b in abL:
    graph[a].append(b)

for a in range(N, 0, -1):
    incL = graph[a]
    for b in incL:
        for i in range(a):
            if a in graph[i]:
                graph[i].append(b)
    graph[a].append(a)

pxL = [[int(x) for x in input().split()] for _ in range(Q)]

for p,x in pxL:
    tmpL = graph[p]
    for b in tmpL:
        tree[p][b] += x

for i in range(1, N+1):
    sum_ = 0
    for j in range(1, N+1):
        sum_ += tree[j][i]
    print(sum_, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, Q = map(int, input().split())
ans = np.zeros((N+1), dtype=np.int)
graph = {i:[None, []] for i in range(1, N+1)}
nums = [False] * (N)
visited = [False] * (N+1)

for i in range(N-1):
    a, b = map(int, input().split())
    graph[b][0] = a
    graph[a][1].append(b)
    nums[a] = True
        
q = [idx+1 for idx, _ in enumerate(nums) if not _]

while q:
    n = q.pop(0)
    visited[n] = True

    par, child = graph[n]
    if not par is None and not visited[par]:
        graph[par][1].extend(child)
        q.append(par)
        
for i in range(Q):
    p, x = map(int, input().split())
    ans[p] += x
    
for i in range(1, N+1):
    ans[graph[i][1]] += ans[i]
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
 
tree = [[i] for i in range(N+1)]
tree_parent = [[0] 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)
  tree_parent[b].append(a)  
  tree[tree_parent[a][-1]].append(b)
    
for i in range(Q):
  p, x = map(int, input().split())
  for node in tree[p]:
    points[node-1] += x
    
for point in points:
  print(point, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

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

def func(p, now):
    global res
    res[p-1]+=px[p-1]+now
    for i in ab[p-1]:
        func(i, res[p-1])

res=[0]*n

func(1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    edges = [set() for i in range(N+1)]
    score = [0] * (N+1)

    for i in range(N-1):
        edges[a[i]].add(b[i])
        edges[b[i]].add(a[i])

    for i in range(Q):
        # print(p[i], [z for z in edges[p[i]] if z > p[i]], x[i])
        # すべての以下のものに配布されるようにする
        tl = [p[i]]
        al = set()
        al.add(p[i])
        while(len(tl) != 0):
            t = tl.pop(0)
            tl += [s for s in edges[t] if s > t]
            # print("tl", tl, set(tl))
            al = al | set(tl)
            # print("al", al)
        # print(p[i], al, x[i])
        for y in al:
            score[y] += x[i]

    print(' '.join(map(str,score[1:])))

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]" 
    x = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

num_node, num_query = map(int, input().split())
node_info = [map(int, input().split()) for i in range(num_node-1)]
query_info = [map(int, input().split()) for i in range(num_query)]

numpy_layer = np.zeros(num_node)
numpy_size = np.zeros(num_node)
numpy_layer[0] = 1

for node in node_info:
    a1, b1 = node
    a1_layer = numpy_layer[int(a1)-1]
    numpy_layer[int(b1)-1] = a1_layer + 1

for query in query_info:
    node, size = query
    node_size = int(numpy_layer[node-1])
    numpy_size[node-1] += size
    # 根を探す
    #np.where(numpy_layer > node_size, numpy_size + size, numpy_size)
    numpy_size[np.where(numpy_layer > node_size)] += size

numpy_size = numpy_size.astype("int64")
print(*numpy_size)

Submission status: Time Limit Exceeded

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

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

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

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:
import collections as C
n, q = map(int,input().split())

g = C.Counter([])
p = C.Counter([])

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

for i in range(q):
	a,b = map(int,input().split())
	if a not in p.keys():
		p[a] = b
	else:
		p[a] = p[a] + b

ans = [0 for _ in range(n)]
que = [0]
i = 1
while i > 0:

	if i in p.keys():
		ans[i-1] += p[i]
	if i in g.keys():
		for j in g[i]:
			ans[j-1] = ans[i-1]
			que.append(j)
	i = que.pop()


for i in ans:
	print(i, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,q = map(int,input().split())
lst = {}
for _ in range(n-1):
  l,r = map(int,input().split())
  try:
    lst[l].append(r)
  except:
    lst.update({l:[r]})
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
    try:
      temp+=lst[search_num]
    except:
      pass
ans = " ".join([str(i) for i in counter])
print(ans)

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}
        ans[p-1] += x
        bn = len(br)
        for j in range(p-1,n-1):
            if(ab[j][0] in br):
                br.add(ab[j][1])
                if(bn != len(br)):
                    ans[ab[j][1]-1] += x
                    bn = len(br)
                    """
        for k in br:
            ans[k-1] += x
            """

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

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(int, input().split()))
c = [0] * (n + 1)
pc = [[] for x in range(n + 1)]     # 親から子
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    pc[a].append(b)
for i in range(n, 0, -1):
    for j in pc[i]:
        pc[i].extend(pc[j])
for i in range(q):
    p, x = list(map(int, input().split()))
    c[p] += x
    for i in pc[p]:
        c[i] += x
for i in range(1, n + 1):
    print("{} ".format(c[i]), end="")
print("")

Submission status: Time Limit Exceeded

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

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

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

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

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

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

    """def bfs(circlepoint):
        flag = [[0 for _ in range(10)] for _ in range(10)]
        queue = deque()
        queue.append(circlepoint)
        while queue != deque():
            cri_i, cri_j = queue.popleft()
            for dx, dy in dd:
                nx = cri_j + dx
                ny = cri_i + dy
                if 0 <= nx < 10 and 0 <= ny < 10:
                    if a[ny][nx] == "o" and flag[ny][nx] == 0:
                        queue.append((ny, nx))
                        flag[ny][nx] = 1
        for i in range(10):
            for j in range(10):
                if a[i][j] == "o" and flag[i][j] == 0:
                    return False
        else:
            return True"""



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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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


class Node:
    def __init__(self, index):
        self.index = index
        self.point = 0

    def updatePoints(self, point):
        self.point += point


# 2*10**5
nodes = [Node(i) for i in range(1, n + 1)]

# 2*10**5
edges = defaultdict(list)
for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)


def memoize(f):
    memo = {}

    def memoized(*args):
        if args not in memo.keys():
            memo[args] = f(*args)
        return memo[args]
    return memoized

@memoize
def selectNode(p):
    selected = [p]
    ls = edges[p]
    selected += ls

    while True:
        if ls == []:
            break
        for x in ls:
            ls = edges[x]
            selected += ls
    return selected

for _ in range(q):
    p, x = map(int, input().split())
    node_index_list = selectNode(p)
    for idx, node in enumerate(nodes):
        if idx + 1 in node_index_list:
            node.updatePoints(x)

print(*(node.point for node in nodes))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
memo = [[i] for i in range(N)]
flg = [False]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)

ans = [0]*N
add = [0]*N

for i in range(Q):
    p, x = map(int, input().split())
    if flg[p-1] is False:
        flg[p-1] = True
        ans[p-1] += x
        queue = [p-1]
        while queue:
            par = queue.pop(0)
            if G[par]:
                for i in G[par]:
                    ans[i] += x
                    queue.append(i)
                    memo[p-1].append(i)
    elif flg[p-1] is True:
        add[p-1] += x
        flg[p-1] = -1
    else:
        add[p-1] += x

ct = 0
for i in flg:
    if i == -1:
        for j in memo[ct]:
            ans[j] += add[ct]
    ct += 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
a=[]
b=[]
p=[]
x=[]
s=[0]


for i in range(0,n-1):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
    s.append(0)
for i in range(0,q):
    P,X=map(int,input().split())
    p.append(P)
    x.append(X)
    s[P-1]=s[P-1]+X


for i in range(1,n):
    for j in range(0,n-1):
        if i==a[j]:
            s[b[j]-1]=s[b[j]-1]+s[i-1]
        

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

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 defaultdict
n, q = map(int, input().split())
child_dict = defaultdict(set)
value_dict = defaultdict(lambda: 0)
for _ in range(n - 1):
    a, b = map(int, input().split())
    child_dict[a].add(b)
import copy
for _ in range(q):
    c, d = map(int, input().split())
    value_dict[c] += d
    child = child_dict[c]
    while len(child) > 0:
        k = []
        for i in child:
            value_dict[i] += d
            k.extend(child_dict[i])
        child = copy.deepcopy(k)
ans = [value_dict[i] for i in range(1 ,n+1)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def score(x):
    cur = x
    p = 0
    while cur>0:
        p += T[cur][2]
        cur = T[cur][0]
    return p
N,Q = map(int,input().split())
G = {}
for _ in range(N-1):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
T = {i:[0,[],0] for i in range(1,N+1)}
cur = 1
T[cur][1] = G[cur]
T[cur][0] = -1
hist = deque([cur])
while hist:
    cur = hist.popleft()
    for y in T[cur][1]:
        T[y][0] = cur
        G[y].remove(cur)
        T[y][1] = G[y]
        hist.append(y)
for _ in range(Q):
    p,x = map(int,input().split())
    T[p][2] += x
S = []
for i in range(1,N+1):
    S.append(score(i))
print(*S)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, q = (int(i) for i in input().split())
tree = dict()
for i in range(n-1):
    p, c = (int(j) for j in input().split())
    child = tree.get(p-1, [])
    tree[p-1] = child + [c-1]
cnt = np.zeros(n, dtype='int64')
for i in range(q):
    p, x = (int(j) for j in input().split())
    cnt[p-1] = cnt[p-1] + x
q = list([0])
while len(q) > 0:
    idx = q.pop(0)
    child = tree.get(idx, [])
    cnt[child] = cnt[child] + cnt[idx]
    q = q + child
print(' '.join([str(c) for c in cnt]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
l=[None]*N
l[0]=[1,1,0]
for i in range(1,N):
    a,b=map(int,input().split())
    l[i]=[b,a,0]
l.sort()
for i in range(Q):
    p,x=map(int,input().split())
    l[p-1][2]+=x
print(l[0][2],end=" ")
for i in range(1,N):
    l[i][2]+=l[l[i][1]-1][2]
    print(l[i][2],end=" ")

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


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

    def make_link(self, other):
        self.link.add(other)
        other.link.add(self)

    def make_child(self, parent=None):
        if parent:
            self.link.remove(parent)
        self.children = list(self.link)
        for child in self.children:
            child.make_child(parent=self)

    def search_all_children(self):
        self.all_children = self.children
        for child in self.children:
            self.all_children += child.search_all_children()
        return self.all_children

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


n, q = map(int, input().split())
ab = sorted([sorted(list(map(int, input().split()))) for _ in range(n-1)], key=lambda x: x[0])
# add x to nodes[p-1]
px = [list(map(int, input().split())) for _ in range(q)]

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

for c in ab:
    nodes[c[0]-1].make_link(nodes[c[1]-1])

nodes[0].make_child()
nodes[0].search_all_children()

for q in px:
    nodes[q[0]-1].count_all(q[1])

for node in nodes:
    print(node.count, end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int,input().rstrip().split(' ')))
sum = [0]*N
connected = list()
from functools import lru_cache

for _ in range(N-1):
    connected.append(list(map(int,input().rstrip().split(' '))))

@lru_cache(maxsize=1000)
def subtree(node):
    sub_tree_list = []
    for c in connected:
        if c[0] == node:
            sub_tree_list.append(c[1])

    if sub_tree_list == []:
        return [node]
    else:
        tmp = []
        for sub in sub_tree_list:
            tmp += subtree(sub)
        return [node] + tmp

for _ in range(Q):
    p, x = list(map(int,input().rstrip().split(' ')))
    sub = subtree(p)
    for y in sub:
        sum[y-1] += x

for r in sum:
    print(r, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
from bisect import bisect, bisect_left


class Node:
    def __init__(self, idx):
        self.idx = idx
        self.v = 0
        self.parent = None
        self.children = []

    def add(self, x):
        self.v += x
        for c in self.children:
            c.add(x)

    def make_tree(self):
        keyidx = bisect_left(brs_keys, self.idx)
        while keyidx < len(brs_keys) and brs_keys[keyidx] == self.idx:
            ni = brs[keyidx][1]
            node = nodes[ni]
            if not node.children:
                self.children.append(node)
            keyidx += 1
        for c in self.children:
            c.make_tree()

    def __str__(self):
        return str(self.idx)


N, Q = [int(_) for _ in input().split()]
nodes = [Node(i) for i in range(0, N)]

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

brs.sort()
brs_keys = [b[0] for b in brs]
nodes[0].make_tree()

# for n in nodes:
#     print(n.idx, [str(c) for c in n.children])

for i in range(Q):
    p, x = [int(_) for _ in input().split()]
    nodes[p - 1].add(x)

print(*[n.v for n in nodes])

Submission status: Time Limit Exceeded

Solution code:
# 再帰
def dfs(p,x):
    flag = 0
    # 部分木をみていく(i番目の頂点の子はi+1番目以上だと仮定している)
    for i in range(p, N+1):
        if ab_aj[p-1][i-1] == 1:
            flag = 1
            counter[i-1] += x
            dfs(i,x)
    if flag == 0:
        return

if __name__ == "__main__":
    # 入力
    N, Q = map(int, input().split())
    # 隣接行列を求める
    ab_aj = [[0]*(N) for _ in range(N)]
    for i in range(N-1):
        a,b = map(int, input().split())
        ab_aj[a-1][b-1] = 1
        ab_aj[b-1][a-1] = 1

    # 操作のデータを保持
    px = [list(map(int, input().split())) for _ in range(Q)]

    # 頂点のカウンターの値を保持
    counter = [0 for _ in range(N)]
    
    # 操作ごとにループ
    for i in range(Q):
        p = px[i][0]
        x = px[i][1]
        counter[p-1] += x
        dfs(p,x)
    for i in range(N):
        print(counter[i], end="")
        print(" ", end="")
    print()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
G = [tuple(map(int, input().split())) for _ in range(N-1)]
W = [tuple(map(int, input().split())) for _ in range(Q)]

# 木の隣接関係 (a<bは保証されている)
M = [[] for _ in range(N+1)]
for g in G:
    M[g[0]].append(g[1])

# print(M)

# 木の親子関係
P = [[] for _ in range(N+1)]
# dfs
visited = []

def dfs(start):
    Stack = [start,]
    while Stack:
        now = Stack.pop(0)
        visited[now] = 1
        for child in M[now]:
            if not visited[child]:
                Stack.append(child)

for parent in range(1, N+1):
    visited = [0,] * (N+1)
    dfs(parent)
    P[parent].extend([i for i, s in enumerate(visited) if s])

# print(P)

res = [0,] * (N+1)
for p, x in W:
    for pp in P[p]:
        res[pp] += x

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

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

tyouten = [list(map(int,input().split())) for _ in range(n-1)]
tree = [list(map(int,input().split())) for _ in range(q)]
ans = [0] * n
temp = [] * n
for i in range(n):
    temp.append([i+1])
temp[0] = [x for x in range(1,n+1)]    

tyouten.sort()

for i in range(n-1):
    if i == 0:
        continue
    temp[tyouten[i][0]-1].append(tyouten[i][1])


for i in range(q):
    s = tree[i][0] - 1
    t = tree[i][1]
    if s == 0:
        for i in range(n):
            ans[i] += t
    else:
        for i in temp[s]:
            ans[i-1] += t

print(*ans)