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

Solution code:
def main():
    from collections import defaultdict
    from collections import deque
    import sys
    input = sys.stdin.readline
    dd = defaultdict(list)
    pq = defaultdict(int)

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

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

    for _ in range(Q):
        p,q = map(int, input().split())
        pq[p] += q
    
    answer = [0]*N
    queue = deque()
    queue.append(1)

    while queue != deque():
        tmp = queue.popleft()
        answer[tmp-1] += pq[tmp]
        for i in dd[tmp]:
            queue.append(i)
            answer[i-1] += answer[tmp-1]
            
    print(*answer)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


input = raw_input
N, Q = list(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)]


class Tree():
    def __init__(self, v):
        self.parent = None
        self.v = v
        self.x = 0
        self.memo = None

    def add(self, x):
        self.x += x

    def calc(self):
        if self.v == 1:
            return self.x
        if self.memo is not None:
            return self.memo

        tmp = self.parent.calc()
        self.memo = tmp + self.x
        return self.memo



trees = {i: Tree(i) for i in range(1, N + 1)}

for a,b in ab:
    trees[b].parent = trees[a]

for p,x in px:
    trees[p].add(x)


print(" ".join(map(str,[trees[i].calc() for i in range(1,N+1)])))

Submission status: Accepted

Solution code:
from collections import deque

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

L = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L[u].append(v)
    L[v].append(u)

par = [-1]*N

cnt = [0]*N

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

q = deque([0])
while len(q) :
    u = q.popleft()
    for v in L[u] :
        if v == par[u] :
            continue
        par[v] = u
        cnt[v] += cnt[u]
        q.append(v)


"""
for i in range(Q) :
    p,x = map(int,input().split())
    p -= 1
    q = deque([p])
    while len(q) :
        u = q.popleft()
        cnt[u] += x
        for v in L[u] :
            if v != par[u] :
                q.append(v)
"""
print(*cnt)

Submission status: Accepted

Solution code:
import collections
n, q = map(int, input().split())
d = collections.defaultdict(list)
score = [0 for i in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    d[a].append(b)
for _ in range(q):
    p, x = map(int, input().split())
    score[p-1] += x
for node in range(1, n+1):
    child = d[node]
    for c in child:
        score[c-1] += score[node-1]
print(" ".join(map(str, score)))

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
L=[[]for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    
S=[0 for i in range(N+1)]
for i in range(Q):
    p,x=map(int,input().split())
    S[p]+=x
    
ANS=[-1 for i in range(N+1)]
ANS[1]=S[1]
l=[]
for i in L[1]:
    l.append([i,1,S[1]])
    
for i in range(N-1):
    X=l[i][0]
    Y=l[i][1]
    Z=l[i][2]
    ANS[X]=Z+S[X]
    for j in L[X]:
        if ANS[j]<0:
            l.append([j,X,ANS[X]])
print(*ANS[1:])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
px=[0 for i in range(n+1)]
for i in range(q):
    p,x=map(int,input().split())
    px[p]+=x
s=[1]
c=[1]*(n+1)
c[1]=0
while s:
    t=s.pop()
    for i in edge[t]:
        if c[i]:
            c[i]=0
            px[i]+=px[t]
            s.append(i)
print(" ".join(map(str,px[1:])))

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
PX = [list(map(int,input().split())) for _ in [0]*Q]

E = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)

P = [-1]*N
P[0] = 0
q = [0]
while q:
    i = q.pop()
    for j in E[i]:
        if P[j]!=-1: continue
        P[j] = i
        q.append(j)
P[0] = -1

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

q = [0]
done = [False]*N
while q:
    i = q.pop()
    done[i] = True
    for j in E[i]:
        if done[j] : continue
        V[j] += V[i]
        q.append(j)

print(*V)

Submission status: Accepted

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


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

q = [0]
while q:
    p = q.pop()
    for c in g[p]:
        ans[c] += ans[p]
        q.append(c)

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

Submission status: Accepted

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

dw = [[] for i in range(n+1)]
pt = [0 for i in range(n+1)]

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

for i in range(q):
    a,b = list(map(int, input().split()))
    pt[a] += b

slist = [1]

while(True):
    nlist = []
    for i in range(len(slist)):
        nowlist = dw[slist[i]]
        for j in range(len(nowlist)):
            pt[nowlist[j]] += pt[slist[i]]
            nlist.append(nowlist[j])
    
    if(len(nlist)==0):
        break
    slist = nlist
pt = ' '.join(map(str, pt[1:]))
print(pt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    g = Graph(N)
    for aa, bb in zip(a, b):
        g.add_edge([aa-1, bb-1, 1])

    P = [0]*N
    for pp, xx in zip(p, x):
        P[pp-1] += xx

    visit = deque()
    visit.append((0, None))
    counter = [0]*N
    while len(visit) > 0:
        # print(visit)
        curr, par = visit.popleft()
        counter[curr] += P[curr]
        for t, w in g.E[curr]:
            if t == par:
                continue
            visit.append((t, curr))
            counter[t] += counter[curr]
    print(*counter)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    x = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

def main():
    N,Q = map(int,sys.stdin.readline().split())
    e = [ [ ] for i in range(N)]
    for i in range(N-1):
        a,b = map(int,sys.stdin.readline().split())
        e[a-1].append(b-1)

    from collections import defaultdict
    d = defaultdict(int)
    for i in range(Q):
        p,x = map(int,sys.stdin.readline().split())
        d[p-1] += x

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

    def dfs(x,c):
        c += d[x]
        ansl[x] = c
        for v in e[x]:
            dfs(v,c)

    dfs(0,0)
    print(" ".join(map(str,ansl)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools, collections, copy, heapq


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    G = [[] for _ in range(N)]
    for i in range(N-1):
        G[a[i]-1].append(b[i]-1)
        G[b[i]-1].append(a[i]-1)
    w = [0] * N
    for i in range(Q):
        w[p[i]-1] += x[i]
    stack = [0]
    visited = [0] * N
    while len(stack) > 0:
        t = stack.pop()
        visited[t] = 1
        adj = G[t]
        for a in adj:
            if visited[a] == 0:
                stack.append(a)
                w[a] += w[t]
    print(' '.join([str(ww) for ww in w]))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]" 
    x = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
lis = [0 for i in range(n)]
li = [0 for i in range(n)]
tree = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    tree[b-1] = a-1
for i in range(q):
    c,d = map(int,input().split())
    li[c-1] += d
lis[0] = li[0]
for i in range(1,n):
    lis[i] = lis[tree[i]]+li[i]
for i in range(n):
    lis[i] = str(lis[i])
print(" ".join(lis))

Submission status: Accepted

Solution code:
def solve():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        A, B = A-1, B-1
        adjL[A].append(B)
        adjL[B].append(A)

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

    useds = [False] * N
    def dfs(vNow, x):
        useds[vNow] = True
        anss[vNow] += x
        ans = anss[vNow]
        for v2 in adjL[vNow]:
            if not useds[v2]:
                dfs(v2, ans)

    dfs(0, 0)

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

solve()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(500000)
N, Q = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
C = [0] * (N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x
Ans = [0] * (N+1)
def dfs(v, p, a):
    a += C[v]
    Ans[v] = a
    for u in E[v]:
        if u!=p:
            dfs(u, v, a)
dfs(1, 0, 0)
print(" ".join(map(str, Ans[1:])))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
tree = [[] for i in range(N+1)]
counter = [0] * (N+1)

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

for i in range(Q):
    p, x = map(int, input().split())
    counter[p] += x
for i in range(1, N+1):
    for pn in tree[i]:
        counter[i] += counter[pn]

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

Submission status: Accepted

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())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)

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

ans = [0] * N

stack = [[0, Point[0]]]
visited = [False] * N
while stack:
    n, p = stack.pop()
    visited[n] = True
    ans[n] = p
    for to in T[n]:
        if visited[to]:
            continue
        stack.append([to, p + Point[to]])

print(*ans, sep=' ')

Submission status: Accepted

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

def main():
    def dfs(i,oi=-1,s=0):
        ans[i]=s+d[i]
        for ki in to[i]:
            if ki==oi:continue
            dfs(ki,i,s+d[i])

    n,q=map(int, input().split())
    to=defaultdict(list)
    d=[0]*n
    ans=[0]*n
    for _ in range(n-1):
        a,b=map(int, input().split())
        a-=1
        b-=1
        to[a].append(b)
        to[b].append(a)
    for _ in range(q):
        p, x = map(int, input().split())
        d[p-1]+=x
    dfs(0)
    print(*ans)

main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n,q=MI()
v=[0]*n
c=[0]*n
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=MI()
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)

for i in range(q):
    p,x=MI()
    c[p-1]+=x

#print(c)


def bfs(x):
    p=deque()
    p.append(x)
    while p:
        cur=p.popleft()
        v[cur]=1
        for i in g[cur]:
            if v[i]==0:
                p.append(i)
                c[i]+=c[cur]
bfs(0)

print(*c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def dfs(graph, v, start=0):
    n = len(graph)

    dp = v
    visited, finished = [False] * n, [False] * n

    stack = [start]
    while stack:
        start = stack[-1]

        # push unvisited children into stack
        if not visited[start]:
            visited[start] = True
            for child in graph[start]:
                if not visited[child]:
                    dp[child] += dp[start]
                    stack.append(child)

        else:
            stack.pop()

            ## base case
            #dp[start] += 1

            ## update with finished children
            #for child in graph[start]:
            #    if finished[child]:
            #        dp[start] += dp[child]

            #finished[start] = True

    return dp


def main():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n)]
    v = [0] * n

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

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

    print(*dfs(tree, v))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(v):
    for w in e[v]:
        if root[w]>=0:continue
        root[w]=v
        dfs(w)
def dfs2(v):
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        data[w]+=data[v]
        dfs2(w)
input=sys.stdin.readline
n,q=map(int,input().split())
e=[[]for _ in range(n)]
root=[0]+[-1]*(n-1)
data=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
    e[b-1]+=a-1,
#dfs(0)
for _ in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
f=[1]+[0]*(n-1)
dfs2(0)
print(*data)

Submission status: Accepted

Solution code:
from collections import deque

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

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

dq = deque([(0, -1)])
while dq:
    v, p = dq.popleft()
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        dq.append((u, v))

print(' '.join([str(x) for x in imos]))

Submission status: Accepted

Solution code:


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

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

queue = [0]
while queue:
	cur = queue.pop()
	for child in v_list[cur]:
		v_list[child].remove(cur)
		queue.append(child)

x_table = [0] * N

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

values = [None] * N
values[0] = x_table[0]
queue = [0]
while queue:
	cur = queue.pop()
	value = values[cur]
	for child in v_list[cur]:
		values[child] = value + x_table[child]
		queue.append(child)

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

Submission status: Accepted

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

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

for i in range(1, n+1):
  c[i] += c[ki[i]]

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

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int,input().split())
edge = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
tree = [0]*N
for i in range(Q):
    p,x = map(int,input().split())
    tree[p-1] += x
flag = [0]*N
flag[0] = 1
queue = deque([0])
while queue != deque([]):
    p = queue.popleft()
    for i in edge[p]:
        if flag[i] == 0:
            flag[i] = 1
            tree[i] += tree[p]
            queue.append(i)

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

Submission status: Accepted

Solution code:
N, Q = [int(i) for i in input().split()]

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

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


from collections import deque

ans = M[:]
visited = [False] * (N + 1)
visited[1] = True
Q = deque([1])
while Q:
    a = Q.popleft()
    for e in E[a]:
        if visited[e]:
            continue
        visited[e] = True
        ans[e] += ans[a]
        Q.append(e)

print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
N,Q=map(int,input().split())
L=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    L[a].append(b)
    L[b].append(a)
CL=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    CL[p-1]+=x

AL=[0]*N
ed=[0]*N
q=[(0,0)]
while len(q)!=0:
    now,val=q.pop(-1)
    ed[now] = 1
    val += CL[now]
    AL[now] = val
    for p in L[now]:
        if ed[p] == 0:
            q.append((p,val))
print(" ".join(map(str,AL)))

Submission status: Accepted

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

ab = []
for i in range(N-1):
    a, b = map(int, input().split())
    ab.append((a, b))
ab = sorted(ab, key=lambda x: x[0])

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

for i in range(N-1):
    a, b = ab[i]
    P[b-1] += P[a-1]

print(*P)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,q = map(int, input().split())

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

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

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

for v in range(n):
    for u in edge[v]:
        cnt[u] += cnt[v]

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N - 1)]
P = [list(map(int, input().split())) for _ in range(Q)]
G = [[] for _ in range(N + 1)]
X = [0] * (N + 1)
for a, b in L:
    G[a].append(b)
for p, x in P:
    X[p] += x
for a, A in enumerate(G):
    for b in A:
        X[b] += X[a]
print(" ".join(map(str, X[1:])))

Submission status: Accepted

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

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

#入力

stack = [0]
while len(stack) > 0:
    now = stack.pop()
    for i in tree[now]:
        ans[i] += ans[now]
        stack.append(i)

for i in range(n):
    print(ans[i],end=" ")
print()

Submission status: Accepted

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

class Node:
    def __init__(self):
        self.count = 0
        self.check = False
        self.link = []

def main():
    # N = int(input())
    N, Q = map(int, input().split())
    # a = list(map(int, input().split()))
    # s = input().strip()
    
    nodes = [Node() for i in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        nodes[p].count += x
    
    q = deque()
    q.append([nodes[0], 0])
    while len(q) > 0:
        node, cost = q.popleft()
        node.check = True
        node.count += cost
        cost = node.count
        for nex in node.link:
            if not nex.check:
                q.append([nex, cost])
    
    for i in range(N-1):
        print(nodes[i].count, end=" ")
    print(nodes[-1].count)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans = [0] * N
ans[0] = ct[0]
q = [(0, ct[0])]
while len(q):
  i, c = q.pop()
  for t in edges[i]:
    ans[t] = c + ct[t]
    q.append((t, ans[t]))
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

def main():
    node_num, q_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(node_num - 1)]
    q_data = [list(map(int, input().split())) for i in range(q_num)]

    graph_data = defaultdict(set)
    for i in range(node_num - 1):
        a, b = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)

    ans_list = [0 for i in range(node_num + 1)]
    for i in range(q_num):
        a, b = q_data[i]
        ans_list[a] += b

    parent_node = [0 for i in range(node_num + 1)]
    parent_node[1] = 1
    now_set = set()
    now_set.add(1)
    next_set = set()
    while len(now_set) > 0:
        for now_ele in now_set:
            for next_ele in graph_data[now_ele]:
                if parent_node[next_ele]:
                    continue
                parent_node[next_ele] = now_ele
                next_set.add(next_ele)
        now_set = next_set
        next_set = set()

    visit_flg = [0 for i in range(node_num + 1)]
    visit_flg[1] = 1
    now_set = set()
    now_set.add(1)
    next_set = set()
    while len(now_set) > 0:
        for now_ele in now_set:
            for next_ele in graph_data[now_ele]:
                if visit_flg[next_ele]:
                    continue
                visit_flg[next_ele] = 1
                ans_list[next_ele] += ans_list[now_ele]
                next_set.add(next_ele)
        now_set = next_set
        next_set = set()

    for i in range(1, node_num + 1):
        print(ans_list[i], end='')
        if i == node_num:
            print()
        else:
            print(' ',end='')





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
#print(E)
xs = [0]*N
for i in range(Q):
  p, x = map(int, input().split())
  xs[p-1] += x
#print(xs)
rs = [0]*N
q = [0]
while q:
  p = q.pop()
  rs[p] += xs[p]
  for c in E[p]:
    rs[c] += rs[p]
    q.append(c)
print(" ".join(map(str, rs)))

Submission status: Accepted

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n, q = map(int, input().split())
    edge = defaultdict(list)
    counter = [0] * n

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

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

    que = deque()
    que.append(0)

    while len(que) > 0:
        node = que.popleft()
        for next in edge[node]:
            counter[next] += counter[node]
            que.append(next)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, q = list(map(int, input().split()))
edge = []
for i in range(n-1):
    tempa, tempb = list(map(int, input().split()))
    edge.append((tempa-1, tempb-1))

node = [0] * n

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

edge.sort()
for e in edge:
    node[e[1]] += node[e[0]]

for n in node:
    print(n)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

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

q = deque()
q.appendleft((1, 1, query[1]))
ans = [0] * (N+1)

while q:
    now, prev, weight = q.pop()
    ans[now] += weight
    for e in edge[now]:
        if e == prev:
            continue
        q.appendleft((e, now, weight+query[e]))

print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque()
q.append((0, 0, -1))
while len(q):
    p, x, prev = q.pop()
    x += P[p]
    cnt[p] = x
    for b in to[p]:
        if b != prev:
            q.append((b, x, p))
print(*cnt)