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

print node

Submission status: Runtime Error

Solution code:
#include<algorithm>
#include<cstdio>
#include<vector>

using namespace std;

const int N_MAX = 2 * 1e5, Q_MAX = 2 * 1e5;

struct ver {
    int cnt = 0;
    vector<int> to;
};

ver v[N_MAX];
int cost[N_MAX];

void dfs(int, int);

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        v[a - 1].to.push_back(b - 1);
        v[b - 1].to.push_back(a - 1);
    }
    for (int i = 0; i < q; i++) {
        int cn, cc;
        scanf("%d %d", &cn, &cc);
        cost[cn - 1] += cc;
    }

    dfs(0, 0);
    
    for (int i = 0; i < n - 1; i++) printf("%d ", v[i].cnt);
    printf("%d\n", v[n - 1].cnt);
    return 0;
}

void dfs(int m, int prn) {
    v[m].cnt = v[prn].cnt + cost[m];
    while (v[m].to.size() > 0) {
        if (v[m].to.back() != prn) dfs(v[m].to.back(), m);
        v[m].to.pop_back();
    }
}

Submission status: Runtime Error

Solution code:
tmp = list(map(int, input().split()))
N, Q = tmp[0], tmp[1]

import numpy as np

tree = np.zeros([N,N])
for i in range(N-1):
    tmp = list(map(int, input().split()))
    tree[tmp[0]-1,tmp[1]-1] = 1

point = np.zeros([N])
for i in range(Q):
    q = list(map(int, input().split()))
    if q[0] == N:
        q_tmp = np.where(tree[(q[0]-1),:] == 1)
    else:
        q_tmp = np.where(tree[(q[0]-1):,:] == 1)
   
    for j in q_tmp[1]:
        point[j] += int(q[1])
    point[q[0]-1] += int(q[1])

point = point.tolist()
point= [int(n) for n in point]

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

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

dic = {}
node_list = set()
for ab in a_b:
    dic[ab[0]] = dic.get(ab[0], [])
    dic[ab[0]].append(ab[1])
    node_list.add(ab[0])
    node_list.add(ab[1])

ans = {}
for px in p_x:
    stack = [px]
    while len(stack) > 0:
        tmp = stack.pop()
        ans[tmp[0]] = ans.get(tmp[0], 0) + tmp[1]
        if tmp[0] in dic.keys():
            for node_num in dic[tmp[0]]:
                stack.append([node_num, tmp[1]])

sorted_nodes = sorted(list(node_list))

for i in sorted_nodes:
    print(ans[i], 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:
def cn(d,l,p):
    global a
    if(l>0):
        ll=0
        for i in a[d]:
            b[i-1]+=p
            ll=len(a[i-1])
            cn(i-1,ll,p)

n,q=map(int,input().split())
t=0
a=[]
b=[]
for i in  range(n):
    a.append([])
    b.append(0)
t0=0
for i in range(n-1):
    t=list(map(int,input().split()))
    a[t[0]-1].append(t[1])
l=0
for i in range(q):
    t=list(map(int,input().split()))
    t0=t[0]-1
    l=len(a[t0])
    b[t0]+=t[1]
    cn(t0,l,t[1])
print(*b)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
tree = [list(map(int, input().split())) for i in range(N-1)]
counter = [list(map(int, input().split())) for i in range(Q)]
dic = {}
for i in tree:
  try:
    dic[i[0]].append(i[1])
  except KeyError:
    dic[i[0]] = [i[1]]
keys = dic.keys()
for i in tree:
  if i[1] not in keys:
    dic[i[1]] = []
q = {i: 0 for i in dic.keys()}

def child_sum(q,v, child):
  if child == []:
    #print('test', q, v, child)
    return q
  else:
    for j in child:
      
      q[j] += v
      child = dic[j]
      #print('test2', j, v, child)
      q = child_sum(q, v, child)
  return q
    
for i, v in counter:
  q[i] += v
  child = dic[i]
  #print(q, i, child)
  q = child_sum(q, v, child)

Submission status: Runtime Error

Solution code:
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 = int(input())
a = []
b = []
for i in range(1,N):
    a1,b1=[int(i) for i in input().split()]
    a.append(a1)
    b.append(b1)
p = []
x = []

for i in range(1,Q+1):
    p1,x1=[int(i) for i in input().split()]
    p.append(p1)
    x.append(x1)
    
sum_N = []
for i in range(1,Q + 1):
  if p[i] == a[k]:
    sum_N[a[k]] = sum_N[a[k]] + x[i]
    sum_N[b[k]] = sum_N[b[k]] + x[i]
    if a[s] == b[k] and k<s:
      sum_N[a[s]] = sum_N[a[s]] + x[i]
      sum_N[b[s]] = sum_N[b[s]] + x[i]
      if a[w] == b[s] and s<w:
        sum_N[a[w]] = sum_N[a[w]] + x[i]
        sum_N[b[s]] = sum_N[b[s]] + x[i]

print(sum_N)

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+1)]
ans = [0 for i in range(n+1)]

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

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

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, key):
	self.key = key
        self.child = []
        self.point = 0

n, q = map(int, input().split())
#a, b, p, x = [], [], [], []
a, b = [None] * n, [None] * n
p, x = [None] * q, [None] * q

nodes = []
nodes.append(None)
ans = []

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

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

# Make node list
for i in range(1, n+1):
    node = Node(i)
    nodes.append(node)

for i in range(n-1):
    nodeParent = nodes[a[i]]
    nodeChild = nodes[b[i]]
    nodeParent.child.append(nodeChild)

def printNode(node):
#    print(node.point)
    ans.append(node.point)
    for child in node.child:
	printNode(child)

def addCount(node, point):
    node.point += point
    for child in node.child:
	addCount(child, point)

for i in range(q):
    node = nodes[p[i]]
    addCount(node, x[i])

printNode(nodes[1])

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

Submission status: Runtime Error

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

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

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

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

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

for i in range(n):
    if opef[i]==False:
        opef[i]=True
        counter(i,ope[i])

print(*ret)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
edges = []
counter = [0] * n
for i in range(n-1):
    edges.append(list(map(int, input().split())))
edges = sorted(edges, key=lambda x: x[0])
actions = []

def increaseChildren(i, x):
    children = map(lambda node:node[1], filter(lambda node:node[0]==i, edges))
    for child in children:
        counter[child-1] += x
        increaseChildren(child, x)

for i in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x
    increaseChildren(p, x)
print(' '.join(map(str, counter)))

Submission status: Runtime Error

Solution code:
def h(p,x):
    c[p]+=x
    if p in t:
        for i in t[p]:
            h(i,x)

n,q=map(int,input().split())
t={}
c=[0 for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    if a in t:
        t[a].append(b)
    else:
        t[a]=[b]

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

print(*c[1:])

Submission status: Runtime Error

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

# vertexes list contained in the ith subtree root
tree = [[] for _ in range(N)]

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

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

def dfs(counter, p, x):
    counter[p] += x

    vertexes = tree[p]
    for v in vertexes:
        dfs(counter, v, x)

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

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

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, data): #コンストラクタ
        self.data = data 
        self.kodomo = []
        self.cnt = 0
        
def saiki(target,tasu,n):
  #target = array[]
  target.cnt += tasu
  for ko in target.kodomo:
    if ko<n:
      saiki(array[ko],tasu,n)
  
        
n, q = [int(i) for i in input().split()]
array=[]
 
for i in range(n):
  array.append(Node(i+1))
  
  
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  array[a-1].kodomo.append(b-1)

  
for i in range(q):
  x, tasu = [int(i) for i in input().split()]
  if x-1<n:
    saiki(array[x-1],tasu,n)
  
for i in range(n):
  if i != n-1:
    print(array[i].cnt, end =" ")
  else:
    print(array[n-1].cnt)

Submission status: Runtime Error

Solution code:

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

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

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)

counters_map = [None for i in range(N)]

def dfs(idx, parent):
    global counters_map
    if counters_map[idx]:
        return counters_map[idx]
    counter = [idx]
    for child in edge_map[idx]:
        if child == parent:
            continue
        counter.extend(dfs(child, idx))
    counter = list(set(counter))
    counters_map[idx] = counter
    return counter

dfs(0, None)

counters = [0 for i in range(N)]

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [0 for i in range(N)]
for i in range(N):
    diff = counters[i]
    for child_idx in counters_map[i]:
        res_list[child_idx] += diff

ans = ""
for res in res_list:
    ans += str(res) + " "
print(ans)

Submission status: Runtime Error

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

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

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

def counter(target,num):
    global ret
    global ope
    global opef
    

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

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

for i in range(n):
    if opef[i]==False:
        opef[i]=True
        counter(i,ope[i])

print(*ret)

Submission status: Runtime Error

Solution code:
import numpy as np
N,Q = map(int,input().split())
a = []
b = []
p = []
x = []
ans = np.array([0]*N)
test = np.array([1]*N)
test = np.diag(test)
for i in range(1,N):
    ai,bi = map(int,input().split())
    test[ai-1,bi-1]+=1
    # a.append(ai)
    # b.append(bi)

for k in reversed(range(N)):
    check = np.where(test[k] > 0)
    test[k]+=np.sum(test[check],axis=0)
test = np.where(test > 0,1,0)
# print(test)

for j in range(Q):
    pj,xj = map(int,input().split())
    temp = test[pj-1]*xj
    ans += temp

    # p.append(pj)
    # x.append(xj)
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

n, q = map(int, input().split())
dic = {}
dic2 = {}

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

for _ in range(n - 1):
    a, b = map(int, input().split())
    if not (a in dic2):
        dic2[a] = 0
    dic2[a] = dic2[a]+b

v_list = [0 for _ in range(n)]


def add_v(num, value):
    v_list[num - 1] = v_list[num - 1] + value
    if num in dic:
        for root in dic[num]:
            add_v(root, value)


for i in dic2:
    add_v(i, dic2[i])


print(*v_list)

Submission status: Runtime Error

Solution code:
N, Q = map(int,input().split())
class Node():
  def __init__(self):
    self.counter = 0
    self.children = []
  def add_point(self,x):
    self.counter += x
    for child in self.children:
      child.add_point(x)

nodes = [Node() for y in range(N)]

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

for j in range(Q):
  p, x = map(int,input().split())
  nodes[p-1].add_point(x)

ans = ""
for nod in nodes:
  ans += (str(nod.counter) + " ")

print(ans[:-1])

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)
P = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    P[p-1] += x
result = [0] * n
E2 = [[i] for i in range(n)]

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

r(E[0], [0])

for i, x in enumerate(P):
    for e2 in E2[i]:
        result[e2] += x

print(*result)

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, x = [int(i) for i in input().split(" ")]
    PX[p-1] += x

ans = [0 for _ in range(N)]
visited = [False for _ in range(N)]
def dfs(i, v):
    if visited[i]:
        return
    visited[i] = True
    ans[i] += v
    for j in edges[i]:
        dfs(j, v + PX[j])
dfs(0, PX[0])
for a in ans:
    print(a, end=" ")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = {}
for i in range(n-1):
    ai, bi = map(int,input().split())
    if ai-1 in d:
        d[ai-1] += [bi-1]
    else:
        d[ai-1] = [bi-1]
    if bi-1 in d:
        d[bi-1] += [ai-1]
    else:
        d[bi-1] = [ai-1]
#point
px = {}
for i in range(q):
    pi,xi = map(int,input().split())
    if pi- 1 in px:
        px[pi-1] += xi
    else:
        px[pi-1] = xi
sp = [0 for i in range(n)]

def f(v,vp,p):
    su = p + px[v]
    sp[v] = su
    if v in d:
        for di in d[v]:
            if not di == vp:
                f(di,v,su)
f(0,0,0)
for i in range(n):
    print(sp[i])

Submission status: Runtime Error

Solution code:
from collections import deque

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)

# make a function
def add(lst, p, x):
    if child[p] == []:
        lst[p] += x
    else:
        lst[p] += x
        for v in child[p]:
            add(lst, v, x)

## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    add(count, p, x)
    
print(' '.join(map(str, count)))

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 = []
for i in range(n-1):
  s = list(map(int, input().split()))
  a.append(s[0])
  b.append(s[1])

nodes = [Node(0)]


for i,k in enumerate(a):
  nodes.append(Node(0))
  nodes[k-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])
for i in range(q):
  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)

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 pt(node, subt):
    if not node in subt:
        part = []
        if node in tree:
            for i in range(len(tree[node])):
                part += pt(tree[node][i], subt)
        subt.setdefault(node, [node]+part)
    return subt[node]
pt(1,subt)

for i in range(q):
    for j in subt[px[i][0]]:
        cnt[j-1] += px[i][1]
print(" ".join(map(str, cnt)))

Submission status: Runtime Error

Solution code:
from collections import deque

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)

# make a function
def add(lst, p, x):
    if child[p] == []:
        lst[p] += x
    else:
        lst[p] += x
        for v in child[p]:
            add(lst, v, x)

## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    add(count, p, x)
    print(count)

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

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-=1
  
matrix[matrix>0]=1

counter=np.zeros(N)
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())
nodes = set()
stree = {}
for n in range(N-1):
    a, b = map(int, input().split())
    nodes.add(a)
    if stree.get(a) is None:
        stree[a] = set()
    stree[a].add(b)
memo = {}
def fla(stree, p):
    cs = stree.get(p)
    if cs is None:
        return None
    if memo.get(p) is not None:
        return memo[p]
    subs = set(cs)
    for c in cs:
        r = fla(stree, c)
        memo[c] = r
        if r is not None:
            subs |= r
        else:
            subs.add(c)
    memo[p] = subs
    return subs

x = [0]*N
# flatten
node_fla = {}
for a in nodes:
    node_fla[a] = fla(stree, a)

for q in range(Q):
    node, add = map(int,input().split())
    x[node-1] += add
    if node_fla.get(node) is not None:
        for c in node_fla[node]:
            x[c-1] += add
print(' '.join(map(str, x)))

Submission status: Runtime Error

Solution code:
#import numpy as np

L = []
T = []

def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A


def setTree(root):
    T[root].add(root)
    for branch in L[root]:
        if not branch in T[root]:
            T[branch] = set() | T[root]
            setTree(branch)


if __name__ == '__main__':
    N, Q = InputToInt()    
    for i in range(N):
        L.append(set())
        T.append(set())
    
    for i in range(N-1):
        a, b = InputToInt()
        L[a-1].add(b-1)
        L[b-1].add(a-1)

    setTree(0)
    
    S = [0]*N
    for i in range(Q):
        p, x = InputToInt()
        for j in range(N):
            if p-1 in T[j]:
                S[j] += x

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

Submission status: Runtime Error

Solution code:
def h(p,x):
    c[p]+=x
    if t[p]!=[]:
        for i in t[p]:
            h(i,x)

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

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

print(*c[1:])

Submission status: Runtime Error

Solution code:
N, Q = map(int,input().split())
class Node():
  def __init__(self):
    self.counter = 0
    self.children = []
  def add_point(self,x):
    self.counter += x
    for child in self.children:
      child.add_point(x)

nodes = [Node()] * N

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

for j in range(Q):
  p, x = map(int,input().split())
  nodes[p-1].add_point(x)

ans = ""
for nod in nodes:
  ans += (str(nod.counter) + " ")

print(ans[:-1])

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)
    ki[b].append(a)

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

ed=[]

def tansa(n,point):
    global ed
    point+=scores[n]
    ed.append(n)
    for p in ki[n]:
        if not p in ed:
            try:
                tansa(p,point)
            except:
                return 0
    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 f(t_index,result,s):
    if t_index in t_keys:
        for one in tree_dict[t_index]:
            f(one,result,s)
    result[t_index] += s
            
n,q = map(int,input().split())
tree_dict = dict()
for i in range(n-1):
    tmp =  list(map(int,input().split()))
    try:
        tree_dict[tmp[0]] = tree_dict[tmp[0]] + [tmp[1]]
    except KeyError:
        tree_dict[tmp[0]] = [tmp[1]] 
        
        

score = dict()
for i in range(q):
    tmp = list(map(int,input().split()))
    try:
        score[tmp[0]] += tmp[1]
    except KeyError:
        score[tmp[0]] = tmp[1]


t_keys = set(tree_dict.keys())
s_keys = set(score.keys())
result = [0 for _ in range(n+1)]
for one in s_keys:
    s = score[one]
    if one in t_keys:
        for t_index in tree_dict[one]:
            f(t_index,result,s)
        result[one] += s 
    else:
        result[one] += s
        
tmp_str = ""
for one in result[1:]:
    tmp_str += str(one) + " "
tmp_str = tmp_str[:-1]
print(tmp_str)

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 y in a2:
        a2[y].append(x)
    else:
        a2[y] = [x]
root = [-1] * n

def c(ind=0, ro=0):
    global root
    if root[ind] != -1:
        return 0
    root[ind] = ro
    if ind in a1:
        for i in a1[ind]:
            if i!=0:
                c(i, ind)
    if ind in a2:
        for i in a2[ind]:
            if i!=0:
                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:
#!/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= " " )

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
l=[[1]]+[0]*(n-1)
ans=[0]*n
for j in range(n-1):
  a,b=map(int,input().split())
  l[b-1]=l[a-1]+[b]
for k in range(q):
  p,x=map(int,input().split())
  for t in range(n):
    if p in l[t]:
      ans[t]+=x
print(*ans,sep=" ")

Submission status: Runtime Error

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N, A = map(int, input().split())		# 5 7 2

M = [ [] for _ in range(N+1) ]	#=> [[], [], [], [], [], [], [], []]
for i in range(N-1):
	a, b = map(int, input().split())		# 5 7 2
	M[a].append(b)

P=[0]*(N+1)
for i in range(A):
	a, x = map(int, input().split())		# 5 7 2
	P[a]+=x


M[0]=[1]
B=[0]*(N+1)

def aaa(i):
	L=M[i]
	for l in L:
		B[l]+=P[l]+B[i]
		aaa(l)

aaa(0)

p("M ",M)
p("P ",P)
p("B ",B)


print( *B[1:] )

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
nodes = {str(i): [] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = input().split()
    nodes[a] += [b]

PX = [input().split() for _ in range(Q)]

ptree_map = {}


def gen_subtree_nodes(node):
    res = [int(node)]
    for n in nodes.get(node, []):
        subtree_nodes = gen_subtree_nodes(n)
        ptree_map[n] = subtree_nodes
        res += subtree_nodes

    return res


ptree_map['1'] = gen_subtree_nodes('1')

node_cnts = [0] * (N+1)
for p, x_str in PX:
    x = int(x_str)
    for n in ptree_map[p]:
        node_cnts[n] += x

print(*node_cnts[1:])

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]:
            add(i,x,hen,value)

for i in range(0,Q):
    p,x = (int(i) for i in input().split())
    add(p,x,hen,value)
print(' '.join(map(str,value)))

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, data): #コンストラクタ
        self.data = data 
        self.kodomo = []
        self.cnt = 0
        
def saiki(target,tasu):
  #target = array[]
  target.cnt += tasu
  for ko in target.kodomo:
    if array[ko]:
      saiki(array[ko],tasu)
  
        
n, q = [int(i) for i in input().split()]
array=[]
 
for i in range(n):
  array.append(Node(i+1))
  
  
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  array[a-1].kodomo.append(b-1)

  
for i in range(q):
  x, tasu = [int(i) for i in input().split()]
  if array[x-1]:
    saiki(array[x-1],tasu)
  
for i in range(n):
  if i != n-1:
    print(array[i].cnt, end =" ")
  else:
    print(array[n-1].cnt)