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:
n,q=map(int,input().split())
a=[[] for i in range(n)]
for i in range(n-1):
  c,d=map(int,input().split())
  if c not in k for k in a:
    a[0].append(c)
while count=0:
  for k in a:
    if c in k:
      a[a.index(k)+1].append(d)
      count+=1
for i in range(q):
  e,f=map(int,input().split())
  while count=0:
  for k in a:
    if e in k:
      for j in a:
        if a.index(j)>=a.index(k):
          e+=f
          for l in j:
            l+=f
     count+=1
      
    
    
print("".join(a))

Submission status: Runtime Error

Solution code:
N,Q= map(int, input().split())
es=[]
ope=[]
for _ in range(N-1):
    a,b=map(int, input().split())
    es.append((a,b))
for _ in range(Q):
    p,x=map(int, input().split())
    ope.append((p,x))
point=[0]*N
import numpy as np
point=np.array(point)
nodes=np.eye(N, dtype=int)
for e in es:
    if sum(nodes[e[0]-1])>=sum(nodes[e[1]-1]):
        nodes[e[0]-1][e[1]-1]=1
        nodes[:,e[1]-1]=np.logical_or(nodes[:,e[1]-1],nodes[:,e[0]-1])
    else:
        nodes[e[1]-1][e[0]-1]=1
        nodes[:,e[0]-1]=np.logical_or(nodes[:,e[1]-1],nodes[:,e[0]-1])
for o in ope:
    point+=nodes[o[0]-1]*o[1]
string=""
for i in range(N):
    string+=str(int(point[i]))+" "
print(string)

Submission status: Runtime Error

Solution code:
N,Q=list(map(int,input().split()))
cnt=[0]*N
dic={}
for _ in range(N-1):
    temp=list(map(int,input().split()))
    dic.setdefault(temp[0],[]).append(temp[1])
p=[]
X=[]
for _ in range(Q):
    temp2=list(map(int,input().split()))
    p.append(temp2[0])
    X.append(temp2[1])
k=dic.keys()

def tree(o):
    cnt[o]+=add
    for y in dic[o]:
        if y in k:
            tree(y)

for x in range(Q):
    add=X[x]
    cnt[p[x]]+=add
    if p[x] in k:
        tree(p[x])

print(*cnt)

Submission status: Runtime Error

Solution code:
def get_subgraph(node):
  subgraph = [node]
  for i, j in edges:
    if node == i:
      subgraph.extend(get_subgraph(j))
  return subgraph

n, q = map(int, input().split())
edges = []
for i in range(n-1):
  e, f = map(int, input().split())
  edges.append((e, f))
edges.reverse()

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

counter = list(map(int, list('0'*n)))

subgraphs = [get_subgraph(i) for i in range(n+1, 1, -1)]

for p, x in tasks:
  for i in subgraphs[p-1]:
    counter[i-1] += x
print(' '.join(map(str, counter)))

Submission status: Runtime Error

Solution code:
N, Q = [int(x) for x in input().split()]
lines = []
while True:
  try:
    lines.append([int(x) for x in input().split()])
  except:
    break
G = lines[:-Q]
O = lines[-Q:]

Gd = {}
for l in G:
  if l[0] not in Gd:
    Gd[l[0]] = []
  Gd[l[0]].append(l[1])
print(Gd)

Od = {}
for l in O:
  if l[0] not in Od:
    Od[l[0]] = []
  Od[l[0]].append(l[1])

counter = {i+1:0 for i in range(N)}
subtrees = {j+1:[] for j in range(N)}
#subtrees[1] = list(range(2, N+1))

def helper(d, i, lst):
  if i not in d:
    return i
  for j in d[i]:
      lst.append(j)
      helper(d, j, lst)
lst = []
print('==>', helper(Gd, 2, lst))
print(lst)
for k in range(1, N+1):
  helper(Gd, k, subtrees[k])

for k, v in Od.items():
  for m in subtrees[k]:
    counters[m] += v
print(counters)

Submission status: Runtime Error

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

ans = [0]*(n-1)
ki = {}
for i in range(1,n+1):
    ki[i] = []

#z = ["1 2", "2 3", "2 4"]

for i in range(n-1):
    e = list(map(int, input().split()))
    #e = list(map(int, z[i].split()))
    ki[e[0]].append(e[1])

#print(ki)

def df(graph, start, point):
    stack = [start]
    visited = []
    while stack:
        v = stack.pop(0)
        ans[v - 1] += point
        if v not in visited:
            visited.append(v)
            stack = graph.get(v, []) + stack

#y = ["2 10", "1 100", "3 1"]
for i in range(q):
    p = list(map(int, input().split()))
    #p = list(map(int, y[i].split()))
    df(ki, p[0], p[1])

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

Submission status: Runtime Error

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

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

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

ans = [0]*(N+1)
checked = [False]*(N+1)

def add(point,num):
    ans[point] += num
    checked[point] = True
    for c in connections[point]:
        if checked[c]:
            continue
        else:
            add(c,num+add_list[c])
            
add(1,add_list[1])

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

Submission status: Runtime Error

Solution code:
class Tree:
  def __init__(self):
    self.ko = []
    self.cnt = 0
  def add_ko(self,a):
    self.ko.append(a)

  def get_ko(self):
    return self.ko
  
  def get_cnt(self):
    return self.cnt
  
  def add_cnt(self,cnt):
    self.cnt += cnt
    for i in self.ko:
      i.add_cnt(cnt)
  
N,Q = map(int,input().split())

node = []
for i in range(N):
  node.append(Tree())

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

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

for i in range(N):
  print(node[i].get_cnt(),end=" ")

Submission status: Runtime Error

Solution code:

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

class Node():
    def __init__(self):
        self.children = []
        self.count = 0



def add_count(G, v):
    for child in G[v].children:
        G[child].count += G[v].count
        add_count(G, child)


def main():
    G = [Node() for _ in range(N)]
    for _ in range(N-1):
        p, c = map(int, input().split())
        G[p-1].children.append(c-1)

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

    add_count(G, 0)

    counts = [node.count for node in G]
    print(*counts)

main()

Submission status: Runtime Error

Solution code:
def main():
  n,q = map(int, input().split())
  tree = []
  addition = [0] * n
  result = [0] * n
  # nodes = [0]
 
  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 dfs(x):
    # if len(tree[nodes[0]]) > 0:
    #   nodes += tree[nodes.pop(0)]
    for i in tree[x]:
      addition[i] += addition[x]
      dfs(i)
 
  dfs(0)
 
  for i in range(n-1):
    print(addition[i], end = " ")
 
  print(addition[n-1])
 
main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
from functools import lru_cache

def main():
    n, q = map(int, input().split())
    ab = [[],[]]
    
    for i in range(n-1):
        na,nb = map(int, input().split())
        ab[0].append(na)
        ab[1].append(nb)

    px = [[],[]]
    for i in range(q):
        np,nx = map(int, input().split())        
        px[0].append(np)
        px[1].append(nx)
    
    # print(n,q,ab,px)
    count = [0 for i in range(n)]

    lgth = max(ab[0])
    node =[[] for i in range(lgth)]
    for i in range(n-1):
        index = ab[0][i]-1
        put = ab[1][i]
        node[index].append(put)

    # print(node)
    @lru_cache(maxsize = 2000)
    def calc(idx,val):
        count[idx] += val

        if idx <= lgth-1:
            for j in node[idx]:
                calc(j-1,val)
        
    for i in range(len(px[0])):    
        calc(px[0][i]-1, px[1][i])
    
    print(' '.join(map(str,count)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self,name):
        self.name=name
        self.parent=[]
        self.counter=0
        self.children=[]
    def plus(self,num):
        self.counter+=num
        
n,q=[int(i) for i in input().split()]
henn=[]
        
#辺の情報    
for i in range(n-1):
    henn.append([int(i) for i in input().split()])


#カウンタの情報
plusdata=[]
for i in range(q):
    plusdata.append([int(i) for i in input().split()])   


#ノードの作成
nodelist=[]
for i in range(n):
    nodelist.append(Node(i+1))

#親の登録

#全て登録
for i in henn:
    nodelist[i[0]-1].parent.append(nodelist[i[1]-1])
    nodelist[i[1]-1].parent.append(nodelist[i[0]-1])
# for i in range(n):
#     print(nodelist[i].name,nodelist[i].parent,nodelist[i].counter)
    
node0=Node(0)
nodelist[0].parent.append(node0)

#排除
def parentdelete(node,i):
    for j in node.parent:
        if i==j:
            a=j
            node.parent.remove(a)
    node.children=node.parent
    for j in node.parent:
        parentdelete(j,node)
    node.parent=a
    
        
parentdelete(nodelist[0],node0)
    
# for i in range(n):
#     print(nodelist[i].name,nodelist[i].parent,nodelist[i].counter)
    
#カウンタの更新
for i in plusdata:
    nodelist[i[0]-1].plus(i[1])

# for i in nodelist:
#     print(i.counter)
    
anslist=[0 for i in range(n)]

def plusplus(node):
    global anslist
    name=node.name
    parent
    
def abc(node):
    node.counter+=node.parent.counter
    anslist[node.name-1]=node.counter
    for j in node.children:
        abc(j)
    
abc(nodelist[0])

for i in range(n):
    anslist[i]=str(anslist[i])
print(" ".join(anslist))

Submission status: Runtime Error

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

tree = [{'count':0,'children':[]} for _ in range(N)]

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

def counter(p,x):
    tree[p]['count'] += x
    if tree[p]['children'] != []:
        for child in tree[p]['children']:
            counter(child,x)

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

printer = [str(node['count']) for node in tree]
print(' '.join(printer))

Submission status: Runtime Error

Solution code:
def comp(s, l):
    ans = set(s)
    l2 = s
    for i in l2:
        if i != 0:
            ans = ans | comp(l[i], l)
    return ans


def solve():
    n, q = map(int, input().split())
    l = [[0] for i in range(n+1)]
    ans = [0]*(n+1)
    for i in range(n-1):
        a, b = map(int, input().split())
        l[a].append(b)
    for i in range(q):
        num, point = map(int, input().split())
        li = list(comp(l[num], l))
        print(li)
        li.append(num)
        li = list(set(li))
        for j in li:
            ans[j] += point
    print(ans[1::])


if __name__=="__main__":
    solve()

Submission status: Runtime Error

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

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

parent = [[0]] * N

#2
for i in range(N):
    parent[i].append(i + 1)

    if i != N-1:
        parent[a[i] - 1].append(b[i])

# 1
#for i in range(N - 1):
#    parent[a[i] - 1].append(b[i])

# 3
for i in range(N):
    for j in range(len(parent[i])):
        for k in range(len(parent[parent[i][j]-1])):
            parent[i].append(parent[parent[i][j]-1][k])

#4
for i in range(N):
    parent[i] = list(set(parent[i]))

###########33

value = [0] * N

for i in range(Q):
    for j in range(len(parent[p[i]-1])):
        value[parent[p[i]-1][j]] = x[i]
        print(parent[p[i]-1][j])


###
#for i in range(N):
#    print(value[i])

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
ans = {x + 1: 0 for x in range(n)}
node = {}
for i in range(n - 1):
    parent, child = map(int, input().split())
    if parent not in node:
        node[parent] = []
    node[parent].append(child)
def plus(parent, value):
    if parent not in node:
        ans[parent] += value
    else:
        ans[parent] += value
        childs = node[parent]
        for child in childs:
            plus(child, value)
for i in range(q):
    p, x = map(int, input().split())
    plus(p, x)
ans_list = []
for i in ans.values():
    ans_list.append(i)
print(' '.join(map(str, ans_list)))

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)
ans = [0] * (N + 1)


def dfs(e, v, x):
    seen[v] = True
    ans[v] += x
    for next_v in e[v]:
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v, x + q[next_v])


dfs(e, 1, q[1])
ans = ans[1:]

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

print()

Submission status: Runtime Error

Solution code:
N ,Q = map(int,input().split())
tree = []
counters = {i:0 for i in range(1,Q+1)}
nodes = [0 for i in range(N)]
tree_list = [[] for i in range(N+1)]
for i in range(N-1):
  a,b = map(int,input().split())
  tree_list[a].append(b)
tree = sorted(tree)
for i in range(Q):
  a,b = map(int,input().split())
  counters[a] += b

for i in range(len(tree_list)-1,0,-1):
  for j in tree_list[i]:
    tree_list[i].extend(tree_list[j])
  
for p,x in counters.items():
  nodes[p-1] += x
  for i in tree_list[p]:
    nodes[i-1] += x

for i in nodes:
  print(i,end=' ')

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(3000)

def add_value(tree, p, x):
    tree[p]["value"] += x
    if len(tree[p]["node"]) == 0:
        return 0
    for next_node_index in tree[p]["node"]:
        add_value(tree, next_node_index, x)

N, Q = map(int, input().split(" "))
tree = {}
for _ in range(N-1):
    a, b = map(int, input().split(" "))
    if not a in tree:
        tree[a] = {"value": 0, "node":[]}
    tree[a]["node"].append(b)

    if not b in tree:
        tree[b] = {"value": 0, "node":[]}

for _ in range(Q):
    p, x = map(int, input().split(" "))
    add_value(tree, p, x)

print(*[tree[i]["value"] for i in range(1, N+1)])

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split()))
childs = [set() for _ in range(n)]
nodes = [0 for _ in range(n)]
for _ in range(n - 1):
    line = input().split()
    a, b = int(line[0]), int(line[1])
    childs[a - 1].add(b - 1)


def add(i, k):
    global childs
    nodes[i] += k
    for j in childs[i]:
        add(j, k)


for _ in range(q):
    line = input().split()
    i, k = int(line[0]), int(line[1])
    add(i - 1, k)

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
stdin = sys.stdin
 
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
s = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

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

seen = [0] * n

def dfs(v):
        seen[v] = True
        for next_v in G[v]:
                if seen[next_v]:
                        continue
                dfs(next_v)
ans = np.zeros(n)
for i in range(q):
        p, x = na()
        seen = np.zeros(n)
        dfs(p-1)
        seen[p-1] = True
        ans += x * seen
ans = ans.astype(np.int32)

print(*ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
# from functools import reduce
from collections import defaultdict


def main():
    # n, q
    n, q = map(int, input().split())

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

    # p, x
    p = []
    x = []
    for _ in range(0, q):
        pi, xi = map(int, input().split())
        p.append(pi)
        x.append(xi)

    print(process(n, q, a, b, p, x))


def process(n, q, a, b, p, x):
    points = [0] * (n + 1)
    graph = defaultdict(list)
    for i in range(0, n - 1):
        graph[a[i]].append(b[i])

    for i in range(0, q):
        target = p[i]
        xi = x[i]
        subtree(points, target, graph, xi)

    # print(points)
    points.pop(0)

    points_sorted = map(str, points)
    return ' '.join(points_sorted)


def subtree(points, target, graph, x):
    points[target] += x
    for i in graph[target]:
        subtree(points, i, graph, x)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
tmp=[int(i) for i in input().split(" ")]
n = tmp[0]
q = tmp[1]
lis = [[] for i in range(n)]
for i in range(n-1):
    tmp = [int(i) for i in input().split(" ")]
    lis[tmp[0]-1].append(tmp[1])
datas = np.array([0 for i in range(n)])
def rec(lis, ind, ret):
    tmp = lis[ind].copy()   
    for i in lis[ind]:
        tmp += rec(lis, i-1, tmp)
    return tmp
for i in range(q):
    tmp=[int(i) for i in input().split(" ")]
    p = tmp[0]
    x = tmp[1]
    mask = np.unique([p]+rec(lis, p-1, []))-1
    datas[mask] += x
print(" ".join(datas.astype(str)))

Submission status: Runtime Error

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

ans = [0]*n-1
ki = {}
for i in range(1,n+1):
    ki[i] = []

#z = ["1 2", "2 3", "2 4"]

for i in range(n-1):
    e = list(map(int, input().split()))
    #e = list(map(int, z[i].split()))
    ki[e[0]].append(e[1])

#print(ki)

def df(graph, start, point):
    stack = [start]
    visited = []
    while stack:
        v = stack.pop(0)
        ans[v - 1] += point
        if v not in visited:
            visited.append(v)
            stack = graph.get(v, []) + stack

#y = ["2 10", "1 100", "3 1"]
for i in range(q):
    p = list(map(int, input().split()))
    #p = list(map(int, y[i].split()))
    df(ki, p[0], p[1])

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

Submission status: Runtime Error

Solution code:
def adx(p,oya,tox,total):
  tox[p] += total
  total = tox[p]
  if(len(oya[p]) == 0):
    return 0

  else:
    for i in oya[p]:
      adx(i,oya,tox,total)

  return 0

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

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

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

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

_ = adx(1,oya,tox,0)

tox.pop(0)

print(*tox)

Submission status: Runtime Error

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, y):
        if 0 == x:
            return

        pa = self.par[x]
        self.children[pa].add(y)
        self.find(pa, y)
        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, 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: Runtime Error

Solution code:
s = list(str(input()))
t = list(str(input()))

ans = []
for a in t:
    ans.append([i for i, x in enumerate(s) if x == a])

ans2 = 0

if [] in ans:
    print(-1)
else:
    _v = 0
    for y in ans:
        c = [x for x in y if _v < x]
        if c = []:
            ans2 += 1
            _v = min(y)
        else:
            _v = minc(c)
    print(ans2*len(s) + _v + 1)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline


def get_children(parent, child_dict):
    children = child_dict.get(parent, [])
    for child in children:
        yield from get_children(child, child_dict)
    yield parent


def main():
    n, q = [int(i) for i in input().split()]
    scores = [0 for i in range(n)]
    lines = [[int(i) for i in input().split()] for _ in range(n - 1)]
    counter = [[int(i) for i in input().split()] for _ in range(q)]
    child_dict = {}
    for parent, child in lines:
        if parent not in child_dict:
            child_dict[parent] = [child]
        else:
            child_dict[parent].append(child)
    for parent, count in counter:
        for child in get_children(parent, child_dict):
            scores[child - 1] += count
    print(' '.join(map(str, scores)))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy.linalg import matrix_power

N, Q = list(map(int, input().split()))
# N: 頂点数
# Q: 操作

ABs = tuple(tuple(map(int, input().split())) for _ in range(N-1))
# (A,B) 辺の index
PXs = tuple(tuple(map(int, input().split())) for _ in range(Q))
# P: 頂点
# X: 足しこむ値

des = np.identity(N, dtype=bool)
for A, B in ABs:
    des[A-1, B-1] = True
des = matrix_power(des, N-1)

b = np.zeros((N,1), dtype=int)
for P, X in PXs:
    b[P-1] += X

print(' '.join(str(a[0]) for a in np.dot(des.T, b)))

# parent = [None] * N
# children = [[] for _ in range(N)]

# print(ABs)
# print(PXs)


# print(parent)
# print(children)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
from functools import lru_cache

def main():
    n, q = map(int, input().split())
    ab = [[],[]]
    
    for i in range(n-1):
        na,nb = map(int, input().split())
        ab[0].append(na)
        ab[1].append(nb)

    px = [[],[]]
    for i in range(q):
        np,nx = map(int, input().split())        
        px[0].append(np)
        px[1].append(nx)
    
    # print(n,q,ab,px)
    count = [0 for i in range(n)]

    lgth = max(ab[0])
    node =[[] for i in range(lgth)]
    for i in range(n-1):
        index = ab[0][i]-1
        put = ab[1][i]
        node[index].append(put)

    # print(node)
    @lru_cache(maxsize = 1000)
    def calc(idx,val):
        count[idx] += val

        if idx <= lgth-1:
            for j in node[idx]:
                calc(j-1,val)
        
    for i in range(len(px[0])):    
        calc(px[0][i]-1, px[1][i])
    
    print(' '.join(map(str,count)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self,name):
        self.name=name
        self.parent=[]
        self.counter=0
        self.children=[]
    def plus(self,num):
        self.counter+=num
        
n,q=[int(i) for i in input().split()]
henn=[]
        
#辺の情報    
for i in range(n-1):
    henn.append([int(i) for i in input().split()])


#カウンタの情報
plusdata=[]
for i in range(n-1):
    plusdata.append([int(i) for i in input().split()])   


#ノードの作成
nodelist=[]
for i in range(n):
    nodelist.append(Node(i+1))

#親の登録

#全て登録
for i in henn:
    nodelist[i[0]-1].parent.append(nodelist[i[1]-1])
    nodelist[i[1]-1].parent.append(nodelist[i[0]-1])
# for i in range(n):
#     print(nodelist[i].name,nodelist[i].parent,nodelist[i].counter)
    
node0=Node(0)
nodelist[0].parent.append(node0)

#排除
def parentdelete(node,i):
    for j in node.parent:
        if i==j:
            a=j
            node.parent.remove(a)
    node.children=node.parent
    for j in node.parent:
        parentdelete(j,node)
    node.parent=a
    
        
parentdelete(nodelist[0],node0)
    
# for i in range(n):
#     print(nodelist[i].name,nodelist[i].parent,nodelist[i].counter)
    
#カウンタの更新
for i in plusdata:
    nodelist[i[0]-1].plus(i[1])

# for i in nodelist:
#     print(i.counter)
    
anslist=[0 for i in range(n)]

def plusplus(node):
    global anslist
    name=node.name
    parent
    
def abc(node):
    node.counter+=node.parent.counter
    anslist[node.name-1]=node.counter
    for j in node.children:
        abc(j)
    
abc(nodelist[0])

for i in range(n):
    anslist[i]=str(anslist[i])
print(" ".join(anslist))

Submission status: Runtime Error

Solution code:

import sys

sys.setrecursionlimit(200000)

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

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

for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x
    
que = [0]
visited[0] = 1
last = 0
while que != []: 
    idx = que.pop(0)
    val[idx] += last
    last = val[idx]
    for i in neighbor[idx]:
        if visited[i] == 0:
            visited[i] = 1
            que.append(i)
            
for num in val:
    ans += str(num) + " "
print(ans)

Submission status: Runtime Error

Solution code:
n, q = map(int,input().split())
cnt = [0] * (n+1)
import numpy as np
tree = np.zeros((n+1, n+1))
part = [0] * (n+1)
for i in range(n-1):
    a, b = map(int,input().split())
    tree[a][b] = 1
def dfs(i):
    ret = [i]
    global part
    if tree[i] == [0] * n:
        part[i] = ret
        return ret
    for j in range(n+1):
        if tree[i][j] == 1:
            ret.extend(dfs(j))
    part[i] = ret
    return ret
dfs(1)
for _ in range(q):
    p,x = map(int,input().split())
    for node in part[p]:
        cnt[node] += x
print(*cnt[1:])

Submission status: Runtime Error

Solution code:
import numpy as np

n,q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n+q-1)]

matrix = np.zeros((n,n))
ans = np.zeros((n,n))

for i in range(n-1):
  matrix[ab[i][0]-1,ab[i][1]-1] = 1
#  matrix[ab[i][1]-1,ab[i][0]-1] = 1

for l in range(n):
  for m in range(n):
    if matrix[l][m]:
      for o in range(n):
        if matrix[m][o]:
          matrix[l][o] = 1
          
ans = np.zeros((n))

for j in range(n-1,n+q-1):
  ans[ab[j][0]-1] += ab[j][1]
  print("ansans",ans)
  for k in range(n):
    if matrix[ab[j][0]-1][k] == 1:
      print(ab[j][1])
      ans[k] += ab[j][1]
  

print(ans)

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
ans=[0]*N;con=[0]*N;ab=[]
for i in range(N-1):
    a, b = map(int, input().split())
    con[b-1] = a

def dfs(Q, X):
    ans[Q-1] += X
    for n in range(N)[Q:]:
        if con[n] == Q:
            dfs(n+1,X)

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

print(*ans)

Submission status: Runtime Error

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

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

class Node():
    def __init__(self):
        self.children = []
        self.count = 0



def add_count(G, v):
    for child in G[v].children:
        G[child].count += G[v].count
        add_count(G, child)


def main():
    G = [Node() for _ in range(N)]
    for _ in range(N-1):
        p, c = map(int, input().split())
        G[p-1].children.append(c-1)

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

    add_count(G, 0)

    counts = [node.count for node in G]
    print(*counts)

main()

Submission status: Runtime Error

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 = [tuple(map(int, input().split())) for _ in range(N-1)][::-1]
counts = np.zeros(N, dtype=np.int32)

for a, b in edges:
    children[a-1] += children[b-1]

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

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

Submission status: Runtime Error

Solution code:
N, Q = (int(i) for i in input().split())
a_b = [[int(i) for i in input().split()] for i in range(N - 1)]
p_x = [[int(i) for i in input().split()] for i in range(Q)]

child = {}
parent = {}
for ab in a_b:
    parent[ab[1]] = ab[0]
    child[ab[0]] = child.get(ab[0], [])
    child[ab[0]].append(ab[1])

for k, v in child.items():
    if k != 1:
        child[parent[k]] += v

ans = {}
for px in p_x:
    ans[px[0]] = ans.get(px[0], 0) + px[1]
    if px[0] in child.keys():
        for node in child[px[0]]:
            ans[node] = ans.get(node, 0) + px[1]

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

Submission status: Runtime Error

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

tree = [{'count':0,'children':[]} for _ in range(N)]

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

def counter(p,x):
    tree[p]['count'] += x
    if tree[p]['children'] != []:
        for child in tree[p]['children']:
            counter(child,x)

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

for node in tree:
    print(str(node['count']) + ' ', end='')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
 
def search(i):
    global edge, child, visit
    work= {i}
    visit[i]= True
    #
    for e in edge[i]:
        if visit[e]: continue
        work|= search(e)
    #
    child[i]= work
    return work
 
import sys
 
n,q = [ int(x) for x in sys.stdin.readline().strip().split() ]
n1= n-1
sys.setrecursionlimit(2*10**5)
#
edge= [ [] for _ in range(n) ]
for i in range(n1):
    a,b = [ int(x)-1 for x in sys.stdin.readline().strip().split() ]
    edge[a].append( b )
    edge[b].append( a )
#
 
visit= [ False for _ in range(n) ]
child= [ set() for _ in range(n) ]
search(0)
#
query= dict()
for i in range(q):
    p,x= [ int(x) for x in sys.stdin.readline().strip().split() ]
    query[p-1]= query.get(p-1,0) + x
#
score= [ 0 for _ in range(n) ]
for p,x in query.items():
    for v in child[p]: score[v]+= x
#
for s in score: print( s,end= " " )