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:
import numpy as np
import heapq

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

links = []

sums = np.zeros(n + 1)

oya = {}

for _ in range(n - 1):
  a, b= map(int, input().split())
  oya[b] = a
  heapq.heappush(links, [a, b])

uppers = np.eye(n + 1)

for l in links:
  oyaId = l[0]
  koId = l[1]
  uppers[oyaId, koId] = 1
  while True: 
    if oyaId in oya:
      uppers[oyaId, koId] = 1
      oyaId = oya[oyaId]
    else:
      uppers[oyaId, koId] = 1
      break
      
for _ in range(m):
  p, x = map(int, input().split())
  sums += x * uppers[p, :]
print(*sums[1:].astype(np.int))

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq

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

links = []

sums = np.zeros(n + 1)

oya = {}

for _ in range(n - 1):
  a, b= map(int, input().split())
  oya[b] = a
  heapq.heappush(links, [a, b])

uppers = np.eye(n + 1)

for l in links:
  oyaId = l[0]
  koId = l[1]

  while True: 
    uppers[oyaId, koId] = 1
    if oyaId != 1:
      oyaId = oya[oyaId]
    else:
      break
      
for _ in range(m):
  p, x = map(int, input().split())
  sums += x * uppers[p, :]
print(*sums[1:].astype(np.int))

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq

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

links = []

sums = np.zeros(n + 1)

oya = {}

for _ in range(n - 1):
  a, b= map(int, input().split())
  oya[b] = a
  heapq.heappush(links, [a, b])

uppers = np.eye(n + 1)

for l in links:
  oyaId = l[0]
  koId = l[1]

  while True: 
    uppers[oyaId, koId] = 1
    if oyaId in oya:
      oyaId = oya[oyaId]
    else:
      break
# print(uppers)
# print(sums)
for _ in range(m):
  p, x = map(int, input().split())
  sums += x * uppers[p, :]
print(*sums[1:].astype(np.int))

Submission status: Runtime Error

Solution code:
def qul(p,v):
    if p in d:
        for j in d[p]:
            if j in d:
                qul(j,v)
            ans[j]+=v

#pre
d={}
n,q=map(int,input().split())
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a]=[b]
w=[0]*(n+1)
ans=[0]*(n+1)
for i in d:
    d[i].sort(reverse=True)
for i in range(q):
    p,x=map(int,input().split())
    w[p]+=x
    ans[p]+=x


#pro
for i in range(1,n):
    if i in d:
        qul(i,w[i])

print(*ans[1:])

Submission status: Runtime Error

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

#def qul(d,l,p):
def qul(p,v):
    if p in d:
        for j in d[p]:
            if j in d:
                qul(j,v)
            ans[j]+=v

#pre
d={}
n,q=map(int,input().split())
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a]=[b]
w=[0]*(n+1)
ans=[0]*(n+1)
for i in d:
    d[i].sort(reverse=True)
for i in range(q):
    p,x=map(int,input().split())
    w[p]+=x
    ans[p]+=x


#pro
for i in range(1,n):
    qul(i,w[i])

print(*ans[1:])

Submission status: Runtime Error

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

import sys


def main():
    n, q = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]

    tree = {}
    data = [0 for x in range(n)]

    for _ in range(n - 1):
        a, b = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
        if a not in tree:
            tree[a] = []
        tree[a].append(b)

    for _ in range(q):
        p, x = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
        data[p - 1] += x

    def add(p, x):
        data[p - 1] += x
        if p not in tree:
            return
        for p2 in tree[p]:
            add(p2, data[p - 1])

    add(1, 0)

    print(" ".join([str(x) for x in data]))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def resolve():
    def dfs(num, p=-1):
        for i in to[num]:
            if p == i:
                continue
            ns[i] += ns[num]
            dfs(i, num)
            
    n, q = map(int, input().split())

    to = [[] for _ in range(n)]

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

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

    dfs(0)
    print(*ns)
resolve()

Submission status: Runtime Error

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

to = [[] for _ in range(n)]
ans = [0 for _ in range(n)]

def dfs(n):
    for x in to[n]:
        ans[x] += ans[n]
        dfs(x)

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

for i in range(q):
    px = map(int,raw_input().split())
    ans[px[0]-1] += px[1]

dfs(0)

for i in ans: print i,

Submission status: Runtime Error

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

to = [[] for _ in range(n)]
ans = [0]*n

def dfs(n,p=-1):
    for x in to[n]:
        if x==p: continue
        ans[x] += ans[n]
        dfs(x,n)

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

for i in range(q):
    px = map(int,raw_input().split())
    ans[px[0]-1] += px[1]

dfs(0)

for i in ans: print i,

Submission status: Runtime Error

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

def qul(d,l,p):
    if p in d:
        for j in d[p]:
            if j in d:
                if j not in l:
                    l.append(j)
                qul(d,l,j)
            else:
                l.append(j)
def sol():
    d={}
    n,q=map(int,input().split())
    for i in range(n-1):
        a,b=map(int,input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a]=[b]
    w=[0]*(n+1)
    for i in d:
        d[i].sort(reverse=True)
    print(0)
    if (True) exit()
    for i in range(q):
        p,x=map(int,input().split())
        w[p]+=x
    for i in range(n,0,-1):
        l=[]
        qul(d,l,i)
        for j in l:
            w[j]+=w[i]
        #print(i,l)
    print(*w[1:])

if __name__=="__main__":
    sol()

Submission status: Runtime Error

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

import sys
from collections import defaultdict


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

tree = defaultdict(list)
data = defaultdict(int)


def add(p, x):
    data[p] += x
    for p2 in tree[p]:
        add(p2, x)


for _ in range(n - 1):
    a, b = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    tree[a].append(b)

for _ in range(q):
    p, x = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    add(p, x)

print(" ".join([str(data[i + 1]) for i in range(n)]))

Submission status: Runtime Error

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

import sys
from collections import defaultdict


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

tree = defaultdict(set)
data = defaultdict(int)


def add(p, x):
    data[p] += x
    for p2 in tree[p]:
        add(p2, x)


for _ in range(n - 1):
    a, b = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    tree[a].add(b)

for _ in range(q):
    p, x = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    add(p, x)

print(" ".join([str(data[i + 1]) for i in range(n)]))

Submission status: Runtime Error

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

sys.setrecursionlimit(10**6)
es = [[] for i in range(N)]

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


point = [0] * N

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

ans = [0] * N
ans[0] = point[0] # 一番上の根なのでこれだけ
visited = [False] * N
visit_cnt = 1
from collections import deque
nexts = deque([0])
while len(nexts) >= 1:
    now = nexts.popleft()
    visited[now] = True

     for next in es[now]:
        if visited[next] == True:
            continue
        nexts.append(next)
        ans[next] = ans[now] + point[next]


print(*ans)

Submission status: Runtime Error

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

import sys
from collections import defaultdict


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

tree = defaultdict(set)
data = {}


def add(p, x):
    global data
    data[p] += x
    for p2 in tree[p]:
        add(p2, x)


for _ in range(n - 1):
    a, b = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    tree[a].add(b)

for k, v in tree.items():
    data[k] = 0
    for v2 in v:
        data[v2] = 0

for _ in range(q):
    p, x = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    add(p, x)

print(" ".join([str(v) for k, v in sorted(data.items(), key=lambda x: x[0])]))

Submission status: Runtime Error

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

import sys
from collections import defaultdict


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

tree = defaultdict(set)
data = {}


def add(p, x):
    global data
    data[p] += x
    for p2 in tree[p]:
        add(p2, x)


for _ in range(n - 1):
    a, b = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    tree[a].add(b)

for k in tree.keys():
    data[k] = 0

for _ in range(q):
    p, x = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    add(p, x)

print(" ".join([str(v) for k, v in sorted(data.items(), key=lambda x: x[0])]))

Submission status: Runtime Error

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

import sys
from collections import defaultdict


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

tree = defaultdict(set)
data = defaultdict(int)


def add(p, x):
    global data
    data[p] += x
    for p2 in tree[p]:
        add(p2, x)


for _ in range(n - 1):
    a, b = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    tree[a].add(b)

for _ in range(q):
    p, x = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    add(p, x)

print(" ".join([str(v) for k, v in sorted(data.items(), key=lambda x: x[0])]))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    N, Q = map(int, input().split())
    link = [[] * N]
    a = [None] * (N-1)
    b = [None] * (N-1)
    for i in range(N-1):
        a[i], b[i] = map(int, input().split())

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

    for i in range(N-1):
        link[a[i]-1].append([b[i]-1, cost[i]])
        link[b[i]-1].append([a[i]-1, cost[i]])

    def dfs(v, c, p):
        for nv in link[v]:
            if nv[0] == p:
                continue
            cost[nv[0]] = c + cost[nv[0]]
            dfs(nv[0], cost[nv[0]], v)
        return

    dfs(0, cost[0], -1)

    print(*cost)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

ab_list = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    ab_list[a-1].append(b-1)
    ab_list[b-1].append(a-1)
    
px_list = [list(map(int,input().split())) for _ in range(Q)]
ans = [0] * N

for q, x in px_list:
    ans[q-1] += x

def add_point(num, root=-1):
    for c in ab_list[num]:
        if root == c:
            continue
        ans[c] += ans[num]
        add_point(c, num)
        
add_point(0, -1)

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

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

for i in range(N-1):
    link[a[i]-1].append([b[i]-1, cost[i]])
    link[b[i]-1].append([a[i]-1, cost[i]])

nums = [0] * N
def dfs(v, c, p):
    for nv in link[v]:
        if nv[0] == p:
            continue
        nums[nv[0]] += c + cost[nv[0]]
        dfs(nv[0], c + cost[nv[0]])
    return

nums[0] = cost[0]
dfs(0, cost[0], -1)

print(*nums)

Submission status: Runtime Error

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

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

value = [0 for i in range(n)]
for p, x in px:
    value[p] += x

s = [0]
flag = [False]*(n)
while s:
    v = s.pop()
    flag[v] = True
    for e in l[v]:
        if flag[e]:
            continue
        value[e] += value[v]
        s.append(e)

print(*value)

Submission status: Runtime Error

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

ab_list = [[] for _ in range(N)]
px_list = [0] * N

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

def add_point(i, root, point):
    point += px_list[i]
    ans[i] = point
    for num in ab_list[i]:
        if num == root:
            continue
        add_point(num, i, point)
        
add_point(0, -1, 0)

print(*ans)

Submission status: Runtime Error

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

T = [[]for i in range(N)]

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

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

# def dfs(x, p):
#     for j in T[x]:
#         if j == p:
#             continue
#         X[j] += X[x]
#         dfs(j, x)
def dfs(nownode,oya=-1):
    for nextnode in T[nownode]:
        if oya == nextnode:
            continue
        X[nextnode] += X[nownode]
        dfs(nextnode,nownode)

dfs(0, -1)

print(*X)

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
ablist = [[] for _ in range(N)]
anslist = [0 for i in range(N)]

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

pxlist = [list(map(int,input().split())) for _ in range(Q)]

for p,x in pxlist:
    anslist[p-1] += x

def dfs(nownode,oya=-1):
    for nextnode in ablist[nownode]:
        if oya == nextnode:
            continue
        anslist[nextnode] += anslist[nownode]
        dfs(nextnode,nownode)
dfs(0,-1)
print(*anslist)

Submission status: Runtime Error

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

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

graph = [[] for _ in range(N+1)]
point_list = [0] * (N+1)

for a, b in ab_list:
    graph[a].append(b)
    graph[b].append(a)
    
for p, x in px_list:
    point_list[p] += x
    
def add_point(num, root, point):
    point_list[num] += point
    for i in graph[num]:
        if i == root:
            continue
        add_point(i, num, point_list[num])

add_point(1, 0, 0)
 
print(*(point_list[1:]))

Submission status: Runtime Error

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

stack = [[] for _ in range(n+1)]
stack[0].append(1)
for i in range(n-1):
	stack[AB[i][0]].append(AB[i][1])

ans = [0] * n
def dfs(cur, num):
	ans[cur-1] += num
	if len(stack[cur]) <= 0:
		return
	for c in stack[cur]:
		dfs(c, num)

for px in PX:
	dfs(px[0], px[1])

print(*ans)

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))
for i in range(N):
  matrix[i, i]=1
  
for i in range(N-1):
  temp=list(map(int, input().split()))
  matrix[temp[0]-1, temp[1]-1]=1
  
counter=np.zeros(N)
for i in range(Q):
  temp=list(map(int, input().split()))
  counter[temp[0]-1]+=temp[1]
  
for i in range(N):
  counter[i]=np.dot(counter, matrix[:, i])
  
print(' '.join(map(str, map(int, counter.tolist()))))

Submission status: Runtime Error

Solution code:
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define print(n) cout<<n<<endl
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ALL(s) s.begin(),s.end()
#define P pair<ll,ll>
#define vl vector<ll>
#define vi vector<int>
#define vvl vector<vector<ll>>
#define vvi vector<vector<int>>
const int M=100111;
const int inf=1000000007;
const long long INF=1e18;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int ddx[8]={1,-1,0,0,1,-1,-1,1},ddy[8]={0,0,1,-1,1,-1,1,-1};

/*
vvl comb(int n, int r) {
	vvl v(n + 1,vl(n + 1, 0));
	for (int i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (int j = 1; j < v.size(); j++) {
		for (int k = 1; k < j; k++) {
			v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
		}
	}
	return v;
}
*/

vi v[M];
int n,q,a,b,p,x,c[M]={};
void dfs(int now,int pre){
	c[now]+=c[pre];
	for(int next:v[now])if(next!=pre){
		dfs(next,now);
	}
}

int main() {
	cin>>n>>q;
	rep(i,0,n-1){
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	rep(i,0,q)cin>>p>>x,c[p]+=x;
	dfs(1,0);
	rep(i,1,n+1){
		cout<<c[i];
		if(i!=n)cout<<" ";
	}
}

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)

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

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

def rec(node, parent):
    for i in root[node]:
        if i == parent:
            continue
        cnt[i] += cnt[node]
        rec(i, node)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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

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

def rec(node, parent):
    for i in root[node]:
        if i == parent:
            continue
        cnt[i] += cnt[node]
        rec(i, node)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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

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

def rec(node, parent):
    for i in root[node]:
        if i == parent:
            continue
        cnt[node] += cnt[parent]
        rec(i, node)

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

Submission status: Runtime Error

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

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

root = {}
for i in range(n-1):
    a, b = map(int, input().split())
    root.setdefault(a, []).append(b)
    root.setdefault(b, []).append(a)
    
cnt = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x

check = []
def rec(node, checked):
    for k in root[node]:
        if not k in checked:
            cnt[k] += cnt[node]
            if not node in checked:
                checked.append(node)
            rec(k, checked)

rec(1, check)
print(" ".join(map(str, cnt[1:])))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(500000)
 
N,Q = map(int, input().split())
tree = np.eye(N, dtype=int)
AB_list = []
for _ in range(N-1):

    a,b = map(int, input().split())
    a -= 1
    b -= 1
    AB_list.append((a,b))
AB_list.sort(key=lambda x:x[0])
 
for a, b in AB_list:
    for i in range(N):
        if tree[i][a] == 1:
            tree[i][b] = 1
 
result = np.zeros(N, dtype=int)
for _ in range(Q):
    p,x = map(int, input().split())
    p -= 1
    add_nums = tree[p]
    add_nums[add_nums > 0] = x
    result =  np.add(result, add_nums)
result = " ".join(map(str, result))
print(result)

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
sons = {1:[]}
edges = {}
for _ in range(N-1):
    a,b = map(int,input().split())
    if a==1:
    	sons[a] += [b]
    else:
        if a in edges.keys():
            edges[a] = edges[a]+[b]
        else:
            edges[a] = [b]
            
        if b in edges.keys():
            edges[b] = edges[a]+[b]
        else:
            edges[b] = [a]

counts = [0]*(N+1)
for _ in range(Q):
    p,x = map(int,input().split())
    counts[p] += x
        
stack = sons[1]
count_stack = [counts[1]]
ignores = set([])
results = [0]*(N+1)
results[1] = counts[1]
next_stack = []
next_cstack = []
while stack != []:
    next_stack = []
    next_cstack = []
    for x,c in zip(stack,count_stack):
        results[x] = counts[x]+c
        sons[x] = set(edges[x])-ignores
        next_stack += sons[x]
        next_cstack += [results[x]]*len(sons[x])
        ignores = ignores | set([x])
    stack = next_stack
    count_stack = next_cstack
print(' '.join([str(results[i]) for i in range(1,N+1)]))

Submission status: Runtime Error

Solution code:

import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

class Graph:
    def __init__(self, node_count, edge_count):
        self.node_count = node_count
        self.lst = [-1 for _ in range(node_count)]
        self.nxt = [0 for _ in range(edge_count)]
        self.to = [0 for _ in range(edge_count)]
        self.m = 0

    def add_edge(self, u, v, w):  # bidirection weight
        m = self.m
        self.nxt[m], self.lst[u], self.to[m] = self.lst[u], m, (v, w)
        self.m += 1

    def traverse(self, u):
        m = self.lst[u]
        while m != -1:
            yield self.to[m]
            m = self.nxt[m]


n,q=getints()
values = [0]*n
gr = Graph(n,2*n)

for _ in range(n-1):
    a,b=getints()
    a,b=a-1,b-1
    gr.add_edge(a,b,1)
    gr.add_edge(b,a,1)

for _ in range(q):
    u, p=getints()
    values[u-1] += p

def distribute(u, par, prev):
    values[u] += prev
    for v, _ in gr.traverse(u):
        if v == par: continue
        distribute(v, u, values[u])

distribute(0, -1, 0)
print(" ".join(map(str, values)))

Submission status: Runtime Error

Solution code:
# 解説動画から累積和ポイント。 
N,Q = map(int,input().split())
ABList = [list(map(int,list(input().split()))) for i in range(N-1)]  
PXList = [list(map(int,list(input().split()))) for i in range(Q)]  
 
# N+1 にしているのは、dfs関数でparentsを使う時に合わせるため 
graph=[[] for _ in range(N+1)]
values=[0]*(N+1)
 
for a,b in ABList:
    graph[a].append(b)
    graph[b].append(a)
    # aとbを入れ替えて
    # graphは例１の時、[[], [2], [1, 3, 4], [2], [2]] になる
    # 頂点がどことつながっているか 
for p,x in PXList:
    values[p]+=x
    # p をキーにしているのでNの昇順ｘにしている
    # 例１であれば[0, 100, 10, 1, 0]　累積和する前の値をもつ
 
def dfs(x,parent,add):
    # 累積和をvaluesに計算していく
    values[x]+=add
    for i in graph[x]:
        # continueはループの残りを飛ばして次の反復へ
        # 親と子判定
        if i==parent:
            continue
        dfs(i,x,values[x])
 
dfs(1,0,0)
 
print(' '.join(map(str,values[1:])))
# 難しい。graph[x]の使い方の理解がまだまだ

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
sons = {1:[]}
edges = {}
for _ in range(N-1):
    a,b = map(int,input().split())
    if a==1:
    	sons[a] += [b]
    else:
      	edges[a] = edges[a]+[b] if b in edges.keys() else [b]
        edgese[b] = edges[b]+[a] if a in edges.keys() else [a]

counts = [0]*(N+1)
for _ in range(Q):
    p,x = map(int,input().split())
    counts[p] += x
        
stack = sons[1]
count_stack = [counts[1]]
ignores = set([])
results = [0]*(N+1)
results[1] = counts[1]
while stack != []:
  	next_stack = []
    next_cstack = []
	for x,c in zip(stack,count_stack):
      	results[x] = counts[x]+c
  		sons[x] = set(edges[x])-ignores
    	next_stack += sons[x]
        next_cstack += [results[x]]*len(sons[x])
        ignores = ignores | set([x])
        print(results[i], end=' ')
    stack = next_stack
    count_stack = next_cstack

Submission status: Runtime Error

Solution code:
def addc(p,ko,c,total):
  c[p] += total
  total = c[p]
  if(len(ko[p]) == 0):
    return 0

  else:
    for i in ko[p]:
      addc(i,ko,c,total)

  return 0

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

ko = [ [] for i in range(n + 1)]
c = [0 for i in range(n + 1)]

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

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

_ = addc(1,ko,c,0)

c.pop(0)

print(*c)

Submission status: Runtime Error

Solution code:
def addc(p,ko,c,total):
  c[p] += total
  total = c[p]
  if(len(ko[p]) == 0):
    return 0

  else:
    for i in ko[p]:
      addc(i,ko,c,total)

  return 0

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

ko = [ [] for i in range(n + 1)] # 各頂点に紐づく子
c = [0 for i in range(n + 1)] # 各頂点のCの値

for i in range(n-1):
  a,b = map(int,input().split())
  ko[a].append(b) # 親a -> 子bに向かう辺がある

for i in range(q):
  p,x = map(int,input().split())
  c[p] += x # 操作により指定されている頂点にxを加える

_ = addc(1,ko,c,0)

c.pop(0)

print(*c)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

N,Q = map(int,input().split())
edge = [[] for x in range(N)]
nodes = [0 for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
for i in range(Q):
    p,x = map(int,input().split())
    nodes[p-1]+=x

def rec(parent):
    if len(edge[parent])>0: 
        for x in edge[parent]:
            nodes[x]+=nodes[parent]
            rec(x)

rec(0)
print(*nodes)

Submission status: Runtime Error

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

def rec(parent):
    if len(edge[parent])>0: 
        for x in edge[parent]:
            nodes[x]+=nodes[parent]
            rec(x)

rec(0)
print(*nodes)

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
adj = [[] for i in range(N+1)]
nodes = [0 for i in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    adj[a].append(b)
for i in range(Q):
    p,x = map(int,input().split())
    nodes[p]+=x

def rec(parent):
    for x in adj[parent]:
    	nodes[x]+=nodes[parent]
    	rec(x)

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

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(500000)

N,Q = map(int, input().split())
tree = np.eye(N, dtype=int)
AB_list = []
for _ in range(N-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    AB_list.append((a,b))
AB_list.sort(key=lambda x:x[0])

for a, b in AB_list:
    for i in range(N):
        if tree[i][a] == 1:
            tree[i][b] = 1

result = np.zeros(N, dtype=int)
for _ in range(Q):
    p,x = map(int, input().split())
    p -= 1
    result += tree[p] * x
result = " ".join(map(str, result))
print(result)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(500000)

N,Q = map(int, input().split())
tree = np.eye(N, dtype=int)
branch = np.zeros((N, N), dtype=int)
for _ in range(N-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    branch[a][b] = 1

break_num = 0
while True:
    tree = tree + np.dot(tree, branch)
    break_check = np.count_nonzero(tree)
    if break_check == break_num:
        tree[tree > 0] = 1
        break
    else:
        break_num = break_check

result = np.zeros(N, dtype=int)
for _ in range(Q):
    try:
        p,x = map(int, input().split())
    except EOFError:
        pass
    p -= 1
    result += tree[p] * x
result = " ".join(map(str, result))
print(result)

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
adj = [[] for x in range(N+1)]
nodes = [0 for i in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    adj[a].append(b)
for i in range(Q):
    p,x = map(int,input().split())
    nodes[p]+=x

def rec(parent):
    if adj[parent]: 
        for x in adj[parent]:
            nodes[x]+=nodes[parent]
            rec(x)

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

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
edge = [list(map(int, input().split())) for i in range (n-1)]
a = []
b = []
for i in range(n-1):
    a.append(edge[i][0])
    b.append(edge[i][1])
ope = [list(map(int, input().split())) for j in range(q)]
c = [0] * n
for j in range(q):
    m = ope[j][0]
    c[m-1] += ope[j][1]
for bi in range(2, n+1):
    i = b.index(bi)
    k = a[i] - 1
    c[bi-1] += c[k]
for x in range(n):
    c[x] = str(c[x])
print(' '.join(c))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


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

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


def down_tree(index, parent):
    global score
    score[index] += score[parent] + q[index]
    for i in to[index]:
        if i == parent:
            continue
        down_tree(i, index)
    return


down_tree(1, 1)

print(*score[1:])