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: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return

#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return

#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return

#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return

#E
def E():
    s = input()
    t = input()

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return

#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return

#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return

#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
                d[y] = 1
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

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

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n, q = getList()

vtxs = [[] for i in range(n)]
already = [0 for i in range(n)]

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

count = [0 for i in range(n)]
for i in range(q):
    x, v = getList()
    count[x-1] += v

ans = [0 for i in range(n)]

def rep(vx, val):
    # print(vx,val)
    tgt = vtxs[vx]
    already[vx] = 1
    for tg in tgt:
        if already[tg] == 0:
            app = count[tg]
            ans[tg] = val+app
            rep(tg, val+app)

rep(0, count[0])
# print(vtxs)
ans[0] = count[0]
print(*ans)

Submission status: Accepted

Solution code:
# for change the recursion limit
import sys
sys.setrecursionlimit(10 ** 6)

# to enable variable use in global
global tree, point

# v : current node, f : parent node 
def dfs(v, f):
    for next_v in tree[v]:
        # parents node is already visited
        if next_v == f:
            continue
    
        point[next_v] += point[v]
        dfs(next_v, v)

n , q = map(int, input().split())
# initalize gloabal variables
tree = [[] for _ in range(n)]
point = [0] * n

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

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

dfs(0, 0)
print(*point)

Submission status: Accepted

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

# to enable variable use in global
global tree, point

# v : current node, f : parent node 
def dfs(v, f):
    global tree, point
    for next_v in tree[v]:
        if next_v == f:
            continue
    
        point[next_v] += point[v]
        dfs(next_v, v)

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

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

dfs(0, 0)
print(*point)

Submission status: Accepted

Solution code:
from collections import deque


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

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

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

is_read = [False] * (N + 1)
d = deque()
d.append(1)

while len(d) != 0:
    now = d.popleft()
    is_read[now] = True
    for c in t[now]:
        if is_read[c]:
            continue
        score[c] += score[now]
        d.append(c)
print(" ".join(map(str, score[1:])))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

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


done = [False]*n
points = [0]*n
d = defaultdict(lambda: 0)

for _ in range(q):
    a, b = list(map(int, input().split()))
    d[a-1] += b


def dfs(i, cnt):
    cnt += d[i]
    points[i] += cnt
    done[i] = True
    for j in G[i]:
        if not done[j]:
            dfs(j, cnt)


dfs(0, 0)
print(*points)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(s):
    stack = [s]
    visited = [False]*N
    while stack:
        v = stack.pop()
        if visited[v]:
            continue
        visited[v] = True
        for u in graph[v]:
            if not visited[u]:
                point[u] += point[v]
                stack.append(u)

N, Q = list(map(int,input().split()))
graph = [deque([]) for _ in range(N)]
point = [0]*N

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

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

dfs(0)
print(*point)

Submission status: Accepted

Solution code:
#
# abc138 d
#
import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(input, output)


def resolve():
    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)]

    G = [[i+1, 0] for i in range(N)]
    for ab in AB:
        a, b = ab
        G[a-1][1] += 1
        G[b-1][1] += 1
        G[a-1].append(b)
        G[b-1].append(a)

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

    S = deque()

    F = [False] * N
    S.append(1)
    F[0] = True

    while S:
        p = S.pop()
        if G[p-1][1] == 0:
            continue

        for np in G[p-1][2:]:
            if F[np-1]:
                continue
            S.append(np)
            F[np-1] = True
            ans[np-1] += ans[p-1]

    print(*ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
f = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    f[a-1].append(b-1)
    f[b-1].append(a-1)
ans = [0] * N
for i in range(Q):
    p,x = map(int,input().split())
    ans[p-1] += x
from collections import deque
d = deque()
d.append(0)
root = [-1]*N
root[0] = 0
while len(d) > 0:
    z = d.popleft()
    for i in f[z]:
        if root[i] == -1:
            root[i] = z
            ans[i] += ans[z]
            d.append(i)
print(*ans)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b)
    g[b-1].append(a)
x=[0]*n
for i in range(q):
    p,X=map(int,input().split())
    x[p-1]+=X
from collections import deque
d=deque()
d.append(0)
y=[0]*n
while len(d)>=1:
    s=d.popleft()
    y[s]+=1
    for i in g[s]:
        if y[i-1]!=1:
            d.append(i-1)
            x[i-1]+=x[s]
print(*x)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
tree=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a) # 無向グラフなので
ans=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x

stack=deque([0]) # 根の位置、現位置の元になる根
visited=[0]*n
visited[0]=1

while stack:
    cur=stack.pop()
    for i in tree[cur]:
        if visited[i]==0:
            visited[i]=1
            ans[i]+=ans[cur]
            stack.append(i)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
tree=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a) # 無向グラフなので
ans=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x

stack=deque([[0,-1]]) # 根の位置、現位置の元になる根
visited=[0]*n
visited[0]=1

while stack:
    cur,rot=stack.pop()
    for i in tree[cur]:
        if visited[i]==0 and i!=rot:
            visited[i]=1
            ans[i]+=ans[cur]
            stack.append([i,cur])
print(*ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = mapint()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
late = [0]*N

for _ in range(Q):
    v, p = mapint()
    late[v-1] += p

ans = [0]*N
checked = [0]*N
from collections import deque
Q = deque([(0, 0)])

while Q:
    v, plus = Q.pop()
    plus += late[v]
    checked[v] = 1
    ans[v] = plus
    for nx in tree[v]:
        if not checked[nx]:
            Q.append((nx, plus))

print(*ans)

Submission status: Accepted

Solution code:
import sys

if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    def write_script(sp):
        if os.path.dirname(sp[1]):
            os.makedirs(os.path.dirname(sp[1]), exist_ok=True)
        with open(sp[1], 'w') as f_write:
            line = f.readline()
            while line:
                if line.startswith("'''"):
                    return
                if line.startswith("###nbacl"):
                    sp = line.split()
                    break
                f_write.write(line)
                line = f.readline()
        write_script(sp)


    with open(__file__) as f:
        line = f.readline()
        while line:
            if line.startswith('###nbacl'):
                sp = line.split()
                write_script(sp)
                break
            line = f.readline()

    import nbmodule
    nbmodule.cc.compile()
    exit(0)


from nbmodule import solve
import numpy as np
i4 = np.int32


def main():
    f = open(0)
    N, Q = [int(x) for x in f.readline().split()]
    ap = np.fromstring(f.read(), i4, sep=' ').reshape((-1, 2))
    a = ap[:N - 1] - 1
    a = np.concatenate((a, a[:, ::-1]))
    p = ap[N - 1:]
    val = solve(a, p, N)
    print(*val.tolist())


if __name__ == '__main__':
    main()

'''
###nbacl nbacl/graphs/adjacency_list.py
import numpy as np
from numba import njit
from collections import namedtuple

AdjacencyList = namedtuple('AdjacencyList', ['v', 'adj'])

@njit
def adjacency_list(n, a):
    """
    隣接リストの作成
    :param n: vertex の数
    :param a: 2d の ndarray, 各行は、[u, v] u: Edge の始点、v: Edge の終点
    :return: AdjacencyList
    """
    v = np.zeros(n + 1, np.int32)
    for i in range(a.shape[0]):
        v[a[i, 0] + 1] += 1
    for i in range(1, v.shape[0]):
        v[i] += v[i - 1]
    adj = np.empty(a.shape[0], np.int32)
    temp = np.zeros(n, np.int32)
    for i in range(a.shape[0]):
        from_ = a[i, 0]
        adj[v[from_] + temp[from_]] = a[i, 1]
        temp[from_] += 1
    return AdjacencyList(v, adj)


@njit
def at(gc, n):
    return gc.adj[gc.v[n]:gc.v[n + 1]]


@njit
def iter(gc, n):
    for i in range(gc.v[n], gc.v[n + 1]):
        yield gc.adj[i]        

###nbacl nbmodule.py
import numpy as np
import nbacl.graphs.adjacency_list as tree
from numba import njit
from numba.types import Array, int32
from numba.pycc import CC
i4 = np.int32
cc = CC('nbmodule')


@njit
def dfs(d, prev, tr, u, val):
    y = val[d]
    for x in tree.iter(tr, d):
        if x == prev:
            continue
        val[x] = y + u[x]
        dfs(x, d, tr, u, val)


@cc.export('solve', (Array(int32, 2, 'C'), Array(int32, 2, 'C'), int32))
def solve(a, p, N):
    tr = tree.adjacency_list(N, a)
    u = np.zeros(N, i4)
    val = np.zeros(N, i4)
    for i in range(p.shape[0]):
        u[p[i, 0] - 1] += p[i, 1]
    val[0] = u[0]
    dfs(int32(0), int32(-1), tr, u, val)
    return val

'''

Submission status: Accepted

Solution code:
from collections import defaultdict

N, Q = map(int, input().split())
d = defaultdict(list)

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

c = defaultdict(int)

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

ans = [0 for i in range(N)]
que = [(1, 0, -1)]
while len(que) > 0:
    tmp = []
    for v, x, par in que:
        x += c[v]
        ans[v - 1] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w, x, v))
    que = tmp

print(*ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n, q = map(int, input().split())
edges=[[] for i in range(1+n)]
for i in range(n-1):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    edges[_].append(__)
    edges[__].append(_)
    """
"""#weighted->erase
cnt=[0]*(1+n)
for i in range(q):
    x,p=map(int,input().split())
    cnt[x]+=p
def f(now,pars_value,par):
    cnt[now]+=pars_value
    a=cnt[now]
    for i in edges[now]:
        if i!=par:f(i,a,now)
f(1,0,-1)
print(*cnt[1:])

Submission status: Accepted

Solution code:
from collections import deque


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

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

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

    q = deque()
    q.append(0)
    visited = [False] * n
    visited[0] = True

    while q:
        u = q.pop()
        for v in adj[u]:
            if visited[v]:
                continue
            ans[v] += ans[u]
            q.append(v)
            visited[v] = True

    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC138 D 
import sys
sys.setrecursionlimit(3*10**5)

res=0
INF=10**9
from collections import deque

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

def bfs(a):
    q=deque()
    q.append(a)
    d=[INF]*(N+1)
    d[a]=0
    res=0
    while q:
        r=q.popleft()
        for nr in G[r]:
            if d[nr]==INF:
                q.append(nr)
                d[nr]=d[r]+1
                res+=1
    return d

d=bfs(1)

late=[0]*(N+1)
for _ in [0]*Q:
    p,x=f()
    late[p]+=x
    


S=[0]*(N+1)
q=deque()
q.append((1,0))
while q:
    node,par=q.popleft()
    S[node]+=late[node]
    for p in G[node]:
        if p==par:
            continue
        late[p]+=late[node]
        q.append((p,node))
        
print(*S[1:],sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())
routings = [[] for _ in range(N+1)]

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

points = [0 for _ in range(N+1)]
scores = [0 for _ in range(N+1)]

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

visited = [False for _ in range(N+1)]
  
edges = deque([1])
scores[1] = points[1]
visited[1] = True

while len(edges) > 0: 
  e = edges.pop()
  for c in routings[e]:
    if not visited[c]:
      scores[c] += scores[e] + points[c]
      visited[c] = True
      edges.append(c)
print(' '.join(map(str, scores[1:])))

Submission status: Accepted

Solution code:
import sys
from typing import List, Tuple
import collections

Graph = List[List[int]]


def main():
    def input(): return sys.stdin.readline()[:-1]
    N, Q = map(int, input().split())

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

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

    queue = collections.deque()
    queue.append(1)
    checked = [0] * (N + 1)
    while queue:
        v = queue.pop()
        checked[v] = 1
        for next_v in graph[v]:
            if checked[next_v] == 1: continue
            px[next_v] += px[v]
            queue.append(next_v)
    print(*px[1:])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)# 各頂点ごとに所属する木の大きさを計算する
N,Q = map(int,input().split())

E = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]
Node_len = [1 for _ in range(N+1)]

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

AS = [0 for i in range(N+1)]
def dfs(node,parent=-1):
    for child in E[node]:
        if child == parent:
            continue
        AS[child] += AS[node]
        dfs(child,node)

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

dfs(1)
print(*AS[1:])

Submission status: Accepted

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

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        point[u] += point[v]
        dfs(u,v)

N, Q = list(map(int,input().split()))
graph = [[] for _ in range(N)]
point = [0]*N

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

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

dfs(0)
print(*point)

Submission status: Accepted

Solution code:
import numpy as np
import sys
i4 = np.int32

if sys.argv[-1] == 'ONLINE_JUDGE':
    adjacency_list = '''
import numpy as np
from numba import njit
from collections import namedtuple

AdjacencyList = namedtuple('AdjacencyList', ['v', 'adj'])

@njit
def adjacency_list(n, a):
    """
    隣接リストの作成
    :param n: vertex の数
    :param a: 2d の ndarray, 各行は、[u, v] u: Edge の始点、v: Edge の終点
    :return: AdjacencyList
    """
    v = np.zeros(n + 1, np.int32)
    for i in range(a.shape[0]):
        v[a[i, 0] + 1] += 1
    for i in range(1, v.shape[0]):
        v[i] += v[i - 1]
    adj = np.empty(a.shape[0], np.int32)
    temp = np.zeros(n, np.int32)
    for i in range(a.shape[0]):
        from_ = a[i, 0]
        adj[v[from_] + temp[from_]] = a[i, 1]
        temp[from_] += 1
    return AdjacencyList(v, adj)


@njit
def at(gc, n):
    return gc.adj[gc.v[n]:gc.v[n + 1]]


@njit
def iter(gc, n):
    for i in range(gc.v[n], gc.v[n + 1]):
        yield gc.adj[i]        
    '''
    import os
    os.makedirs('nbacl/graphs', exist_ok=True)
    with open('nbacl/graphs/adjacency_list.py', 'w') as f:
        f.write(adjacency_list)

    abc138_d_numba = '''
import numpy as np
import nbacl.graphs.adjacency_list as tree
from numba import njit
from numba.types import Array, int32
from numba.pycc import CC
i4 = np.int32
cc = CC('abc138_d_numba')


@njit
def dfs(d, prev, v, adj, u, val):
    y = val[d]
    for i in range(v[d], v[d + 1]):
        x = adj[i]
        if x == prev:
            continue
        val[x] = y + u[x]
        dfs(x, d, v, adj, u, val)


@cc.export('solve', (Array(int32, 2, 'C'), Array(int32, 2, 'C'), int32))
def solve(a, p, N):
    tr = tree.adjacency_list(N, a)
    u = np.zeros(N, i4)
    val = np.zeros(N, i4)
    for i in range(p.shape[0]):
        u[p[i, 0] - 1] += p[i, 1]
    val[0] = u[0]
    dfs(int32(0), int32(-1), tr.v, tr.adj, u, val)
    return val


if __name__ == '__main__':
    cc.compile()
    '''
    with open('abc138_d_numba.py', 'w') as f:
        f.write(abc138_d_numba)
    import subprocess
    cmd = "python3.8 abc138_d_numba.py"
    subprocess.run(cmd.split())
    exit(0)


from abc138_d_numba import solve

def main():
    f = open(0)
    N, Q = [int(x) for x in f.readline().split()]
    ap = np.fromstring(f.read(), i4, sep=' ').reshape((-1, 2))
    a = ap[:N - 1] - 1
    a = np.concatenate((a, a[:, ::-1]))
    p = ap[N - 1:]
    val = solve(a, p, N)
    print(*val.tolist())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
i4 = np.int32

if sys.argv[-1] == 'ONLINE_JUDGE':
    adjacency_list = '''
import numpy as np
from numba import njit
from collections import namedtuple

AdjacencyList = namedtuple('AdjacencyList', ['v', 'adj'])

@njit
def adjacency_list(n, a):
    """
    隣接リストの作成
    :param n: vertex の数
    :param a: 2d の ndarray, 各行は、[u, v] u: Edge の始点、v: Edge の終点
    :return: AdjacencyList
    """
    v = np.zeros(n + 1, np.int32)
    for i in range(a.shape[0]):
        v[a[i, 0] + 1] += 1
    for i in range(1, v.shape[0]):
        v[i] += v[i - 1]
    adj = np.empty(a.shape[0], np.int32)
    temp = np.zeros(n, np.int32)
    for i in range(a.shape[0]):
        from_ = a[i, 0]
        adj[v[from_] + temp[from_]] = a[i, 1]
        temp[from_] += 1
    return AdjacencyList(v, adj)


@njit
def at(gc, n):
    return gc.adj[gc.v[n]:gc.v[n + 1]]


@njit
def iter(gc, n):
    for i in range(gc.v[n], gc.v[n + 1]):
        yield gc.adj[i]        
    '''
    import os
    os.makedirs('nbacl/graphs', exist_ok=True)
    with open('nbacl/graphs/adjacency_list.py', 'w') as f:
        f.write(adjacency_list)

    abc138_d_numba = '''
import numpy as np
import nbacl.graphs.adjacency_list as tree
from numba import njit
from numba.types import Array, int32
from numba.pycc import CC
i4 = np.int32
cc = CC('abc138_d_numba')


@njit((int32, int32, Array(int32, 1, 'C'), Array(int32, 1, 'C'), Array(int32, 1, 'C'), Array(int32, 1, 'C')))
def dfs(d, prev, v, adj, u, val):
    y = val[d]
    for i in range(v[d], v[d + 1]):
        x = adj[i]
        if x == prev:
            continue
        val[x] = y + u[x]
        dfs(x, d, v, adj, u, val)


@cc.export('solve', (Array(int32, 2, 'C'), Array(int32, 2, 'C'), int32))
def solve(a, p, N):
    tr = tree.adjacency_list(N, a)
    u = np.zeros(N, i4)
    val = np.zeros(N, i4)
    for i in range(p.shape[0]):
        u[p[i, 0] - 1] += p[i, 1]
    val[0] = u[0]
    dfs(0, -1, tr.v, tr.adj, u, val)
    return val


if __name__ == '__main__':
    cc.compile()
    '''
    with open('abc138_d_numba.py', 'w') as f:
        f.write(abc138_d_numba)
    import subprocess
    cmd = "python3.8 abc138_d_numba.py"
    subprocess.run(cmd.split())
    exit(0)


from abc138_d_numba import solve

def main():
    f = open(0)
    N, Q = [int(x) for x in f.readline().split()]
    ap = np.fromstring(f.read(), i4, sep=' ').reshape((-1, 2))
    a = ap[:N - 1] - 1
    a = np.concatenate((a, a[:, ::-1]))
    p = ap[N - 1:]
    val = solve(a, p, N)
    print(*val.tolist())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, q = read_ints()
    tree = [[] for _ in range(n)]
    c = [0] * n
    for _ in range(n-1):
        a, b = read_ints()
        tree[~-a].append(~-b)
        tree[~-b].append(~-a)
    for _ in range(q):
        p, x = read_ints()
        c[~-p] += x
    que = deque([0])
    seen = [False] * n
    while que:
        p = que.pop()
        seen[p] = True
        for x in tree[p]:
            if seen[x]: continue
            que.append(x)
            c[x] += c[p]
    
    print(*c)

if __name__ == '__main__':
    Main()

Submission status: Accepted

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

n,q=map(int,input().split())
ans=[0 for _ in range(n)]
gra=[[] for _ in range(n)]
visited=[0 for _ in range(n)]

for _ in range(n-1):
  a,b=map(int,input().split())
  gra[a-1].append(b-1)
  gra[b-1].append(a-1)
  
for _ in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
  
def dfs(st):
  temp=gra[st]
  for i in temp:
    if visited[i]==0:
      visited[i]+=1
      ans[i]+=ans[st]
      dfs(i)
      
visited[0]+=1
dfs(0)

for h in range(n):
  ans[h]=str(ans[h])
  
print(' '.join(ans))

Submission status: Accepted

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


def dfs(_v, _u):
  for u in v[_v]:
    if u==_u: continue;
    ans[u]+=ans[_v]
    dfs(u, _v)
        
  
def main():
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1, input().split())
    v[a].append(b)
    v[b].append(a)
  
  for i in range(q):
    p,x=map(lambda x:int(x)-1, input().split())
    ans[p]+=x+1
  
  dfs(0,-1)
  
  print(*ans, sep=' ')
  
if __name__=='__main__':
  n,q=map(int,input().split())
  ans=[0]*n
  v=[[]*n for i in range(n)]
  main()

Submission status: Accepted

Solution code:
from collections import deque


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

  root=[0]*n
  edge=[[]*n for i in range(n)]
  root[0]=0
  q=deque([0])
  visited=[False]*n
  visited[0]=True
  
  while q:
    r=q.popleft()
    for e in node[r]:
      if not visited[e]:
        visited[e]=True
        q.append(e)
        root[e]=r
        edge[r].append(e)
  
  
  p=[0]*n
  q=deque(edge[0])
  visited=[False]*n
  while q:
    e=q.popleft()
    p[e]=p[root[e]]+1
    for e2 in edge[e]:
      if not visited[e2]:
        visited[e2]=True
        q.append(e2)
  
  p=sorted(enumerate(p), key=lambda x:x[1])
  for i in range(1,n):
    e=p[i][0]
    r=root[e]
    ans[e]+=ans[r]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()