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:
class Node:
    def __init__(self, num):
        self.children = []
        self.num = num
        self.score = 0

    def add_child(self, node):
        self.children.append(node)

    def add_score(self, score):
        self.score += score


class Tree:
    def __init__(self):
        self.root = Node(1)
        self.nodes = { 1: self.root }

    def add_node(self, parent_num, num):
        parent = self.nodes[parent_num]
        child = Node(num)
        parent.add_child(child)
        self.nodes[num] = child

    def find_node(self, num):
        return self.nodes[num]

    @classmethod
    def add_score(cls, node, score):
        node.add_score(score)
        for n in node.children:
            cls.add_score(n, score)


N, Q = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(1, N):
    A[i], B[i] = map(int, input().split())

P = [0] * (Q+1)
X = [0] * (Q+1)
for i in range(1, Q+1):
    P[i], X[i] = map(int, input().split())

tree = Tree()
for i in range(1, N):
    tree.add_node(A[i], B[i])

for i in range(1, Q+1):
    node = tree.find_node(P[i])
    Tree.add_score(node, X[i])

for i in range(1, N+1):
    node = tree.find_node(i)
    print(node.score, end=' ')

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

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

def calc(p, x, li, ans):
    ans[p] += x
    if len(li[p]) == 0:
        return
    for b in li[p]:
        calc(b, x, li, ans)

n, q = na()
li = [[] for i in range(n)]
ans = [0 for i in range(n)]

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

for i in range(q):
    p, x = na()
    calc(p-1, x, li, ans)
print(*ans)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[list(map(int,input().split())) for i in range(b)]
e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[i]for i in range(a)]

def s(i,e,f):
  for j,k in enumerate(e[i]):
    if f==k:
      e[i].pop(j)
      break
  if e[i]==[]:
    return []
  global g
  g[i]=g[i]+e[i]
  for j in e[i]:
    g[i]=g[i]+s(j,e,i)
  return e[i]


s(0,e,0) 
h=[0 for i in range(a)]
for i in d:
  for j in g[i[0]-1]:
    h[j]+=i[1]
    
print(" ".join(map(str,h)))

Submission status: Runtime Error

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

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

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

for j in range(q):
    bb=list(map(int,input().split()))
    b.append(bb)

c={}
for k in a:
    key=k[0]
    if key not in c:
        c[key]=[]
    c[key].append(k[1])


d=[0]*n
def it(x,xx):
    if x in c:
        for y in c[x]:
           it(y,xx)
    d[x-1]+=xx

for alpha,beta in b:
    it(alpha,beta)
print(*d)

Submission status: Runtime Error

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import collections
N,Q=map(int,input().split())
A,B=[],[]
for i in range(N-1):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
P,X=[],[]
qy=collections.defaultdict(int)
for j in range(Q):
    p,x = map(int,input().split())
    P.append(p)
    X.append(x)
    qy[p]+=x



#print(list(zip(A,B)))
#print(list(zip(P,X)))



#from_tos
fts=collections.defaultdict(set)

#make links
for a, b in zip(A,B):
    fts[a].add(b)

#descendants
des=collections.defaultdict(set)

def get_des(p):
#    print("get_des:"+str(p))
    des[p].add(p)
    if len(fts[p]) == 0:
        pass
    else:
        sum=set()
        for pp in fts[p]:
            sum |= get_des(pp)
        des[p] |= sum
    
    return des[p]

get_des(1)

counters = [0] * N

#calc points
for p,x in qy.items():
    for pp in des[p]:
        counters[pp-1] += x
#    print(counters)

for c in counters:
    print(str(c)+' ',end='')
print()

Submission status: Runtime Error

Solution code:
def prod(p, x):
    if p in tree:
        #counter[p-1] += x
        for pi in tree[p]:
            #print(pi)
            counter[pi-1] += x
            prod(pi, x)
            
n, q = map(int, input().split())
tree = {}
counter = [0 for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = [b]
#print(tree)
for j in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x
    prod(p, x)

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

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
tree = [set() for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    tree[a-1].add(b)
ans=[0]*n
def add_l(x):
    if not tree[x-1]:
        return
    else:
        for i in list(tree[x-1]):
            if not tree[i-1]:
                continue
            add_l(i)
            tree[x-1] |= (tree[i-1])
add_l(1)
#print(tree)

for i in range(q):
    
    p,x=map(int,input().split())
    ans[p-1]+=x
    for j in list(tree[p-1]):
        ans[j-1]+=x
print(*ans)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
vec = [ [] for _ in range(N)]
for _ in range(N-1) :
    u, v = map(int, input().split())
    vec[u-1].append(v-1)
com = []
for _ in range(Q) :
    p, x = map(int, input().split())
    com.append([p-1,x])
#print(vec)
#print(com)
num = [0] * N
#print(num)
def update(p,x,num,vec):
  num[p] += x
  v = vec[p]
  for i in v:
    num = update(i,x,num,vec)
  return num
for i in range(len(com)):
  p,x = com[i]
  num = update(p,x,num,vec)
  #num[p] += x
for i in range(len(num)):
  print(num[i],"",end = "")

Submission status: Runtime Error

Solution code:

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

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

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

for i in range(0,N):
    if value[N-i-1] != 0:
        add(N-i,value[N-i-1],hen,value)
print(' '.join(map(str,value)))

Submission status: Runtime Error

Solution code:
# クエリはまとめてしまえ

n, q = map(int, input().split())
ki = [[] for i in range(n)]

def union(a, b):
  # aの子供
  ki[a].append(b)

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

table = {}
for _ in range(q):
  p, x = map(int, input().split())
  if p-1 not in table:
    table[p-1] = x
  else:
    table[p-1] += x
ans = [0 for _ in range(n)]


def f(k, v, b):
  if len(ki[k])>0:
    # 自分自身
    if b == False:
      ans[k] += v
    for x in ki[k]:
      ans[x] += v
    for x in ki[k]:
      # 再起するときのマーク
      f(x, v, True)
  else:
    if b == False:
      ans[k] += v
for k, v in table.items():
  f(k, v, False)

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

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
A = []
B = []

for i in range(N - 1):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

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


T = {}
for i in range(len(A)):
    a = A[i]
    b = B[i]
    if a in T:
        T[a].append(b)
    else:
        T[a] = [b]

def subnode(n, l):
    l.append(n)
    if n in T:
        for n2 in T[n]:
            l = subnode(n2, l)
    return l

T2 = {}
for i in range(1, N + 1):
    T2[i] = subnode(i, [])

d = [0] * N

for i in range(len(P)):
    p = P[i]
    x = X[i]
    l = T2[p]
    for i in l:
        d[i - 1] += x


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

Submission status: Runtime Error

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

def dfs(p, parents, count):
  parents.append(p)
  count += o.get(p, 0)
  for i in g[p]:
    if not i in parents:
      dfs(i, parents, count)
  counter[p] = counter.get(p, 0) + count
  parents.remove(p)
 

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

g = {}
o = {}
counter = {}
for i in range(n-1):
  a,b= map(int, input().split())
  if not g.get(a, False):
    g[a] = [b]
  else:
    if not b in g[a]:
      g[a].append(b)
  if not g.get(b, False):
    g[b] = [a]
  else:
    if not a in g[b]:
      g[b].append(a)

for i in range(q):
  p,x= map(int, input().split())
  if not o.get(p, False):
    o[p] = x
  else:
    o[p] = o[p] + x

dfs(1, [], 0)
for i in range(1, n+1):
  print(counter.get(i, 0), end=' ')

Submission status: Runtime Error

Solution code:
import bisect

n,q = (int(num) for num in input().split())
par = [i for i in range(n)]
nex = [[] for _ in range(n)]
ch = [0] * n
rank = [1] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    if a > b:
        a,b = b,a
    ab.append((a,b))
ab.sort(key = lambda x: x[0])
    
for item in ab:
    a = item[0]
    b = item[1]
    if rank[a] > rank[b]:
        par[b] = a
        nex[a].append(b)
    elif rank[a] < rank[b]:
        par[a] = b
        nex[b].append(a)
    elif a < b:
        par[b] = a
        nex[a].append(b)
        rank[a] += 1
    else:
        par[a] = b
        nex[b].append(a)
        rank[b] += 1
        
#print(par)
#print(nex)
#print(rank)

for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x
    
def calc(idx,nex,val,bias):
    val[idx] += bias
    if nex[idx] == []:
        return
    else:
        for i in nex[idx]:
            calc(i,nex,val,val[idx])
        
calc(0,nex,val,0)    
ans = ""    
for num in val:
    ans += str(num) + " "
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
from collections import Counter

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

a,b = [],[]

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

p,x = [],[]

for i in range(q):
    _p,_x = map(int,input().split())
    p.append(_p)
    x.append(_x)

class ki:
    def __init__ (self,n):
        self.name = n
        self.num = 0
        self.node = []
    
    def add(self,n,ne):
        if self.name == n:
            self.node.append(ki(ne))
            return 0
        else:
            for i in self.node:
                i.add(n,ne)
            return 0
            
    def add_num(self,n,num,f):
        if self.name == n or f:
            self.num += num
            f = True
        else:
            f = False
            
        for i in self.node:
            i.add_num(n,num,f)
    
    def out(self):
        d = {self.name:self.num}
        for i in self.node:
            d = dict(Counter(d) + Counter(i.out()))
        return(d)

Ki = ki(1)

for i,j in zip(a,b):
    Ki.add(i,j)
for i,j in zip(p,x):
    Ki.add_num(i,j,False)

d = Ki.out()
print(" ".join([str(d[i+1]) for i in range(n)]))

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, label):
        self.label = label
        self.count = 0
        self.child = []
        
    def addchild(self, child_node):
        self.child.append(child_node)
        
    def countup(self, count):
        self.count += count
        for child_node in self.child:
            child_node.countup(count)


n, q = map(int, input().split())
node_dict = [None] * n
node_dict[0] = Node(1)

for i in range(n - 1):
    a, b = map(int, input().split())
    if node_dict[b - 1] is None:
        node_dict[b - 1] = Node(b)
    node_dict[a -1].addchild(node_dict[b - 1])

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

print(' '.join(map(str, [node.count for node in node_dict])))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

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

seen = [False] * (N + 1)
oya = [[] for _ in range(N + 1)]


def dfs(e, v):
    seen[v] = True
    oya[v].append(v)
    for next_v in e[v]:
        oya[next_v].extend(oya[v])
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v)


dfs(e, 1)
ans = [0] * (N + 1)
for i in range(N + 1):
    for j in oya[i]:
        ans[i] += q[j]

print(*ans[1:])

Submission status: Runtime Error

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

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

# P = []
C = [0]*(n+1)

def add_point(C, p, x):
    C[p] += x
    for v in B[p]:
        C = add_point(C, v, x)
    return C


for _ in range(q):
    p, x = map(int, input().split())
    # P += [(p, x)]
    C = add_point(C, p, x)

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

Submission status: Runtime Error

Solution code:


import sys
sys.setrecursionlimit(100000)

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


def search(n):
    global P,res,visited
    
    visited[n]=True
    for l in L[n]:
        if not visited[l]:
            res[l]=res[n]+P[l]
            search(l)

N,Q=acinput()

L=[[]for i in range(N+1)]
visited=[False]*(N+1)
for i in range(N-1):
    try:
        tmp=acinput()
        L[tmp[0]].append(tmp[1])
        L[tmp[1]].append(tmp[0])
    except:
        pass

P=[0]*(N+1)
for i in range(Q):
    tmp=acinput()
    P[tmp[0]]+=tmp[1]

res=[0]*(N+1)
res[1]=P[1]
search(1)

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

Submission status: Runtime Error

Solution code:
def update(node,p,x):
    node[p][1] += x
    for child in node[p][0]:
        update(node,child,x)

NQ = map(int,raw_input().split())
n = NQ[0]
q = NQ[1]

node = [[[],0] for _ in range(n)]

for _ in range(n-1):
    ab = map(int,raw_input().split())
    node[ab[0]-1][0].append(ab[1]-1)

for _ in range(q):
    px = map(int,raw_input().split())
    p = px[0]-1
    x = px[1]
    update(node,p,x)

for r in node: print r[1],

Submission status: Runtime Error

Solution code:
def main():
  n,q = map(int, input().split())
  tree = []
  addition = [0] * n
  result = [0] * n

  for _ in range(n):
    tree.append([])

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

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

  def bfs(x):
    result[x] += addition[x]
    a = tree[x]
    for i in a:
      addition[i] += addition[x]
      bfs(i)

  bfs(0)

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

  print(result[n-1])

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


from sys import stdin
input = stdin.readline
N, Q = map(int, input().split())
abs_ = [list(map(int, input().split())) for _ in range(N-1)]
pxs_ = [list(map(int, input().split())) for _ in range(Q)]


# In[13]:


class Node:
    def __init__(self, nb, data): #コンストラクタ
        self.nb = nb
        self.data = data #ノードがもつ数値
        #self.parent = -1 # nodeがrootのとき-1、それ以外番号
        self.childs = [] # childになるnode classが入る
        
    def connect_childs(self, child_class_):
        self.childs.append(child_class_)


# In[44]:


nodes = [Node(_+1, 0) for _ in range(N)]


# In[45]:


for i in range(N-1):
    a, b = abs_[i]
    nodes[a-1].connect_childs(nodes[b-1])
    nodes[b-1].parent = a-1


# In[46]:


for i in range(Q):
    p, x = pxs_[i]
    nodes[p-1].data += x


# In[47]:


def sum_data_to_childs(node):
    data = node.data
    for child in node.childs:
        child.data += data
        sum_data_to_childs(child)


# In[48]:


sum_data_to_childs(nodes[0])


# In[49]:


datas = [str(nodes[_].data) for _ in range(N)]
print(' '.join(datas))


# In[ ]:

Submission status: Runtime Error

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

res = [0]*(n+1)
def add_x(p, x):
    res[p] += x
    for child in tree[p]:
        new_x = x+adds[child]
        add_x(child, new_x)

add_x(1, adds[1])

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

Submission status: Runtime Error

Solution code:
# 2019/08/18
# AtCoder Beginner Contest 138 - D

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

pdict = dict()
sdict = dict()

for i in range(1, n+1):
    sdict[i] = list()
    sdict[i].append(i)

# Make Tree
for i in range(n-1):
    # Input
    a, b = map(int,input().split())
    pdict[b] = a
#    if sdict.get(a) == None:
#        sdict[a] = list()
#        sdict[a].append(a)
    sdict[a].append(b)
    
    wka = a
    while(wka != 1):
        sdict[pdict[wka]].append(b)
        wka = pdict[wka]

anslist = [0] * (n + 1)

# Calc
for i in range(q):
    # Input
    p, x = map(int,input().split())
#    anslist[p] = anslist[p] + x
    for j in range(len(sdict[p])):
        anslist[sdict[p][j]] = anslist[sdict[p][j]] + x

# Output
anslist.remove(0)
print(*anslist)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
d = {}
ans = [0]*(n+1)
for i in range(n-1):
    sta,gol = map(int,input().split())
    if sta not in d:
        d[sta] = set() 
    d[sta].add(gol)

def dig(d_,sta_):
    ansset = set()
    if sta_ in d_:
        targetset = d_[sta_]
        for t in targetset:
            ansset.add(t)
            tmpset = dig(d_,t)
            ansset= ansset|tmpset
    return ansset
  
for sta in d:
    d[sta] = dig(d,sta)
#print(d)
    
def cal_(ans_,sta_,val_):
    ans_[sta_]+=val_
    if sta_ in d:
        targetset = d[sta_]
        for t in targetset:
            ans_[t]+=val_
    return ans_

for i in range(q):
    sta,val = map(int,input().split())
    ans = cal_(ans,sta,val)
    
for i in range(n):
    print(ans[i+1], " ",end="")

Submission status: Runtime Error

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

ab=[[] for _ in range(n)]
arr=[0 for _ in range(n)]

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

px=[list(map(int,input().split())) for _ in range(q)]
  
  
def search(tree, root):
  arr=[]
  children=tree[root]
  if children == []:
    return None
  else:
    arr.extend(children)
    for child in children:
      ret=search(tree, child)
      if ret is not None:
        arr.extend(ret)    
  return arr
      
for p,x in px:
  children=search(ab,p-1)
  if children is not None:
    children=[p-1]+children
  else:
    children=[p-1]
  for child in children:
    arr[child]+=x
print(*arr)

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(200000)


def main():
    def read_tree(n):
        tree = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            a, b = [int(x) for x in stdin.readline().split()]
            tree[a].append(b)
        return tree

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

    n, q = [int(x) for x in input().split()]
    
    tree = read_tree(n)
    cnt = [0] * (n + 1)

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

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


main()

Submission status: Runtime Error

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

    def add_child(self, node):
        self.children.append(node)

    def add_score(self, score):
        self.score += score


class Tree:
    def __init__(self):
        self.root = Node(1)
        self.nodes = { 1: self.root }

    def add_node(self, parent_num, num):
        parent = self.find_node(parent_num)
        child = Node(num)
        parent.add_child(child)
        self.nodes[num] = child

    def find_node(self, num):
        return self.nodes[num]

    @classmethod
    def add_score(cls, node, score):
        node.add_score(score)
        for n in node.children:
            cls.add_score(n, score)

N, Q = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(1, N):
    A[i], B[i] = map(int, input().split())

P = [0] * (Q+1)
X = [0] * (Q+1)
for i in range(1, Q+1):
    P[i], X[i] = map(int, input().split())

tree = Tree()
for i in range(1, N):
    tree.add_node(A[i], B[i])

for i in range(1, Q+1):
    node = tree.find_node(P[i])
    Tree.add_score(node, X[i])

for i in range(1, N+1):
    node = tree.find_node(i)
    print(node.score, end=' ')

Submission status: Runtime Error

Solution code:


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


def search(n):
    global P,res,visited
    
    visited[n]=True
    for l in L[n]:
        if not visited[l]:
            res[l]=res[n]+P[l]
            search(l)

N,Q=acinput()

L=[[]for i in range(N+1)]
visited=[False]*(N+1)
for i in range(N-1):
    try:
        tmp=acinput()
        L[tmp[0]].append(tmp[1])
        L[tmp[1]].append(tmp[0])
    except:
        pass

P=[0]*(N+1)
for i in range(Q):
    tmp=acinput()
    P[tmp[0]]+=tmp[1]

res=[0]*(N+1)
res[1]=P[1]
search(1)

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

Submission status: Runtime Error

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

# pt, oya, ko
ki = [[0, 0, []] for i in range(N)]

def dfs(target, p, x):
  target.extend(ki[p-1][2])
  ki[p-1][0] += x
  target.pop(0)
  
  if len(target) == 0:
    return
  else:
  	dfs(target, target[0], x)

for i in range(N-1):
  a, b = map(int, input().split())
  ki[a-1][2].append(b)
  ki[b-1][1] = a
  
for i in range(Q):
  p, x = map(int, input().split())
  
  target = [p]
  dfs(target, p, x)
  
print(ki[0][0], end="")
for i in ki[1:]:
  print(" " + str(i[0]), end="")

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
#ABC138D
import copy
import sys
import math

#n = int(input())
tmp = input().split()
n,q = list(map(lambda a: int(a), tmp))

a=[]
b=[]
apex=[]
node=[]

apex.append(0)

node=[]
for i in range(0,n+1):
	node.append([])

for i in range(1,n):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	apex.append(0)
	node[hoge[0]].append(hoge[1])
apex.append(0)

for i in range(1,q+1):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	apex[hoge[0]]+=hoge[1]

#print(apex)

def calc(j):
	for i in node[j]:
		apex[i]+=apex[j]
		calc(i)

calc(1)

ans=str(apex[1])
for i in range(2,n+1):
	ans += " " + str(apex[i])
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

n,q = (int(num) for num in input().split())
par = [i for i in range(n)]
nex = [[] for _ in range(n)]
ch = [0] * n
rank = [1] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    if a > b:
        a,b = b,a
    ab.append((a,b))
ab.sort(key = lambda x: x[0])
    
for item in ab:
    a = item[0]
    b = item[1]
    if rank[a] > rank[b]:
        par[b] = a
        nex[a].append(b)
    elif rank[a] < rank[b]:
        par[a] = b
        nex[b].append(a)
    elif a < b:
        par[b] = a
        nex[a].append(b)
        rank[a] += 1
    else:
        par[a] = b
        nex[b].append(a)
        rank[b] += 1
        
#print(par)
#print(nex)
#print(rank)

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

Submission status: Runtime Error

Solution code:
import numpy as np

temp=list(map(int, input().split()))
N=temp[0]
Q=temp[1]

matrix=np.zeros((N, N), dtype=int)
for i in range(N):
  matrix[i, i]=1

for i in range(N-1):
  temp=list(map(int, input().split()))
  matrix[int(temp[0]-0.5), int(temp[1]-0.5)]=1
  
index=int(N-0.5)
while index>=0:
  matrix[index, :]+=np.sum(matrix*matrix[index, :].reshape(-1, 1), axis=0)
  index=int(index-0.5)
  
matrix[matrix>0]=1

counter=np.zeros(N, dtype=int)
for i in range(Q):
  temp=list(map(int, input().split()))
  counter+=matrix[int(temp[0]-0.5), :]*temp[1]
  
print(' '.join(map(str, map(int, counter.tolist()))))

Submission status: Runtime Error

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

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

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


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

ed=[]

def tansa(n,point):
    global ed
    point+=scores[n]
    ed.append(n)
    for p in ki[n]:
        if not p in ed:
            tansa(p,point)
    else:
        ans[n]=point
        
tansa(1,0)

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

Submission status: Runtime Error

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

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

#print(M)

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

def dfs(start):
    visited[start] = 1
    for child in M[start]:
        if not visited[child]:
            dfs(child)

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

#print(P)

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

n,q=input().split()
n=int(n)
q=int(q)
l=[[] for i in range(n)]
def count(p,x,l,counter):
    counter[p-1]+=x
    for i in l[p-1]:
        counter[i-1]+=x
        if l[i-1]:
            count2(i,x,l,counter)
def count2(p,x,l,counter):
    for i in l[p-1]:
        counter[i-1]+=x
        if l[i-1]:
            count2(i,x,l,counter)
for i in range(n-1):
    a,b=input().split()
    a=int(a)
    b=int(b)
    l[a-1].append(b)
counter=[0 for i in range(n)]
for i in range(q):
    p,x=input().split()
    p=int(p)
    x=int(x)
    count(p,x,l,counter)
for i in counter:
    print(i,end=" ")
print()

Submission status: Runtime Error

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


E2 = [[i] for i in range(n)]

def r(e, chain):
    while True:
        try:
            ee = e.pop()
            E[ee].remove(chain[-1])
        except IndexError:
            break
        for c in chain:
            E2[c].append(ee)
        r(E[ee], chain+[ee]) 

r(E[0], [0])

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

print(*result)

Submission status: Runtime Error

Solution code:
import sys
import collections


def main():
    [n, q] = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [-1] * (n-1)
    b = [-1] * (n-1)
    tree = collections.defaultdict(set)
    for i in range(n-1):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split()]
        tree[a[i]-1].add(b[i]-1)

    p = [-1] * q
    x = [-1] * q
    adds = [0] * n
    for i in range(q):
        p[i], x[i] = [int(s) for s in sys.stdin.readline().strip().split()]
        adds[p[i]-1] += x[i]

    results = [0] * n
    seen = set()

    def rec_add(node, cur):
        cur += adds[node]
        results[node] = cur
        seen.add(node)
        for child in tree[node]:
            if child in seen:
                continue
            rec_add(child, cur)

    rec_add(0, 0)
    print(' '.join([str(n) for n in results]))


main()

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
px = [list(map(int, input().split())) for i in range(q)]

cnt = [0] * n
tree = {}
subt = {}
for i in range(n-1):
    tree.setdefault(ab[i][0], [])
    tree[ab[i][0]].append(ab[i][1])

def adder(node, value):
    cnt[node-1] += value
    if node in tree:
        for i in tree[node]:
            adder(i, value)
for i in range(q):
    adder(px[i][0], px[i][1])
print(" ".join(map(str, cnt)))

Submission status: Runtime Error

Solution code:

  
class Node:
    def __init__(self, data): 
      self.data = data #ノードがもつ数値
      self.child = []
        
    def add(self, x):
      self.data += x
      return self.child
          
n, q = map(int, input().split())
a = []
b = []
nodes = [Node(0)]
for i in range(n-1):
  s = list(map(int, input().split()))
  a.append(s[0])
  b.append(s[1])

  nodes.append(Node(0))
  nodes[a[i]-1].child.append(b[i]-1)
  
p = []
x = []
for i in range(q):
  s = list(map(int, input().split()))
  p.append(s[0])
  x.append(s[1])
  c = nodes[p[i]-1].add(x[i])
  while(True):
    
    d = []
    for j in c:
      for k in nodes[j].add(x[i]):
  	    d.append(k)
    if d == []:
      break
    c = d
   

          
      
 
for j in nodes:
  print(j.data,end=' ')
print()