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:
import collections

N, Q = map(int, input().split())
lst = [[] for _ in range(N)]
ans = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    lst[b-1].append(a-1)
    lst[a-1].append(b-1)
for j in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
               
q=collections.deque()
q.append(0)
flag = [0]*N
while q:
    y = q.pop()
    flag[y] = 1
    for k in lst[y]:
        if flag[k] == 1:
            continue
        ans[k] += ans[y]
        q.append(k)
print(*ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, Q = map(int, input().split())
connections = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    pa, ki = map(int, input().split())
    connections[pa].append(ki)
    connections[ki].append(pa)

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

i = 1

def dfs(k=1,bef=-1):
    global scores
    global fins
    kids = connections[k]
    if len(kids)==1 and bef==kids[0]:
        return
    for kid in kids:
        # print(f'k:{k} kids:{kids}')
        if bef==kid:
            continue
        scores[kid]+=scores[k]
        dfs(kid,k)


dfs()



print(*scores[1:])

Submission status: Accepted

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

 
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
s = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

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

counter = [0] * n
for i in range(q):
        p, x = na()
        counter[p-1] += x

visit = [False] * n
visit[0] = True
que = deque([0])

while que:
        parent = que.popleft()
        for child in G[parent]:
                if visit[child]:
                        None
                else:
                        visit[child] = True
                        counter[child] += counter[parent]
                        que.append(child)

print(*counter)

Submission status: Accepted

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

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

counter = [0] * n
for i in range(q):
        p, x = na()
        counter[p-1] += x

visit = [False] * n
visit[0] = True
stack = [0]

while stack:
        parent = stack.pop()
        for child in G[parent]:
                if visit[child]:
                        None
                else:
                        visit[child] = True
                        counter[child] += counter[parent]
                        stack.append(child)

print(*counter)

Submission status: Accepted

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

import sys


sys.setrecursionlimit(10**6)


def main():
    n, q = map(int, sys.stdin.readline().split())

    tree = [[] for x in range(n + 1)]
    data = [0 for x in range(n + 1)]

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

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

    def dfs(p, p2, x):
        data[p] += x
        for p3 in tree[p]:
            if p3 == p2:
                continue
            dfs(p3, p, data[p])

    dfs(1, 0, 0)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n,q = map(int,input().split())
    edges = [list(map(int,input().split())) for _ in range(n-1)]
    px = [list(map(int,input().split())) for _ in range(q)]

    count = [0]*n
    ans = [0]*n
    visit = [False] * n
    visit[0] = True

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

    for a,b in edges:
        roots[a-1].append(b-1)
        roots[b-1].append(a-1)

    for p,x in px:
        count[p-1] += x

    q = [0]

    ans[0] = count[0]

    while q:
        label = q.pop(-1)
        for i in roots[label]:
            if not visit[i]:
                ans[i] += ans[label] + count[i]
                visit[i] = True
                q.append(i)


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N)]
    a = []
    b = []
    a_append = a.append
    b_append = b.append
    for i in range(N-1):
        x, y = map(int, input().split())
        a_append(x)
        b_append(y)
    cost = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cost[p-1] += x

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

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

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

    print(*cost)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

    visited = [False] * n
    stack = [0]
    while len(stack) > 0:
        num = stack.pop()
        visited[num] = True
        for i in to[num]:
            if visited[i]:
                continue
            ns[i] += ns[num]
            stack.append(i)
    print(*ns)
resolve()

Submission status: Accepted

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

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

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

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

def bfs(): 
    q = deque()
    q.append((1, 0))
    while q:
        v, p = q.popleft()
        cnt[v] += cnt[p]
        for nv in g[v]:
            if nv == p:
                continue
            q.append((nv, v))
    ret = ' '.join(map(str, cnt[1:]))
    return ret

ans = bfs()
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(500000)
input=sys.stdin.readline
n,q=map(int,input().split())
edge=[[] for i in range(n)]
cost=[0]*n
for i in range(n-1):
  p,s=map(int,input().split())
  p-=1;s-=1
  edge[p].append(s)
  edge[s].append(p)
for i in range(q):
  x,c=map(int,input().split())
  x-=1
  cost[x]+=c
visited=[False]*n
queue=deque([0])
visited[0]=True
while len(queue)!=0:
  a=queue.popleft()
  for i in edge[a]:
    if visited[i]==True:continue
    queue.append(i)
    visited[i]=True
    cost[i]+=cost[a]
for i in range(n):
  cost[i]=str(cost[i])
print(" ".join(cost))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N, Q = inpl()
neighbor = [[] for i in range(N)]
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)
X = [0] * N
for _ in range(Q):
    p, x = inpl()
    X[p-1] += x

result = [0] * N
result[0] = X[0]
visited = [False] * N
dfs_stack = [0]
while dfs_stack:
    node = dfs_stack.pop()
    visited[node] = True
    for c in neighbor[node]:
        if visited[c]:
            continue
        else:
            dfs_stack.append(c)
            result[c] = result[node] + X[c]

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

Submission status: Accepted

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

    visited = [False] * n
    stack = [0]
    while len(stack) > 0:
        num = stack.pop()
        visited[num] = True
        for i in to[num]:
            if visited[i]:
                continue
            ns[i] += ns[num]
            stack.append(i)
    print(*ns)
resolve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**9)

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
ans = [0]*N
queue = deque()

for _ in range(N-1):
    aa, bb = map(int, input().split())
    tree[aa-1].append(bb - 1)
    tree[bb-1].append(aa - 1)


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

# def DFS(x, pre):
#     global ans
#     for i in tree[x]:
#         if i==pre:
#             continue
#
#         ans[i] += ans[x]
#         DFS(i, x)
#
#     return
#
# for _ in range(Q):
#     q, x = map(int, input().split())
#     ans[q-1] += x

def DFS(x, pre):
    global ans
    for i in tree[x]:
        if i==pre:
            continue

        ans[i] += ans[x]
        queue.append((i, x))

queue.append((0, -1))
while queue:
    DFS(*queue.pop())

for x in ans:
    print(x)

Submission status: Accepted

Solution code:
def d_ki():
    import sys
    input = sys.stdin.readline
    N, Q = [int(i) for i in input().split()]

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

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

    # 1次元配列だったら単純に累積和を取ればいいのだが、木なので
    # DFSをしなければならない
    q = [0]
    is_visited = [False] * N
    while q:
        current = q.pop()
        is_visited[current] = True
        for child in tree[current]:
            if is_visited[child]:
                continue
            ans[child] += ans[current]
            q.append(child)
    return ' '.join(map(str, ans))

print(d_ki())

Submission status: Accepted

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

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

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

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

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(500000)
n,q=map(int,input().split())
edge=[[] for i in range(n)]
cost=[0]*n
for i in range(n-1):
  p,s=map(int,input().split())
  p-=1;s-=1
  edge[p].append(s)
  edge[s].append(p)
for i in range(q):
  x,c=map(int,input().split())
  x-=1
  cost[x]+=c
visited=[False]*n
queue=deque([0])
visited[0]=True
while len(queue)!=0:
  a=queue.popleft()
  for i in edge[a]:
    if visited[i]==True:continue
    queue.append(i)
    visited[i]=True
    cost[i]+=cost[a]
for i in range(n):
  cost[i]=str(cost[i])
print(" ".join(cost))

Submission status: Accepted

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

def dfs(v, p):
    for u in link[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

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

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

dfs(0, -1)

print(*ans)

Submission status: Accepted

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

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

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

q = deque([(0, -1)])
while len(q) > 0:
    u, p = q.pop()
    for v in adjacent[u]:
        if v == p:
            continue
        ans[v] += ans[u]
        q.appendleft((v, u))
print(' '.join([str(ans[i]) for i in range(N)]))

Submission status: Accepted

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

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N, Q = inpl()
neighbor = [[] for i in range(N)]
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)
X = [0] * N
for _ in range(Q):
    p, x = inpl()
    X[p-1] += x

result = [0] * N
result[0] = X[0]
visited = [False] * N
dfs_stack = [0]
x = 0
while dfs_stack:
    node = dfs_stack.pop()
    visited[node] = True
    for c in neighbor[node]:
        if visited[c]:
            continue
        else:
            dfs_stack.append(c)
            result[c] = result[node] + X[c]

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

Submission status: Accepted

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

def main():
    N, Q = map(int, input().split())
    tree = [[] for _ in range(N)]
    
    for i 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 i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x

    visited = [False] * N
    visited[0] = True
    Q = deque([0])

    while Q:
        p = Q.popleft()

        for q in tree[p]:
            if visited[q]:
                continue
            visited[q] = True
            ans[q] += ans[p]
            Q.append(q)

    print(*ans)
main()

Submission status: Accepted

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

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

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

Solution code:
# 絶対に参考にするな他を当たれ
n, q = map(int, input().split())

links = [[] for _ in range(n + 1)]
point = [0] * (n + 1)
checked = [False] * (n + 1)

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

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

nextCheck = [1]

while nextCheck:
    idx = nextCheck.pop()
    for dest in links[idx]:
        if not checked[dest]:
            point[dest] += point[idx]
            nextCheck.append(dest)
            checked[idx] = True

print(*point[1:])

Submission status: Accepted

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:
    p -= 1
    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: Accepted

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

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

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

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

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

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

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


def main():
    N, Q = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    cnt = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x
    ans = [0] * N
    q = deque([(0, 0, -1)])
    while len(q):
        cur, total, prev = q.popleft()
        total += cnt[cur]
        ans[cur] = total
        for a in adj[cur]:
            if a == prev:
                continue
            q.append((a, total, cur))
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
Edge = [set() for _ in range(N+1)]
for i in range(N-1):
  e1,e2 = map(int, input().split())
  Edge[e1].add(e2)
  Edge[e2].add(e1)
Counter = [0] * (N+1)
for i in range(Q):
  p,x = map(int, input().split())
  Counter[p] += x

#print(Edge)
  
Visited = [False] * (N+1)
stack = {1}
while (stack):
  stack2 = set()
  for i in range(len(stack)):
    e1 = stack.pop()
    for e2 in Edge[e1]:
      if not Visited[e2]:
        Counter[e2] += Counter[e1]
        stack2.add(e2)
    Visited[e1] = True
  stack = stack2
  #print(Visited)

print(*[Counter[i] for i in range(1,N+1)])

Submission status: Accepted

Solution code:
from collections import deque

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

stack = deque()
stack.append(0)
checked = [False] * N

while stack:
    v = stack.popleft()
    checked[v] = True
    for e in E[v]:
        if checked[e]:
            continue
        V[e] += V[v]
        stack.append(e)
        checked[e] = True

print(*V)

Submission status: Accepted

Solution code:
n,q,*abpx=map(int,open(0).read().split())
edge=[[] for i in range(n)]
for a,b in zip(abpx[:-2*q:2],abpx[1:-2*q:2]):
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

base_score = [0]*n
for p,x in zip(abpx[-2*q::2],abpx[-2*q+1::2]):
    base_score[p-1] += x
    
score=[0]*n
check=[0]*n
update_n=[0]
check[0] = 1
while update_n:
    current_n = update_n.pop()
    score[current_n] = base_score[current_n]
    for next_n in edge[current_n]:
        if check[next_n]:
            continue
        else:
            check[next_n] = 1
            base_score[next_n] += base_score[current_n]
            update_n += next_n,

print(*score)

Submission status: Accepted

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+1)]
for a, b in ab:
    l[a].append(b)
    l[b].append(a)

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

s = [1]
flag = [False]*(n+1)
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[1:])

Submission status: Accepted

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

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 q,x in pxlist:
    anslist[q-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: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
from collections import deque

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

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

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

ans = [0] * N

stack = deque([1])
while len(stack)>0:
    node = stack.pop()
    ans[node-1] += operations[node-1]
    for node_c in connection[node-1]:
        connection[node_c-1].remove(node)
        ans[node_c-1] += ans[node-1]
        stack.append(node_c)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,readline().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,readline().split())
    val[a-1] += b 

def dps(i,parent): 
    for j in graph[i]:
        if j == parent:
            continue
        val[j] += val[i]
        dps(j,i)
                
dps(0,-1)
print(*val)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(i,we,par):
    global adj,co,res
    we+=co[i]
    res[i]=we
    for j in adj[i]:
        if j!=par:
            dfs(j,we,i)
            
input = sys.stdin.readline
n,q=map(int,input().split())
adj=[set() for i in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    adj[a-1].add(b-1)
    adj[b-1].add(a-1)
co=[0]*n
for i in range(q):
    a,b=map(int,input().split())
    co[a-1]+=b
res=[0]*n
dfs(0,0,None)
for i in range(n):
    print(res[i],end=" ")
print()

Submission status: Accepted

Solution code:
def main():
  N, Q = map(int, input().split())
  #graph = [[] for i in range(200010)]
  #ans = [0 for i in range(200010)]
  graph = [[] for i in range(N)]
  ans = [0 for i in range(N)]
  import sys
  #sys.setrecursionlimit(100000)
  sys.setrecursionlimit(10**7)
  #
  readline = sys.stdin.readline


  for _ in range(N - 1):
      #a, b = map(int, input().split())
      a, b = map(int, readline().split())
      a -= 1
      b -= 1

      graph[a].append(b)
      graph[b].append(a)

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

      ans[p] += x

  def dfs(node, frm=-1):
      for to in graph[node]:
          if to == frm:
              continue
          ans[to] += ans[node]
          dfs(to, node)
  dfs(0)

  #print(*ans[:N])
  print(*ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

def addc(p,b):
  for i in e[p]:
    if(i == b):
      continue
    c[i] += c[p]
    addc(i,p)

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

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

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

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

addc(1,-1)

print(*c[1:])

Submission status: Accepted

Solution code:
def main():
  N, Q = map(int, input().split())
  graph = [[] for i in range(200010)]
  ans = [0 for i in range(200010)]
  import sys
  #sys.setrecursionlimit(100000)
  sys.setrecursionlimit(10**7)
  #
  readline = sys.stdin.readline


  for _ in range(N - 1):
      #a, b = map(int, input().split())
      a, b = map(int, readline().split())
      a -= 1
      b -= 1

      graph[a].append(b)
      graph[b].append(a)

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

      ans[p] += x

  def dfs(node, frm=-1):
      for to in graph[node]:
          if to == frm:
              continue
          ans[to] += ans[node]
          dfs(to, node)
  dfs(0)

  print(*ans[:N])

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
n, q = map(int, input().split())
tl = [list() for _ in range(n)]
xl = [0] * n
ans = [0] * n
 
for i in range(n-1):
    a, b = map(int, input().split())
    tl[a-1].append(b-1)
    tl[b-1].append(a-1)
 
for i in range(q):
    p, x = map(int, input().split())
    xl[p-1] += x

def rec(p, parent, x):
    x += xl[p]
    ans[p] = x
    for num in tl[p]:
        if num == parent: continue
        rec(num, p, x)

rec(0, -1, 0)
 
print(*ans)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
graph = [[] for i in range(200010)]
ans = [0 for i in range(200010)]
import sys
#sys.setrecursionlimit(100000)
sys.setrecursionlimit(10**7)
#
readline = sys.stdin.readline


for _ in range(N - 1):
    #a, b = map(int, input().split())
    a, b = map(int, readline().split())
    a -= 1
    b -= 1

    graph[a].append(b)
    graph[b].append(a)

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

    ans[p] += x

def dfs(node, frm=-1):
    for to in graph[node]:
        if to == frm:
            continue
        ans[to] += ans[node]
        dfs(to, node)
dfs(0)

print(*ans[:N])

Submission status: Accepted

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

N, Q = map(int, input().split())
tree = [[] for _ in range(N+1)]
value = [0] * (N+1)
visit = [False] * (N+1)

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

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

# all_value_sum
q = queue.Queue()
q.put(1)
visit[1] = True
while not q.empty():
    now = q.get()
    for next in tree[now]:
        if not visit[next]:
            value[next] += value[now]
            q.put(next)
            visit[next] = True

# output_value
s = " ".join(map(str, value[1:]))
print(s)