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:
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
for i in range(n):
    for j in tree[i]:
        if i != j:
            tree[i] += tree[j]
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
    for j in tree[p - 1]:
        counter[j] += x
print(*counter)

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:
        return
    for node in chil[toN]:
        cleanse(toN, node)

def connect(fromN, toN):
    chil[toN].remove(fromN)
    if len(chil[toN])==0:
        return
    for node in chil[toN]:
        cleanse(toN, node)

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

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

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

print(*count[1:])

Submission status: Time Limit Exceeded

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

ans=[0]*N
ab=[[] for i in range(N)]

for _ in range(N-1):
    a,b=map(int,input().split())
    ab[a-1].append(b-1)
    
for j,item in enumerate(ab[::-1]):
    for i in item:
        ab[N-j-1].extend(ab[i])

#for i in range(N):
#    ab[i]=list(set(ab[i]))
    
for _ in range(Q):
    p,x=map(int,input().split())
    for i in ab[p-1]:
        ans[i]=ans[i]+x
    ans[p-1]=ans[p-1]+x
#    print(ans) 

print(str(''.join(str(j)+' ' for j in ans)[:-1]))

Submission status: Time Limit Exceeded

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

p = [0 for i in range(Q)]
x = [0 for i in range(Q)]
for i in range(Q):
    parent, x[i] = map(int, input().split())
    p[i] = parent - 1
child = [[] for i in range(N)]
visited = [False for i in range(N)]
def bfs(v):
    Q = []
    visited[v] = True
    Q.append(v)
    while len(Q) > 0:
        u = Q.pop(0)
        for v in graph[u]:
            if visited[v] == False:
                visited[v] = True
                child[u].append(v)
                Q.append(v)
bfs(0)
#print(child)

def bfs2(v, x):
    Q = []
    visit[v] += x
    Q.append(v)
    while len(Q) > 0:
        u = Q.pop(0)
        for vv in child[u]:
            visit[vv] += x
            Q.append(vv)

visit = [0 for i in range(N)]
for i in range(Q):
    bfs2(p[i], x[i])
visit = [str(i) for i in visit]
print(' '.join(visit))

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
#+++++
		
def main():
	n,q = map(int, input().split())
	tree=[[] for _ in range(n+1)]
	hh=[ 0 for _ in range(n+1)]
	ret=[0 for _ in range(n+1)]
	
	for i in range(n-1):
		pa,ch = map(int, input().split())
		tree[pa].append(ch)
		
	for v in range(q):
		nd, hv = map(int, input().split())
		hh[nd] += hv
		
	ol = queue.Queue()
	ret[1]=hh[1]
	vv=hh[1]
	for cc in tree[1]:
		ol.put((vv,cc))
		
	while not ol.empty():
		ph,nd=ol.get()
		ret[nd]=hh[nd]+ph
		vv=ret[nd]
		for cc in tree[nd]:
			ol.put((vv,cc))

	print(' '.join([str(v) for v in ret[1:]]))
	
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

p = [0]*q
x = [0]*q

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


score = [0]*n

def down_tree(parent, add_score):
    global score
    for i in range(q):
        if p[i]-1 == parent:
            add_score += x[i]
    for i in range(n-1):
        if a[i]-1 == parent:
            down_tree(b[i]-1, add_score)

    score[parent] += add_score

    return 0

down_tree(0, 0)

print(*score)

Submission status: Time Limit Exceeded

Solution code:

N, Q = list(map(int, input().split()))
eda = [[] for i in range(N)]
ope = [0]*N
score = [0]*N
parent = [-1]*N


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

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


que = []
que.append(0)
score[0] = ope[0]
for ss in range(N - 1):
	loc = que.pop()
	for edge in eda[loc]:
		if parent[loc] != edge:
			score[edge] += score[loc] + ope[edge]
			que.append(edge)
			parent[edge] = loc

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000000)


class Node:
  def __init__(self, v, next=None):
    self.v = v
    self.next = next


class Graph:

  def __init__(self, N):
    self.V = [0] * (N + 1)
    self.E = [None] * (N + 1)

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


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

  def walk(u, current_value=0):
    current_value += G.V[u]
    result[u - 1] = current_value
    node = G.E[u]
    while node is not None:
      walk(node.v, current_value)
      node = node.next

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

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi)
    graph[bi - 1].append(ai)

# print("#", graph)

cnttab = [0] * N
for j, (pj, xj) in enumerate(px):
    cnttab[pj - 1] += xj

# print("#", cnttab)

ans = [None] * N
ans[0] = cnttab[0]
from collections import deque
q = deque([(1, None, ans[0])])
while len(q) > 0:
    src, prev, score = q.popleft()
    for dst in graph[src - 1]:
        if dst == prev: continue
        ans[dst - 1] = score + cnttab[dst - 1]
        if len(graph[dst - 1]) > 1:
            q.append((dst, src, ans[dst - 1]))

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000000)

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

tree = [[] for _ in range(n)]
ope = [0]*n
opef=[False]*n
ret=[0]*n

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

def counter(target,num):
    global ret
    global ope
    global opef
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        tmp=0
        if opef[i]==False:
            tmp=ope[i]
            opef[i]=True
        counter(i,num+tmp)

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

counter(0,ope[0])

print(*ret)

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

    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 = {p[i]}
        while(len(tl) != 0):
            t = tl.pop(0)
            tl += edges[t]
            al |= set(tl)
        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:
N, Q = map(int, input().split())
a = [0] * N
b = [0] * N
p = [0] * Q
x = [0] * Q
isTree = [False] * N
output = [0] * N

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

for i in range(Q):
    isTree = [False] * N
    for j in range(N):
        isTree[p[i] - 1] = True
        if p[i] == a[j] or isTree[a[j] - 1]:
            isTree[b[j] - 1] = True
    for k in range(N):
        if isTree[k]:
            output[k] += x[i]

print(*output)

Submission status: Time Limit Exceeded

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

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

c = [0]*N
res = [0]*N
for p,x in PX:
    c[p-1] += x

def BFS(start,edges,N,c):
    roots=[[] for _ in range(N)]
    for a,b in edges:
        roots[a-1]+=[(b-1,c[b-1])]
        roots[b-1]+=[(a-1,0)]
    queue=[]
    visited=[start]
    queue.append(start)
    res[start] = c[start]
    while queue:
        label = queue.pop()
        for i,c in roots[label]:
            if i not in visited:
                res[i]= res[label]+c
                queue += [i]
                visited.append(i)
    return res
print(*BFS(0,edges,N,c))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from collections import defaultdict

N, Q = list(map(int,input().rstrip().split(' ')))
sum = [0]*N
connected = list()

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

direct_sub_node = defaultdict(list)
for node in range(2, N+1):
    for c in connected:
        if c[0] == node:
            direct_sub_node[node].append(c[1])


@lru_cache(maxsize=1000)
def subtree(node):
    if node == 1:
        return list(range(1,N+1))
    sub_tree_list = direct_sub_node[node]

    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
input = sys.stdin.readline

[n,q]=[int(x) for x in input().split()]
ab=[[int(x) for x in input().split()] for _ in range(n-1)]
px=[[int(x) for x in input().split()] for _ in range(q)]

bubungi=[[x] for x in range(1,n+1)]
ab.sort()
for node in ab[::-1]:
    bubungi[node[0]-1]=bubungi[node[0]-1]+bubungi[node[1]-1]

scores=[0,]*n
for q in px:
    for i in bubungi[q[0]-1]:
        scores[i-1]+=q[1]

print(" ".join([str(s) for s in scores]))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
tl = [list() for _ in range(n)]
ab = []
ans = [0] * n

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

ab.sort(reverse=True)

for a, b in ab:
    a -= 1
    b -= 1
    tl[a].append(b)
    tl[a].extend(tl[b])

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

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

Submission status: Time Limit Exceeded

Solution code:
line1 = input().split()
n = int(line1[0])
q = int(line1[1])

sahen = [0 for num in range(n)]

for num in range(n-1):
  inp =input().split()
  sahen[num] = int(inp[0])

j = [0 for num in range(q)]
for num in range(q):
  inpt =input().split()
  j[num] = [int(inpt[0]),int(inpt[1])]

result = [0 for num in range(n)]

for num2 in j:
  if (num2[0] in sahen):
    start = sahen.index(num2[0])
    for num in range(start,n):
      result[num] += num2[1]
  else:
    result[num2[0]-1] += num2[1]

print(*result)

Submission status: Time Limit Exceeded

Solution code:
import queue

N,Q = map(int,input().split())
Ki_p = [0 for i in range(N+1)]
Ki_c = [[] for i in range(N+1)]
Ki_co = [0 for i in range(N+1)]
 
for i in range(N-1):
    a,b = map(int,input().split())
    Ki_p[b] = a
    Ki_c[a] += [b]
 
for i in range(Q):
    p,x = map(int,input().split())
    Ki_co[p] += x
 
ans = [0 for i in range(N+1)]
q = queue.Queue()
q.put(1)
while not q.empty():
    vi = q.get()
    ans[vi] = Ki_co[vi] + ans[Ki_p[vi]]
    for a in Ki_c[vi]:
        q.put(a)
 
print(' '.join(map(str,ans[1:N+1])))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def resolve():
    n, q = map(int, input().split())
    ab = sorted(list(list(map(int, input().split())) for _ in range(n - 1)))
    pq = list(list(map(int, input().split())) for _ in range(q))
    d = defaultdict(list)
    counters = [0] * n
    for a, b in ab:
        d[a].append(b)
    for p, q in pq:
        child = d[p]
        nodes = [p] + child
        while any([c in d for c in child]):
            new_nodes = []
            for c in child:
                if c in d:
                    new_nodes += d[c]
            child = new_nodes
            nodes += new_nodes
        for n in nodes:
            counters[n - 1] += q
    print(" ".join([str(c) for c in counters]))


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N,Q = (int(i) for i in input().split())
X = []
for i in range(N-1):
    Y = [int(n) for n in input().split()]
    X.append(Y)
X = sorted(X, key=lambda x:x[1])
Z = [] 
for i in range(N):
    Z.append(0)
    
for i in range(Q):
    Z_1,Z_2 = (int(i) for i in input().split())
    Z[Z_1-1] = Z[Z_1-1] + Z_2

#print(X)
#print(Z)

ans=[]
for i in range(N):
    ans.append(0)
ans[0]=Z[0]

for i in range(1,N):
    ans[i] += Z[i]
    for n in range(len(X)):
        if X[n][1] == i+1:
            ans[i] += ans[X[n][0]-1]
            A = n+1
        else:
            for i in range(A):
                X.pop(0)
            break

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
gu = [set() for _ in range(n)]
gl = [set() for _ in range(n)]

def upper(a,b):
  if gu[a] == {}:
    gl[a].add(b)
  else:
    gl[a].add(b)
    for l in gu[a]:
      upper(l, b)

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

#print(gu)
#print(gl)

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

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

Submission status: Time Limit Exceeded

Solution code:

def main():
    
    
    in1 = [int(e) for e in input().split()]
    n = in1[0]
    q = in1[1]

    a = []
    b = []
    for i in range(n-1):
        in1 = [int(e) for e in input().split()]
        a.append(in1[0])
        b.append(in1[1])

    p = []
    x = []
    for i in range(q):
        in1 = [int(e) for e in input().split()]
        p.append(in1[0])
        x.append(in1[1])

    l = [0] * n

    def addval(p,x):
        l[p-1] += x

        for j in range(n-1):
            #print('j',j)
            if(a[j] == p):
                addval(b[j],x)

    for i in range(q):
        addval(p[i],x[i])

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




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

import sys
sys.setrecursionlimit(100000)

# N <= 2*10^5
# Q <= 2*10^5
N, Q = [int(x) for x in stdin.readline().rstrip().split()]
#ab = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]
#px = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]

ans = [0] * (N+1)
child = [[] for _ in range(N+1)]


def add(node, num):
    for x in child[node]:
        add(x, num)

    ans[node] += num

for a, b in [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]:
    child[a].append(b)

#print(child)

for p, x in [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]:
    ii = p
    add(p, x)

print(*ans[1:], sep=" ")

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**6)
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


point_root = [0] * N
query = [None]
for i in range(Q):
    p,x = map(int, input().split())
    point_root[p-1] += x 
point_root = tuple(point_root)
ans = [0] * N
visited = [False] * N
#ans[0] = point_root[0]
#visited[0] = True
def solve(node, point):
    #print("aa", *ans)
    ans[node] += point
    visited[node] = True
    if all(visited) == True:
        print(*ans)
        exit()

    if es.get(node, None) != None:
        next_nodes = (es[node]) # これからポイントを足し行くやつら
        for i in next_nodes:
            solve(i, point+point_root[i])
solve(0, point_root[0])

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


def dfs(tree: dict, count: list) -> list:
    res = [0] * (N + 1)

    stack = [1]
    while stack:
        label = stack.pop(0)
        res[label] = count[label]
        if tree[label] != []:
            for next_label in tree[label]:
                count[next_label] += count[label]
            stack = tree[label] + stack

    return res


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

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

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

ans = dfs(tree, count)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Aug 18 21:19:43 2019
ABC138D
@author: maezawa
"""

n, q = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    graph[ai].append(bi)
    graph[bi].append(ai)
    
parent = [[] for _ in range(n+1)]
child = [[] for _ in range(n+1)]
current = 1
while current <= n:
    for j in graph[current]:
        if current in child[j]:
            continue
        child[current].append(j)
    current += 1
#print(child)
parray = [-1]*(n+1)
parray[1] = 0
for i in range(1,n+1):
    for j in child[i]:
        parray[j] = i
#print(parray)
tpoint = [0]*(n+1)
for i in range(q):
    pi, xi = list(map(int, input().split()))
    tpoint[pi] += xi
tpmem = [-1]*(n+1)
for i in range(1, n+1):
    pi = 0
    j = i
    while True:
        if tpmem[j] != -1:
            pi += tpmem[j]
            break
        pi += tpoint[j]
        if parray[j] == -1:
            break
        j = parray[j]
    print(pi)
    tpmem[i] = pi

Submission status: Time Limit Exceeded

Solution code:

def get_root_counter(counter, root_num):
    counter += counter_add_dict[root_num]
    if tree_root_dict[root_num] == 0:
        return counter

    return get_root_counter( counter, tree_root_dict[root_num])

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

C = [0] * (N+1)

tree_root_dict = {}
for i in range(N):
    tree_root_dict[i] = 0

# make tree
for i in range(N-1):
    a, b = map(int, input().split(" "))
    tree_root_dict[b] = a

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

# get counters
for i in range(Q):
    p, x = map(int, input().split(" "))
    counter_add_dict[p] += x

# add counters
for i in range(1, len(tree_root_dict)):
    C[i] = get_root_counter(counter_add_dict[i], tree_root_dict[i])

# print counters
ans = ""
for i in range(1, N+1):
    ans += str(C[i]) + " "

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, Q = map(int, input().split())
#a = [0] * (N - 1)
#b = [0] * (N - 1)
p = [0] * Q
x = [0] * Q
link = [[] for _ in range(N)]
children = [[i] for i in range(N)]
arrived = [0] * N

def dps(v):
	arrived[v] = 1
	tmp_list = []
	
	for i in link[v]:
		if arrived[i] == 0:
			tmp_list.append(dps(i))
			
	for j in tmp_list:
		for k in j:
			children[v].append(k)
		
	return children[v]

for i in range(N - 1):
	#a[i], b[i] = map(int, input().split())
	a, b = map(int, input().split())
	a -= 1
	b -= 1
	link[a].append(b)
	link[b].append(a)
	
dps(0)
ans = [0] * N
	
for i in range(Q):
	tmp_p, x[i] = map(int, input().split())
	p[i] = tmp_p - 1
	
	for j in children[p[i]]:
		ans[j] += x[i]
		
for i in range(N):
	print(ans[i], end=' ')

Submission status: Time Limit Exceeded

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

for i in range(N-1):
    new_a, new_b = map(int, input().split())
    tmp_branch = branch_list[new_a-1]
    tmp_branch.append(new_b)
    branch_list.pop(new_a-1)
    branch_list.insert(new_a-1, tmp_branch)

score_list = []
for i in range(N):
    score_list.append(0)

def branch_adder(p, x):
    p_branch = branch_list[p-1]
    score_list[p-1] += x
    for i in range(len(p_branch)):
        branch_adder(p_branch[i], x)

for i in range(Q):
    new_p, new_x = map(int, input().split())
    branch_adder(new_p, new_x)

for i in range(N):
    print(score_list[i], end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N,Q = map(int,input().split())
d = defaultdict(list)

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

c = defaultdict(int)

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

ans = [0 for i in range(N)]
que = [(1,0,-1)]
while len(que)>0:
    tmp = []
    for v,x,par in que:
        x += c[v]
        ans[v-1] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w,x,v))
    que = tmp

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
dic = {}
amari = {}
for i in range(N-1):
  k, v = map(int, input().split())
  try:
    dic[k].append(v)
  except KeyError:
    dic[k] = [v]
  try:
    amari.pop(k)
  except:
    pass
  amari[v] = None
for i in amari.keys():
  dic[i] = []
counter = [list(map(int, input().split())) for i in range(Q)]
q = {i: 0 for i in dic.keys()}
 
def child_sum(q,v, child):
  if child == []:
    return q
  else:
    for j in child:
      q[j] += v
      child = dic[j]
      q = child_sum(q, v, child)
  return q
    
for i, v in counter:
  q[i] += v
  child = dic[i]
  #print(q, i, child)
  q = child_sum(q, v, child)
print(' '.join([str(i) for i in q.values()]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():

    N, Q = [int(x) for x in input().split()]
    counter = {key:0 for key in range(1, N+1)}
    parent_dict = dict()
    child_data = defaultdict(set)
    child_data[1] = set([1])

    # 要は木構造っぽいものを作りたいが、再起関数だと処理時間で死んだ
    # なので、親一覧 + 自分のリストを作成する
    for _ in range(N - 1):
        a, b = [int(x) for x in input().split()]
        parent_dict[b] = a
        child_data[b].add(b)
        temp = b
        while temp in parent_dict:
            temp = parent_dict[temp]
            child_data[temp].add(b)
    
    # print(parent_dict)
    # print(child_data)

    # 親一覧 + 自分のリストから答えを出す   
    for _ in range(Q):
        p, x = [int(x) for x in input().split()]
        for key in child_data[p]:
            counter[key] += x

    print(" ".join([str(val) for key, val in sorted(counter.items())]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
 
N,Q = (int(i) for i in input().split())
hen = {}
value = [0] * N
flag = [0] * N
for i in range(0,N-1):
    a,b = (int(i) for i in input().split())
    if a in hen:
        hen[a].append(b)
    else:
        hen[a] = [b]
#print(hen)

def add(p,x):
    if p in hen:
        for i in hen[p]:
            value[i-1] = value[i-1] + x
            add(i,value[i-1])

for i in range(0,Q):
    p,x = (int(i) for i in input().split())
    value[p-1] = value[p-1] + x


add(1,value[0])
print(' '.join(map(str,value)))

Submission status: Time Limit Exceeded

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

trees = {}
for _ in range(N - 1):
    id1, id2 = map(int, input().split())
    if id1 not in trees:
        trees[id1] = []
    trees[id1].append(id2)

values = {}
for _ in range(Q):
    nid, val = map(int, input().split())
    if nid not in values:
        values[nid] = 0
    values[nid] += val

counters = {}
for nid, val in values.items():
    stack = [nid]
    while len(stack) > 0:
        myid = stack.pop()
        if myid not in counters:
            counters[myid] = 0
        counters[myid] += val
        if myid in trees:
            stack.extend(trees[myid])

ret = []
for myid in range(1, N + 1):
    if myid not in counters:
        ret.append(str(0))
    else:
        ret.append(str(counters[myid]))
        
print(' '.join(ret))

Submission status: Time Limit Exceeded

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

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

dic={}
inv_dic={}
for a,b in ab_list:
    inv_dic[b]=a
for i in range(N):
    dic[i+1]=[i+1]

for key,item in inv_dic.items():
    next_key=key
    while True:
        dic[item].append(key)
        if item in inv_dic.keys():
            item=inv_dic[item]
        else:
            break   

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 bisect
import sys

sys.setrecursionlimit(200000)

n,q = (int(num) for num in input().split())
neighbor = [[] for _ in range(n)]
visited = [0] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    ab.append((a,b))

    
for item in ab:
    a = item[0]
    b = item[1]
    neighbor[a].append(b)
    neighbor[b].append(a)
    
        
#print(par)
#print(neighbor)
#print(rank)

for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x
    
def calc(idx,neighbor,val,bias):
    val[idx] += bias
    for i in neighbor[idx]:
        if visited[i] == 0:
            visited[i] = 1
            calc(i,neighbor,val,val[idx])

visited[0] = 1
calc(0,neighbor,val,0)    
ans = ""    
for num in val:
    ans += str(num) + " "
print(ans)

Submission status: Time Limit Exceeded

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

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

result = [0]*N

def konitas(i, j):
    result[i-1] += j
    for ii, mi in enumerate(matrix[i-1]):
        if mi==1:
            konitas(ii+1, j)

sousa = [[int(x) for x in input().split()] for _ in range(Q)]
sousa2 = [0]*N
for x in sousa:
    sousa2[x[0]-1] += x[1]
for i, y in enumerate(sousa2):
    konitas(i+1,y)

print(*result)

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

counter = [0] * n

px =[]
for j in range(q):
  px.append(list(map(int, input().split())))
  
def search(item_list, key):
  index_list = [key]
  for item in item_list:
    if item[0] == key:
      index_list.append(item[1])
      index_list += search(item_list, item[1])
  return index_list
  
def print_str(num_list):
  new_list = []
  for item in num_list:
    new_list.append(item)
  ans = ""
  for i in range(len(new_list)):
    ans = ans + str(new_list.pop(0)) + " "
  print(ans)
  
for k in px:
  index_list = search(ab,k[0])
  for i in range(1,n+1):
    if i in index_list:
      counter[i-1] += k[1]

print_str(counter)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
a = []
b = []
p = []
x = []
for i in range(n-1):
    a1,b1=[int(i) for i in input().split()]
    a.append(a1)
    b.append(b1)
for i in range(q):
    p1,x1=[int(i) for i in input().split()]
    p.append(p1)
    x.append(x1)
cnt = [0]*n
root = [0]*n
for i in range(q):
    cnt[p[i]-1] += x[i]
    for j in range(n-1):
        if a[j] == p[i]:
            cnt[b[j]-1] += x[i]
            root[j] = b[j]
        if a[j] in root:
            cnt[b[j]-1] += x[i]
            root[j] = b[j]
    root = [0]*n
print(' '.join(map(str,cnt)))