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:
from collections import deque
from collections import defaultdict

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

class Graph(object):

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

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

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

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

G = Graph()

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

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

#幅優先
q = deque([]) 
val = 0
ans = [0 for i in range(N + 1)]
visit = [-1 for i in range(N + 1)]
visit[1] = 1
q.append(1)
while q:
	m = q.pop()
	ans[m] += plus[m]
	visit[m] = 1
	for i in G.graph[m]:
		if visit[i] == -1:
			q.append(i)
			ans[i] += ans[m]

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

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

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(int, input().split(" ")))
a = []
b = []
tree = []

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

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

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

# make node
for i in range(n):
    tree.append(Node(i))
# add node
for i in range(n-1):
    j, k = list(map(int, input().split(" ")))
    tree[j-1].add_node(tree[k-1])

# add count
for i in range(q):
    j, k = list(map(int, input().split(" ")))
    tree[j-1].add_count(k)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# ★頂点1からdfsを始めればよいので、 自分の親はどれで子はどれなのか分からなくてもできる！

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

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

def dfs(vertex):
	global counters
	global visited

	visited[vertex] = True


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


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

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

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

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

px = [list(map(int, input().split() )) for _ in range(n_query)]
for z in px:
	counters[z[0]-1] += z[1]

dfs(0)

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

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

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [0 for i in range(n)]  # 親
        self.children = [set([i]) for i in range(n)]  # 子の一覧

    # xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return
        else:
            self.children[self.par[x]
                          ] = self.children[self.par[x]] | self.children[x]
            self.find(self.par[x])
            return


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

tree = UnionFind(N+1)

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

# print(tree.par)

for i in range(N+1):
    tree.find(i)

# print(tree.children)

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

ans = ""
for i in anslist[1:]:
    ans += str(i)+" "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split()) # 複数の数字を変数に格納
List_ab = [list(map(int,input().split())) for i in range(N-1)] # [[1,2],[3,4],[5,6]]
List_px = [list(map(int,input().split())) for i in range(Q)] # [[1,2],[3,4],[5,6]]

count_list = [0]*N

List_ab.sort()
List_px.sort()

for i in range(Q):
    p = List_px[i][0]
    x = List_px[i][1]
    count_list[p-1] += x
        
for i in range(N-1):
    a = List_ab[i][0]
    b = List_ab[i][1]
    count_list[b-1] += count_list[a-1]
    
print(*count_list)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
N, Q = map(int, input().split())
e = dd(list)
for i in range(1, N):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  
res = deque([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)
res.popleft()
print(" ".join(map(str, res)))

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):
    child.append([])

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

    ans[node] += num

for a, b in ab:
    child[a].append(b)

#print(child)

for p, x in px:
    add(p, x)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

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

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

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

    q = queue.Queue()
    q.put(0)
    while not q.empty():
        target = q.get()
        for child in nodes[target]:
            counter[child] += counter[target]
            q.put(child)

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


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] +=xi
sp = [0 for i in range(n)]
def f(v,vp,p):
    sp[v] = p + px[v]
    for di in d[v]:
        if not di == vp:
            f(di,v,sp[v])
f(0,0,0)
for i in range(n):
    print(sp[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,q=map(int,input().split())
d={i:[] for i in range(n)}
for i in range(n-1):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
bubunki={i:[] for i in range(n)}
for i in range(n):
    idx = n-1-i
    bubunki[idx].append(idx)
    if idx in d.keys():
        for children in d[idx]:
            bubunki[idx] += bubunki[children]
counter = np.zeros(n)
for i in range(q):
    p,x=map(int,input().split())
    s=bubunki[p-1]
    counter[s]+=x
print(' '.join(map(str, map(int,(counter)))))

Submission status: Time Limit Exceeded

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

from collections import deque

c = [0]*n
visit = [[] for _ in range(n)]
visit_log = [0]*n

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

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

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
child_rel={}
parent_rel={}
for l in node_lst:
    src, dst = l[0], l[1]
    if src not in child_rel.keys():
        child_rel[src]=[dst]
    else:
        child_rel[src].append(dst)
    if src in parent_rel.keys():
        for e in parent_rel[src]:
            child_rel[e].append(dst)
    if dst not in parent_rel.keys():
        parent_rel[dst]=[src]
    else:
        parent_rel[dst].append(src)
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
    if p in child_rel.keys():
        for e in child_rel[p]:
            cnt_lst[e-1]+=x
print(" ".join([str(c) for c in cnt_lst]))

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(_) for _ in input().split())
l = [list(map(int, input().split())) for i in range(n-1)]
p = [list(map(int, input().split())) for i in range(q)]
l = sorted(l,key = lambda x:(x[0] ,x[1]))

res = [0] * n
for i in p:
    res[i[0]-1] += i[1]
for i in l:
    res[i[1]-1] += res[i[0]-1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys,resource
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (256*1024*1024,hard))

def dfs(i,fromup):
    y[i] = fromup + v[i]
    for d in dst[i]:
        dfs(d,y[i])

setrlim()
n,q = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
v = [0]*n
for i in range(q):
    p,x = inm()
    p -= 1
    v[p] += x
y = [0]*n
dfs(0,0)
for i in range(n):
    printn((' ' if i>0 else '') + str(y[i]))
print("")

Submission status: Time Limit Exceeded

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

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

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

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

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n, q = map(int, input().split())
d = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in d:
        d[a].append(b)
    else:
        d[a] = [b]
    if b in d:
        d[b].append(a)
    else:
        d[b] = [a]
d2 = {}
for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    if p in d2:
        d2[p].append(x)
    else:
        d2[p] = [x]

ans = [0] * n

def dfs(cur, pre, point):
    if cur in d2:
        point += sum(d2[cur])
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join([str(item) for item in ans]))

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)

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

# print("#", parent)

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

# print("#", cnttab)
    
ans = [0] * N
for i in range(N):
    pos = i + 1
    while pos != None:
        # print("##", pos)
        ans[i] += cnttab[pos - 1]
        pos = parent[pos - 1]

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
AB = [None] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    AB[i] = (a, b)
PX = [None] * (Q)
for i in range(Q):
    p, x = map(int, input().split())
    PX[i] = (p, x)
    
edges = AB[:]
vals = PX[:]

from collections import defaultdict
graph = defaultdict(lambda: {})
for a, b in edges:
    graph[a][b] = 0
    graph[b][a] = 0
#print(graph)
    
vals_dict = defaultdict(lambda: 0)
for v, n in vals:
    vals_dict[v] += n
#print(vals_dict)

from collections import deque
q = deque([1])
visited = [None] * (N+1)
while q:
    v = q.popleft()
    visited[v] = True
    for t in graph[v]:
        if visited[t] == None:
            graph[v][t] = vals_dict[t]
            q.append(t)
#print(graph)
from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, 1, N)
shortest = [s+vals_dict[1] for s in shortest]
#print(shortest)
ans = ' '.join(map(str, shortest[1:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,q=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n-1)]
lq=[list(map(int,input().split())) for _ in range(q)]
lst=[set() for i in range(n)]
for i in l:
    lst[i[0]-1].add(i[1]-1)
ans=[0 for i in range(n)]
for i in lq:
    queue = deque([i[0]-1])
    while queue:
        x = queue.popleft()
        ans[x]+=i[1]
        for j in lst[x]:
            queue.append(j)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:

N,Q = map(int,input().split())
edges = []*N
for n in range(N-1):
	a,b = map(int,input().split())
	edges.append((a-1,b-1))
edges.sort()
#print(edges)

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

cur = 0
for a,b in edges:
	#print('    ({},{})'.format(a,b))
	if cur<a:
		while cur<a:
			print('{} '.format(counters[cur]),end='')
			cur += 1
		#print('    up!')
	counters[b] += counters[a]
# remaining nodes
while cur<N:
	print('{} '.format(counters[cur]),end='')
	cur += 1

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int, input().split())
ab=[]
for v in range(n):
    ab.append([v+1])
for _ in range(n-1):
    a,b=map(int, input().split())
    for v in ab:
        if a in v:
            v.append(b)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] +=xi
sp = [0 for i in range(n)]
sp[0] = px[0]
def f(v,vp,p):
    sp[v] = p + px[v]
    for di in d[v]:
        if not di == vp:
            f(di,v,sp[v])
f(0,0,0)
for i in range(n):
    print(sp[i])

Submission status: Time Limit Exceeded

Solution code:
p=input().rstrip().split(' ')
l=[]
q=[]
for i in range(0,int(p[0])-1):
    u=input().rstrip().split(' ')
    D=[]
    D.append(int(u[0]))
    E=[]
    E.append(int(u[1]))
    if D not in l:
        l.append(D)
        q.append(E)
    else:
        V=l.index(D)
        q[V].append(int(u[1]))
w=[0]*int(p[0])
S=[]
D=[]
for i in range(0,int(p[1])):
    u=input().rstrip().split(' ')
    if int(u[0]) not in S:
        S.append(int(u[0]))
        D.append(int(u[1]))
    else:
        G=S.index(int(u[0]))
        D[G]+=int(u[1])
V=[]
W=[]
for i in range(1,int(p[0])+1):
    DD=[]
    DD.append(i)
    XX=[]
    if DD in l:
        V.append(i)
        C=l.index(DD)
        A=q[C];
        G=0;
        while(len(A)!=0):
            X=A[0]
            XX.append(X)
            O=[]
            O.append(X)
            if O in l:
                Z=l.index(O)
                B=q[Z];
                for j in range(0,len(B)):
                    A.append(B[j])
            del(A[0])
    XX=list(set(XX))
    W.append(XX)
#print(V,W)
#print(S,D)
for i in range(0,len(S)):
    if S[i] in V:
        H=V.index(S[i])
        J=W[H];
        w[S[i]-1]+=D[i]
        for j in range(0,len(J)):
            w[J[j]-1]+=D[i];
    else:
        w[S[i]-1]+=D[i]
print(*w)

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
for i in range(N):
    s=i+1
    t=l[0][2]
    while s!=1:
        t+=l[s-1][2]
        s=l[s-1][1]
    print(t,end=" ")

Submission status: Time Limit Exceeded

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

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

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


def rec(index, counter):
    node = nodes[index]
    counts[index] += counter
    for path in node:
        rec(path, counts[index])

rec(0, 0)

for count in counts:
    print(count, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q = map(int,input().split())
Tree = {i+1:[] for i in range(N)}
count = {i+1:0 for i in range(N)}
for i in range(N-1):
    a,b = map(int,input().split())
    Tree[a] += [b] 
operation = [list(map(int,input().split())) for _ in range(Q)]
q = deque()
for op in operation:
    p = op[0]
    x = op[1]
    count[p] += x
    for t in Tree[p]:
        q.append(t)
    
    #print(p,x,q)
#"""
    while len(q) > 0:
        vertex = q.popleft()
        count[vertex] += x
        for t in Tree[vertex]:
            q.append(t)
        #print(q)
#"""
print(*count.values())

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
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(a):
    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
    
for point in points:
  print(point, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

def add_q(x):
    ans[x-1] += j
    l = tree[x]
    if l:
        for node in l:
            add_q(node)
        
n,q = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(n-1)]
queri = [tuple(map(int,input().split())) for _ in range(q)]
tree = {}
ans = [0]*n
for i in range(n):
    tree[i+1] = []
for i in edge:
    tree[i[0]].append(i[1])
for i,j in queri:
    add_q(i)
print(" ".join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(20000)

n, q = [int(x) for x in input().split()]

tree = [[] for _ in range(n + 1)]
cnt = [0] * (n + 1)

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

def walk(p, x):
    cnt[p] += x
    for n in tree[p]:
        walk(n, x)

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

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split()) # 複数の数字を変数に格納
List_ab = [list(map(int,input().split())) for i in range(N-1)] # [[1,2],[3,4],[5,6]]
List_px = [list(map(int,input().split())) for i in range(Q)] # [[1,2],[3,4],[5,6]]

count_list = [0]*N

List_ab.sort()
List_px.sort()

for i in range(Q):
    p = List_px[i][0]
    x = List_px[i][1]
    for j in range(N):
        if p == j+1:
            count_list[j] += x
        
for i in range(N-1):
    a = List_ab[i][0]
    b = List_ab[i][1]
    count_list[b-1] += count_list[a-1]
    
print(*count_list)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


N, Q = list(map(int, input().split()))
tree = [dict() for i in range(N)]
for i in range(N):
	tree[i]["edge"] = []
	tree[i]["ope"] = 0
	tree[i]["score"] = 0
	tree[i]["parent"] = -1

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def roooot(arr, i):
    tmp = i
    while len(arr[i]) != 1:
        i = arr[i][-1]-1
        arr[tmp].append(i+1)

n, q = map(int, input().split())
cnt = [0]*n
root = [[i+1] for i in range(n)]

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

for i in range(q):
    p, x = map(int, input().split())
    for j in range(len(root)):
        if p in root[j]: cnt[j] += x
print(*cnt)

Submission status: Time Limit Exceeded

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


N, Q = map(int, input().split())
AB = [[] 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= map(int,input().split())

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

ans = {i:0 for i in range(1,n+1)}
dp = {i:[i] for i in range(1,n+1)}
dp[n] = [n]
for i in range(n,0,-1):
  for j in edges[i]:
    dp[i] += dp[j]

queries = [0]*(n+1)
for _ in range(q):
  p,x = map(int,input().split())
  queries[p] += x
for i in range(1,n+1):
  for j in dp[i]:
    ans[j] += queries[i]
    
st = ""
for key in ans:
  if key != 1:
    st+=" "
  st+= str(ans[key])
print(st)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq,math,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (256*1024*1024,hard))

def dfs(i,fromup):
    y[i] = fromup + v[i]
    for d in dst[i]:
        dfs(d,y[i])

setrlim()
n,q = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
v = [0]*n
for i in range(q):
    p,x = inm()
    p -= 1
    v[p] += x
y = [0]*n
dfs(0,0)
for i in range(n):
    printn((' ' if i>0 else '') + str(y[i]))
print("")

Submission status: Time Limit Exceeded

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

#print(n,q)
edge=[]
for i in range(n-1):
    a = list(map(int,input().split()))
    edge.append(a)

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

#print(edge,add_list)

ans = [0] * n
edge_list = [[] for i in range(n)]

for e in edge:
    edge_list[e[1]-1].append(e[0]-1)

add_value = [0]*n
for v in add_list:
    add_value[v[0]-1] += v[1]

#print(edge_list)
#print(add_value)


dp = [-1] * n
def get_value(i):
    if(dp[i]!=-1):
        return dp[i]
    tmp = add_value[i]
    for e in edge_list[i]:
        tmp += get_value(e)
    dp[i] = tmp
    return dp[i]

for i in range(n):
    ans[i] = get_value(i)
    #print(i,ans)

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ab_lst = [list(map(int, input().split())) for _ in range(n-1)]
px_lst = [list(map(int, input().split())) for _ in range(q)]


neighbor = [[] for _ in range(n+1)]
for edge in ab_lst:
    neighbor[edge[0]].append(edge[1])

root_value = [0] * (n+1)
for px in px_lst:
    root_value[px[0]] += px[1]

res = [0] * (n+1)
queue = [(1, root_value[1])]
while len(queue) > 0:
    pair = queue.pop()
    res[pair[0]] += pair[1]
    if neighbor[pair[0]] != []:
        for i in neighbor[pair[0]]:
            queue.append((i, pair[1] + root_value[i]))
    
for i in res[1:]:
    print(i, end=" ")

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

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


def dfs(v, p, cnt):
    cnt += val[v]
    ans[v] = cnt
    for next_v in nl[v]:
        if next_v != p:
            dfs(next_v, v, cnt)


dfs(1, -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:
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)]
    v = 0
    if 1 in ops: v = ops[1]
    cur = [[1, v]]

    visited = set([1])
    while cur:
        temp = []
        for a, v in cur:
            vals[a-1] += v
            if a in graph:
                for b in graph[a]:
                    if b not in visited:
                        if b in ops:
                            temp.append([b, v+ops[b]])
                        else:
                            temp.append([b, v])
                        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)]

x_sorted = [0] * n
for i in range(q):
    p = px[i][0]
    x = px[i][1]
    x_sorted[p - 1] += x

# print(x_sorted)

start = 0
# コストテーブルの作成
from heapq import heappop, heappush
inf = float('inf')
cost = dict() # コストテーブル
for i, j in ab:
    c = x_sorted[i - 1]
    cost[i - 1] = cost.get(i - 1, []) + [(j - 1, c)]
# print(cost)

d = [inf for i in range(n)] # 最短距離
d[start] = 0

qq = [] # min-heap, (距離, 頂点)
heappush(qq, (d[start], start))
while qq:
    du, u = heappop(qq) # 最短距離とその頂点
    if d[u] < du:
        continue
    for v, weight in cost.get(u, []):
        alt = du + weight
        if d[v] > alt:
            d[v] = alt
            heappush(qq, (alt, v))

ans = ''
for i in range(n):
    ans += str(d[i] + x_sorted[i]) + ' '

print(ans[:-1])