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: Runtime Error

Solution code:
#
# Yet I'm feeling like
# 	There is no better place than right by your side
# 		I had a little taste
# 			And I'll only spoil the party anyway
# 				'Cause all the girls are looking fine
# 					But you're the only one on my mind


import sys
import re
# inf = float("inf")
#sys.setrecursionlimit(1000000)

# abc='abcdefghijklmnopqrstuvwxyz'
# abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
# mod,MOD=1000000007,998244353
# vow=['a','e','i','o','u']
# dx,dy=[-1,1,0,0],[0,0,1,-1]

# from cmath import sqrt
from collections import deque, Counter, OrderedDict,defaultdict
from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
# from math import ceil,floor,log,sqrt,factorial,pow,pi,gcd,log10,atan,tan
# from bisect import bisect_left,bisect_right
# import numpy as np

def dfs(curr,parent):
    visited[curr]=True
    value[curr]+=value[parent]
    for i in mydict[curr]:
        if not visited[i]:
            dfs(i,curr)


def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

n,q=get_ints()
mydict=defaultdict(list)
parent=[0]*(n+1)
for i in range(n-1):
    a,b=get_ints()
    mydict[a].append(b)
    parent[b]=a

value=[0]*(n+1)
while q>0:
    index,score=get_ints()
    value[index]+=score
    q-=1

visited=[False]*(n+1)
dfs(1,0)

print(*value[1:])

Submission status: Runtime Error

Solution code:
def main():
    N, Q = [int(s) for s in input().split()]
    adj = [[] for _ in range(N)]
    counters = [0] * N
    increments = [0] * N

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

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

    dfs(0, -1, 0, increments, adj, counters)
    print(' '.join(str(c) for c in counters))


def dfs(vertex, parent, increment, increments, adj, counter):
    increment += increments[vertex]
    counter[vertex] += increment

    for other in adj[vertex]:
        if other != parent:
            dfs(other, vertex, increment, increments, adj, counter)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

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

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

n,q = get_nums_l()

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

scores = [0] * (n+1)

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

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

for e in edges:
    queue.append(e)

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

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

Submission status: Runtime Error

Solution code:

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

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


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

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

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

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

    inc(tree, point, p, x)

point.pop(0)
print(*point)

Submission status: Runtime Error

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

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

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

# print(tree)

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

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

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

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

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

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

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

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

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
N, Q = map(int, input().split(" "))
cnt = [0] * N
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

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


def dfs(n, prev):
    for e in edge[n]:
        if e == prev:
            continue
        cnt[e] += cnt[n]
        dfs(e, n)


dfs(0, -1)
print(*cnt)

Submission status: Runtime Error

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

tree = {i:[] for i in range(1,N+1)}
sub = {i:[i] for i in range(1,N+1)}
fin = [False]*(N+1)
vals = [0]*(N+1)

for i in [0]*(N-1):
	a,b = map(int,input().split(' '))
	tree[a].append(b)

def get_sub(p):
	if not fin[p]:
		for t in tree[p]:
			sub[p].extend(get_sub(t))
		fin[p] = True
	return sub[p]

for i in [0]*Q:
	p,x = map(int,input().split(' '))
	subtree = get_sub(p)
	for t in subtree:
		vals[t] += x
#print(tree)
#print(sub)

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

Submission status: Runtime Error

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

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

ps=[0 for i in range(n+1)]
for i in range(q):
    p, x = map(int, input().split())
    ps[p] += x

parent = [0 for i in range(n + 1)]
def rec(now):
    # print('debug', 'called rec(', now, ')')
    # print(tonaris[now],parent[now])
    for tonari in tonaris[now]:
        if tonari != parent[now]:
            ps[tonari] += ps[now]
            parent[tonari] = now
            rec(tonari)

rec(1)

for i in range(1,n+1):
    if i > 1: print(' ', end='')
    print(ps[i],end='')

Submission status: Runtime Error

Solution code:
from sys import stdin

ntree = []
ans = []


def addnum(p, x):
    ans[p-1] += x
    for i in range(len(ntree[p-1])):
        addnum(ntree[p-1][i], x)

n, q = [int(x) for x in stdin.readline().rstrip().split()]

for i in range(n):
    ntree.append([])
    ans.append(0)

for i in range(n-1):
  a, b = [int(x) for x in stdin.readline().rstrip().split()]
  ntree[a-1].append(b)


for i in range(q):
  p, x = [int(x) for x in stdin.readline().rstrip().split()]
  addnum(p,x)

print(' '.join([str(n) for n in ans]))

Submission status: Runtime Error

Solution code:
# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]
# from math import factorial
# def nCr(n, r): return factorial(n) // factorial(r) // factorial(n - r)
from collections import defaultdict 

N, Q = [int(i) for i in input().split(" ")]
edges = defaultdict(list)
for _ in range(N - 1):
    a, b = [int(i) for i in input().split(" ")]
    edges[a-1].append(b-1)
PX = defaultdict(int)
for _ in range(Q):
    p, s = [int(i) for i in input().split(" ")]
    PX[p-1] += s
ans = [0 for _ in range(N)]
def dfs(i, v):
    ans[i] += v
    for j in edges[i]:
        dfs(j, v)
for i in range(N):
    dfs(i, PX[i])
for a in ans:
    print(a, end=" ")

Submission status: Runtime Error

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 range(N)]
node_rel={}
for l in node_lst:
    src, dst = l[0], l[1]
    if src not in node_rel.keys():
        node_rel[src]=[dst]
    else:
        node_rel[src].append(dst)
    for k, v in node_rel.items():
        if src in v:
            node_rel[k].append(dst)
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
    if p in node_rel.keys():
        for e in node_rel[p]:
            cnt_lst[e-1]+=x
print(" ".join([str(c) for c in cnt_lst]))

Submission status: Runtime Error

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

class Node:
    def __init__(self, index):
        self.index = index
        self.paths = []
        self.count = 0

    def append(self, next_node):
        self.paths.append(next_node)

nodes = [Node(i) for i in range(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())
    nodes[p-1].count += x


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

rec(0, 0)

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

Submission status: Runtime Error

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

def sol():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]

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

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

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

    def calc(now, parent):
        if parent != -1:
            ans[now] += ans[parent]
        for to in edge[now]:
            if to != parent:
                calc(to, now)
        return

    calc(0, -1)
    print(*ans)


sol()

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
A = [''] * (N+1)
C = [0] * (N+1)
for i in range(N-1):
  a, b = map(int, input().split())
  if len(A[a]) == 0:
    A[a] = [b]
  else:
    A[a].append(b)

def AddPX(n, x):
  C[n] += x
  for i in A[n]:
    AddPX(i, x)
  
for i in range(Q):
  p, x = map(int, input().split())
  AddPX(p, x)
print (" ".join(map(str, C[1:])))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
memo = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    memo[p-1] += x

result = [None]*N
def dfs(v,a):
    c = memo[v]
    for u in adj[v]:
        dfs(u,a+c)
    result[v] = a+c
dfs(0,0)
print(*result)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
ki=[[] for i in range(n+1)]
ki[0]="null"

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

scores=[0 for i in range(n+1)]
scores[0]="null"
for i in range(q):
    p,x=map(int,input().split())
    scores[p]+=x


ans=[0 for i in range(n+1)]
ans[0]="null"
point=0


def tansa(n,point):
    point+=scores[n]
    for p in ki[n]:
        tansa(p,point)
    else:
        ans[n]=point
        
tansa(1,0)

ans=ans[1:]
ans=[str(i) for i in ans]
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
def sol():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]

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

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

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

    def calc(now, parent):
        ans[now] += ans[parent]
        for to in edge[now]:
            if to != parent:
                calc(to, now)
        return

    calc(0, -1)
    print(*ans)


sol()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
    
visited = [False] * N
visited[0] = True
parent = [[] for _ in range(N)]

def bfs(cur, par) :
    parent[cur] = [cur] + par
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            bfs(nex, parent[cur])

bfs(0, [])

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

ret = []
for i in range(N) :
    s = 0
    for j in parent[i] :
        s += pq[j]

    ret.append(s)
    
print(*ret)

Submission status: Runtime Error

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)]
ad_list = [[] for _ in range(n)]
for a, b in ab:
  ad_list[a-1].append(b)
count = [0 for _ in range(n)]

def dfs(v, x):
  count[v] += x
  if len(ad_list[v]) == 0:
    return 0
  else:
    for ad_v in ad_list[v]:
      dfs(ad_v-1, x)
    return 0

for p, x in px:
  dfs(p-1, x)
print(*count)

Submission status: Runtime Error

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

def add(idx, val):
    global nodes
    nodes[idx][1] += val
    for n in nodes[idx][0]:
        add(n, val)

for _ in range(n-1):
    a, b = map(int, input().split())
    nodes[a-1][0].append(b-1)
for _ in range(q):
    p, q = map(int, input().split())
    add(p-1, q)
op = str(nodes[0][1])
for n in range(1, len(nodes)):
    op += " {}".format(nodes[n][1])
print(op)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


children = defaultdict(set)


def collect_children(cs, cc):
  for cx in cs:
    if children[cx]:
      collect_children(children[cx], cc)
    cc.add(cx)


N, Q = list(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)]

for a, b in AB:
  children[a].add(b)

for cs in list(children.values()):
  cc = set()
  collect_children(cs, cc)
  cs.update(cc)

sums = [0] * N
for p, x in PX:
  for c in children[p]:
    sums[c - 1] += x
  sums[p - 1] += x
print(" ".join(str(s) for s in sums))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split(" "))
cnt = [0] * N
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

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


def dfs(n, prev):
    global cnt
    for e in edge[n]:
        if e == prev:
            continue
        cnt[e] += cnt[n]
        dfs(e, n)


dfs(0, -1)
print(*cnt)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
ki=[[] for i in range(n+1)]
ki[0]="null"

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

scores=[0 for i in range(n+1)]
scores[0]="null"
for i in range(q):
    p,x=map(int,input().split())
    scores[p]+=x


ans=[0 for i in range(n+1)]
ans[0]="null"
point=0


def tansa(n,point):
    point+=scores[n]
    for p in ki[n]:
        tansa(p,point)
    else:
        ans[n]=point
        
tansa(1,0)

ans=ans[1:]
ans=[str(i) for i in ans]
print(" ".join(ans[1:]))

Submission status: Runtime Error

Solution code:
# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]
# from math import factorial
# def nCr(n, r): return factorial(n) // factorial(r) // factorial(n - r)
from collections import defaultdict 

N, Q = [int(i) for i in input().split(" ")]
edges = defaultdict(list)
for _ in range(N - 1):
    a, b = [int(i) for i in input().split(" ")]
    edges[a-1].append(b-1)
PX = defaultdict(int)
for _ in range(Q):
    p, s = [int(i) for i in input().split(" ")]
    PX[p-1] += s
ans = [0 for _ in range(N)]
def dfs(i, v):
    ans[i] += v
    for j in edges[i]:
        dfs(j, v)
for i in range(N):
    dfs(i, PX[i])
print(ans)

Submission status: Runtime Error

Solution code:
n,q=[int(i) for i in input().split()]
a1={}
a2={}
for _ in range(n-1):
  x,y=[int(i)-1 for i in input().split()]
  if x in a1:
    a1[x].append(y)
  else:
    a1[x]=[y]
  if x in a2:
    a2[x].append(y)
  else:
    a2[x]=[y]
root=[0]*n
def c(ind=0,ro=0):
  global root
  if root[ind]!=0:
    return 0
  root[ind]=ro
  if ind in a1:
    for i in a1[ind]:
      c(i,ind)
  if ind in a2:
    for i in a2[ind]:
      c(i,ind)
c()
p=[0]*n
for _ in range(q):
  x,y=[int(i) for i in input().split()]
  p[x-1]+=y
r=[]
for i in range(n):
  j=i
  k=0
  while True:
    k+=p[j]
    if j==0 and root[j]==0:
      break
    j=root[j]
  r.append(str(k))
print(" ".join(r))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)


class Graph:

  def __init__(self, N):
    self.V = {}
    self.E = {}

    for i in range(N):
      self.V[i + 1] = 0
      self.E[i + 1] = {}

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


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

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

  walk(1, 0)

  return result


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

G = Graph(N)

for _ in range(N - 1):
  a, b = map(int, input().strip().split())
  G.add_edge(a, b, 0)

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

result = calc(N, G)

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

Submission status: Runtime Error

Solution code:
def kowa(ko, p):
    if ko[p]==[]:
        return [p]
    else:
        kodomo=[]
        for i in ko[p]:
            kodomo+=kowa(ko, i)
        return kodomo+[p]
    

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

counter=[0]*n
ko=[]
for i in range(n):
    ko.append([])

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

for i in range(q):
    p, x = map(int, input().split())
    child=kowa(ko, p-1)
    #print(child)
    for ch in child:
        counter[ch]+=x

for co in counter:
    print(co, end=" ")

Submission status: Runtime Error

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

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

ans = [0] * n
def dfs(cur, c, parent):
    c += cost[cur]
    ans[cur] = c
    for next in edge[cur]:
        if next != parent:
            dfs(next, c, cur)

dfs(0, 0, -1)
print(*ans)

Submission status: Runtime Error

Solution code:
# お約束
INF = float("inf")
MOD = int(1e9 + 7)

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

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

edges = [[] for _ in range(N)]
for a, b in AB:
	a, b = a - 1, b - 1
	edges[a] += [b]
	edges[b] += [a]

visited = [False] * N
vals = [0] * N

def dfs(v, p, add_val):
	global visited, vals
	visited[v] = True
	vals[v] = add_val + sum_val[v]
	for n in edges[v]:
		if visited[n]: continue
		dfs(n, v, add_val + sum_val[v])

dfs(0, -1, 0)
for v in vals:
	print(v)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
def dfs(p,q):
  for r in route[q]:
    if p != r:
      cnt[r] += cnt[q]
      dfs(q,r)

dfs(-1,0)
print(" ".join([str(c) for c in cnt]))

Submission status: Runtime Error

Solution code:
import sys
# sys.setrecursionlimit(200005)

# はぁー・・

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ps = [0] * n
for i in range(q):
    p, x = na()
    p -= 1
    ps[p] += x

ans = [0] * n

def dfs(cur, pre, g, curv):
    global ps, ans
    curv += ps[cur]
    ans[cur] = curv
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, curv)

dfs(0, -1, g, 0)

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

Submission status: Runtime Error

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


def dfs(s, prev):
    global g, cost
    for t in g[s]:
        if t == prev:
            continue
        cost[t] += cost[s]
        dfs(t, s)


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


dfs(0, -1)
print(*cost, sep=' ')

Submission status: Runtime Error

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

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

ans = [0] * n
def dfs(cur, c, parent):
    c += cost[cur]
    ans[cur] = c
    for next in edge[cur]:
        if next != parent:
            dfs(next, c, cur)

dfs(0, 0, -1)
print(*ans)

Submission status: Runtime Error

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

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

def counter_add(root, v):
    res[root] += v
    if neighbor[root] != []:
        for i in neighbor[root]:
            counter_add(i, v)

for px in px_lst:
    counter_add(px[0], px[1])
    
for i in res[1:]:
    print(i, end=" ")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab=sorted(ab, key=lambda x:x[0])
pq=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for p,q in pq:
	res[p-1]+=q
for a,b in ab:
	res[b-1]+=res[a-1]
print(" ".join(res))

Submission status: Runtime Error

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

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

def counter_add(root, v):
    res[root] += v
    if neighbor[root] != []:
        for i in neighbor[root]:
            counter_add(i, v)

for px in px_lst:
    counter_add(px[0], px[1])
print(res)

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
T = [[] for i in range(N+1)]
V = [0]*(N+1)
for _ in range(N-1):
    a,b = map(int,input().split())
    T[a].append(b)
    T[b].append(a)
for _ in range(Q):
    p,x = map(int,input().split())
    V[p]+=x
def f(v,p):
    global T,V
    for c in T[v]:
        if c==p:continue
        V[c]+=V[v]
        f(c,v)
f(1,0)
print(*V[1:])

Submission status: Runtime Error

Solution code:
'''
date +%Y.%m.%d

题解先咕着。
'''
def intinput():
    return [int(i) for i in input().split()]

n, q = intinput()
G = [[] for i in range(n + 1)]
a = [0 for i in range(n + 1)]

def dfs(u, fa):
    for v in G[u]:
        if v != fa:
            a[v] += a[u]
            dfs(v, u)

for i in range(n - 1):
    u, v = intinput()
    G[u].append(v)
    G[v].append(u)

for i in range(q):
    u, x = intinput()
    a[u] += x

dfs(1, 0)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def dfs(i, d):
  visited[i] = True
  ans[i] = d + pp[i]
  for j in edges[i]:
    if not visited[j]:
      dfs(j, d + pp[i])

n, q = map(int, input().split())
ans = [0 for _ in range(n)]
visited = [False for _ in range(n)]
edges = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)
pp = [0 for _ in range(n)]
for _ in range(q):
  p, x = map(int, input().split())
  pp[p-1] += x
dfs(0, 0)
print(*ans)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
tree = []
for _ in range(n + 1):
    tree.append(set())
for _ in range(n - 1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)
sons = []
used = [0] * (n + 1)
used[1] = 1
for _ in range(n + 1):
    sons.append(set())


def get_son(i):
    if len(tree[i]) == 1 and i != 1:
        pass
    for u in tree[i]:
        if used[u] == 0:
            used[u] = 1
            sons[i].add(u)
            get_son(u)
            for dd in sons[u]:
                sons[i].add(dd)


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

Submission status: Runtime Error

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

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

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


visited = [False]*n


def dfs(v, p_cnt):
    if visited[v]:
        return
    visited[v] = True
    cnt[v] += p_cnt
    for nv in tree[v]:
        dfs(nv, cnt[v])


dfs(0, 0)
print(' '.join(map(str, cnt)))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

long long w[1<<20] = {0}, ans[1<<20];
vector<long long> g[1<<20];

long long cur = 0;
void dfs(int u, int p) {
  cur += w[u];
  ans[u] = cur;
  for (int v : g[u]) if (v != p) {
    dfs(v, u);
  }
  cur -= w[u];
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  priority_queue<double, vector<double>, greater<>> pq;
  int n, q; cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    int a, b; cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  while (q--) {
    int p, x; cin >> p >> x;
    --p;
    w[p] += x;
  }
  dfs(0, 0);
  for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
}

Submission status: Runtime Error

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

Ans = [0] * (N+1)
def dfs(v, p, a):
    global ans
    a += C[v]
    Ans[v] = a
    for u in E[v]:
        if u!=p:
            dfs(u, v, a)
dfs(1, 0, 0)
print(" ".join(map(str, Ans[1:])))

Submission status: Runtime Error

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

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
memo = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    memo[p-1] += x

result = [None]*N
def dfs(v,a):
    c = memo[v]
    for u in adj[v]:
        dfs(u,a+c)
    result[v] = a+c
dfs(0,0)
print(*result)

Submission status: Runtime Error

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

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

def dfs(v, p):
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        dfs(u, v)

dfs(0, -1)
print(' '.join([str(x) for x in imos]))