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:
from collections import deque
import sys
input = sys.stdin.readline

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

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

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

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

print(*ans)

Submission status: Accepted

Solution code:
(n,q),*t=[list(map(int,t.split()))for t in open(0)]
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
for a,b in t:
 if~-n:n-=1;e[a-1]+=b-1,;e[b-1]+=a-1,
 else:d[a-1]+=b
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d)

Submission status: Accepted

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

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

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:
# ABC138D - Ki
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    def dfs(v, p):
        for u in T[v]:
            if u != p:
                cnt[u] += cnt[v]
                dfs(u, v)

    N, Q = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    P = tuple(tuple(map(int, input().split())) for _ in range(Q))
    T = [[] for _ in range(N + 1)]  # T[i] := children of vertex i
    cnt = [0] * (N + 1)
    for a, b in A:  # set tree relations
        T[a] += [b]
        T[b] += [a]
    for p, x in P:  # increment on roots
        cnt[p] += x
    dfs(1, -1)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def dfs(v, p, tree, cnt):
    for u in tree[v]:
        if u != p:
            cnt[u] += cnt[v]
            dfs(u, v, tree, cnt)


def main():
    N, Q = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    P = tuple(tuple(map(int, input().split())) for _ in range(Q))
    T = [[] for _ in range(N + 1)]  # T[i] := children of vertex i
    cnt = [0] * (N + 1)
    for a, b in A:  # set tree relations
        T[a] += [b]
        T[b] += [a]
    for p, x in P:  # increment on roots
        cnt[p] += x
    dfs(1, -1, T, cnt)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,q,*t=map(int,open(0).read().split());s=[0];d=s*n;f=s+[1]*n;e=[[]for _ in d]
for a,b in zip(*[iter(t[:-q-q])]*2):e[a-1]+=b-1,;e[b-1]+=a-1,
for p,x in zip(*[iter(t[-q-q:])]*2):d[p-1]+=x
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d)

Submission status: Accepted

Solution code:
n,q,*t=map(int,open(0).read().split())
e=[[]for _ in[0]*n]
s=[0]
d=s*n
f=[1]+s*n
for a,b in zip(*[iter(t[:-q-q])]*2):
  e[a-1]+=b-1,
  e[b-1]+=a-1,
for p,x in zip(*[iter(t[-q-q:])]*2):d[p-1]+=x
while s:
  v=s.pop()
  for w in e[v]:
    if f[w]:continue
    f[w]=1
    d[w]+=d[v]
    s+=w,
print(*d)

Submission status: Accepted

Solution code:
from collections import deque
def main():
  _map, _input, _int = map, input, int
  n, q = _map(_int, _input().split())
  values = [0] * n
  links = [[] for _ in range(n)]
  for _ in range(n - 1):
    a, b = _map(_int, _input().split())
    links[a - 1].append(b - 1)
    links[b - 1].append(a - 1)
  for _ in range(q):
    p, x = _map(_int, _input().split())
    values[p - 1] += x
  d = deque()
  d.append((0, -1))
  while len(d) != 0:
    i, p = d.popleft()
    for j in links[i]:
      if j == p:
        continue
      values[j] += values[i]
      d.append((j, i))
  print(*values)
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def main():
  _map = map
  _input = input
  _int = int
  def calc_results(values, links, i, p):
    for j in links[i]:
      if j == p:
        continue
      values[j] += values[i]
      calc_results(values, links, j, i)
  n, q = _map(_int, _input().split())
  values = [0] * (n + 1)
  links = [[] for _ in range(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())
    values[p] += x
  calc_results(values, links, 1, 0)
  print(*values[1:])
main()

Submission status: Accepted

Solution code:
import sys
def input():
        return sys.stdin.readline()[:-1]

N,Q = map(int,input().split())
 
e_list = [[] for i in range(N)]
 
for i in range(N-1):
        a,b = map(int,input().split())
        a,b = a-1,b-1
        e_list[a].append(b)
        e_list[b].append(a)
 
add_list = [0]*N
 
for i in range(Q):
        p,x = map(int,input().split())
        p = p-1
        add_list[p]+=x
 
count_list = [0]*N
count_list[0] = add_list[0]
 
vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
checked_list = [False]*N
checked_list[vi]=True
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            count_list[v1] = count_list[v]+add_list[v1]
 
print(*count_list)

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())
t = [[] for _ in range(n)]
for _ in range(n - 1):
  a, b = map(lambda x: int(x) - 1, input().split())
  t[a].append(b)
  t[b].append(a)
c = [0] * n
for _ in range(q):
  p, x = map(int, input().split())
  c[p - 1] += x
stk = deque()
stk.appendleft((0, -1))
while len(stk) != 0:
  i, p = stk.popleft()
  for j in t[i]:
    if j == p:
      continue
    c[j] += c[i]
    stk.appendleft((j, i))
print(*c)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
 
e_list = [[] for i in range(N)]
 
for i in range(N-1):
        a,b = map(int,input().split())
        a,b = a-1,b-1
        e_list[a].append(b)
        e_list[b].append(a)
 
add_list = [0]*N
 
for i in range(Q):
        p,x = map(int,input().split())
        p = p-1
        add_list[p]+=x
 
count_list = [0]*N
count_list[0] = add_list[0]
 
vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
checked_list = [False]*N
checked_list[vi]=True
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            count_list[v1] = count_list[v]+add_list[v1]
 
print(*count_list)

Submission status: Accepted

Solution code:
N,Q = list(map(int,input().split()))
 
e_list = [[] for i in range(N)]
 
for i in range(N-1):
        a,b = list(map(int,input().split()))
        a,b = a-1,b-1
        e_list[a].append(b)
        e_list[b].append(a)
 
add_list = [0]*N
 
for i in range(Q):
        p,x = list(map(int,input().split()))
        p = p-1
        add_list[p]+=x
 
count_list = [0]*N
count_list[0] = add_list[0]
 
vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            count_list[v1] = count_list[v]+add_list[v1]
 
print(*count_list)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
# 深さ優先探索で各直線を考える


def main():
    def dfs(v, p):
        for u in tree[v]:
            if u == p:
                continue
            # 累積和の計算
            ans[u] += ans[v]
            dfs(u, v)

    n, q = map(int, input().split())
    # tree[i]: 頂点i+1の子どもたち
    tree = [[] for i in range(n)]
    ans = [0] * n

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

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

    # 根ノードの頂点 1 から開始
    dfs(0, -1)

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from pprint import pprint
from collections import deque, defaultdict

n, q = list(map(int, input().strip().split(" ")))
# edges = defaultdict(set)
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a_i, b_i = list(map(int, input().strip().split(" ")))
    edges[a_i-1].append(b_i-1)
    edges[b_i-1].append(a_i-1)
    # edges[a_i-1].add(b_i-1)
    # edges[b_i-1].add(a_i-1)

# p = defaultdict(int)
# counter = defaultdict(int)
counter = [0] * n
p = [0] * n
for _ in range(q):
    p_i, x_i = list(map(int, input().strip().split(" ")))
    # p[p_i-1] += x_i
    counter[p_i-1] += x_i


parents = deque()
# parents.append(0)
# parents = []
parents.append(0)
visited = set()
while parents:
    parent = parents.popleft()
    # parent = parents.pop()
    if parent in visited:
        continue
    visited.add(parent)
    # counter[parent] += p[parent]
    # print("parent")
    # print(parent, counter[parent])
    for child in edges[parent]:
        if child in visited:
            continue
        # if counter[child] != 0:
        #    continue
        counter[child] += counter[parent]
        # print("child")
        # print(child, counter[child])
        parents.append(child)
        # parents.add(child)

#print(" ".join(list(map(str, counter.values()))))
#print(" ".join(list(map(str, counter))))
print(*counter)

Submission status: Accepted

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

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

edge_dic = defaultdict(lambda: [])

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

ans_array = [0] * N

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


node_deque = deque()
used_array = [-1] * N
node_deque.append(0)
used_array[0] = 1

while len(node_deque):
    node = node_deque.popleft()
    for n in edge_dic[node]:
        if used_array[n] == 1:
            continue
        ans_array[n] += ans_array[node]
        used_array[n] = 1
        node_deque.append(n)

ans_str = map(str,ans_array)
print(" ".join(ans_str))

Submission status: Accepted

Solution code:
from pprint import pprint
from collections import deque, defaultdict

n, q = list(map(int, input().strip().split(" ")))
# edges = defaultdict(set)
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a_i, b_i = list(map(int, input().strip().split(" ")))
    edges[a_i-1].append(b_i-1)
    edges[b_i-1].append(a_i-1)
    # edges[a_i-1].add(b_i-1)
    # edges[b_i-1].add(a_i-1)

# p = defaultdict(int)
# counter = defaultdict(int)
counter = [0] * n
p = [0] * n
x = []
for _ in range(q):
    p_i, x_i = list(map(int, input().strip().split(" ")))
    # p[p_i-1] += x_i
    counter[p_i-1] += x_i


parents = deque()
# parents.append(0)
# parents = []
parents.append(0)
visited = set()
while parents:
    parent = parents.popleft()
    # parent = parents.pop()
    if parent in visited:
        continue
    visited.add(parent)
    # counter[parent] += p[parent]
    # print("parent")
    # print(parent, counter[parent])
    for child in edges[parent]:
        if child in visited:
            continue
        # if counter[child] != 0:
        #    continue
        counter[child] += counter[parent]
        # print("child")
        # print(child, counter[child])
        parents.append(child)
        # parents.add(child)

#print(" ".join(list(map(str, counter.values()))))
print(" ".join(list(map(str, counter))))

Submission status: Accepted

Solution code:
from collections import deque
import sys


input = sys.stdin.readline
n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n-1)]
p = [list(map(int, input().split())) for i in range(q)]

tree = [[] for i in range(n)]
for i in range(n-1):
    tree[info[i][0] - 1].append(info[i][1] - 1)
    tree[info[i][1] - 1].append(info[i][0] - 1)

memo = {}
for i in range(n):
    memo[i] = 0
for i in range(q):
    memo[p[i][0] - 1] += p[i][1]

dp = [0] * n
visited = [False]*n
q = deque([0])
visited[0] = True
dp[0] = memo[0]

while q:
    pos = q.popleft()
    for next_pos in tree[pos]:
        if visited[next_pos]:
            continue
        visited[next_pos] = True
        dp[next_pos] += dp[pos] + memo[next_pos]
        q.append(next_pos)
print(*dp)

Submission status: Accepted

Solution code:
from collections import deque
import sys


input = sys.stdin.readline
n, q = map(int, input().split())
info = [tuple(map(int, input().split())) for i in range(n-1)]
p = [tuple(map(int, input().split())) for i in range(q)]

tree = [[] for i in range(n)]
for i in range(n-1):
    tree[info[i][0] - 1].append(info[i][1] - 1)
    tree[info[i][1] - 1].append(info[i][0] - 1)

memo = {}
for i in range(n):
    memo[i] = 0
for i in range(q):
    memo[p[i][0] - 1] += p[i][1]

dp = [0] * n
visited = [False]*n
q = deque([0])
visited[0] = True
dp[0] = memo[0]

while q:
    pos = q.popleft()
    for next_pos in tree[pos]:
        if visited[next_pos]:
            continue
        visited[next_pos] = True
        dp[next_pos] += dp[pos] + memo[next_pos]
        q.append(next_pos)
print(*dp)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
r = [[] for i in range(n)]
v = [0 for i in range(n)]

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

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


bfs = [0]
visit = [False for i in range(n)]
while len(bfs) != 0:
    tmp = []
    for i in bfs:
        for y in r[i]:
            if not visit[y]:
                v[y] += v[i]
                tmp.append(y)
        visit[i] = True
    bfs = tmp

#print(" ".join(map(str,v)))
print(*v)

Submission status: Accepted

Solution code:
import collections

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
for _ in range(q):
  v,val=map(int,input().split())
  cnt[v]+=val
q=collections.deque()
q.append(1)
checked=[0]*(n+1)
while q:
  v=q.pop()
  checked[v]=1
  for u in g[v]:
    if checked[u]==1:
      continue
    cnt[u]+=cnt[v]
    q.append(u)
print(*cnt[1:])

Submission status: Accepted

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


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    e = [list(map(int, input().split())) for _ in range(n-1)]
    p = [list(map(int, input().split())) for _ in range(q)]

    e2 = [[] for _ in range(n)]
    for ee in e:
        a, b = ee
        e2[a-1].append(b-1)
        e2[b-1].append(a-1)

    counters = [0] * n
    for pp in p:
        counters[pp[0]-1] += pp[1]

    used = [0] * n

    def dfs(x, p_sum):
        counters[x] += p_sum
        used[x] = 1
        for y in e2[x]:
            if used[y] == 1:
                continue
            dfs(y, counters[x])

    dfs(0, 0)
    print(*counters)


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
stdin = sys.stdin
na = lambda: map(int, stdin.readline().split())
N, Q = na()
ans = [0] * N
g = [[] for _ in range(N)]

def dfs(cur, par): 
  for e in g[cur]:
    if e == par:
      continue
    ans[e] += ans[cur]
    dfs(e, cur)

for _ in range(N - 1):
    a, b = na()
    g[a-1] += [b-1]
    g[b-1] += [a-1]
    
for _ in range(Q):
    p, x = na()
    ans[p-1] += x
 
dfs(0, -1)
print(*ans)

Submission status: Accepted

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


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    e = [list(map(int, input().split())) for _ in range(n-1)]
    p = [list(map(int, input().split())) for _ in range(q)]

    e2 = [[] for _ in range(n)]
    for ee in e:
        a, b = ee
        e2[a-1].append(b-1)
        e2[b-1].append(a-1)

    counters = [0 for _ in range(n)]
    for pp in p:
        counters[pp[0]-1] += pp[1]

    used = [0] * n

    def dfs(x, p_sum):
        counters[x] += p_sum
        used[x] = 1
        for y in e2[x]:
            if used[y] == 1:
                continue
            dfs(y, counters[x])

    dfs(0, 0)
    print(*counters)


main()

Submission status: Accepted

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

def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = input().split()
        a = int(a)
        b = int(b)
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

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

    st = []
    seen = set()
    st.append(0)
    while(st):
        x = st.pop()
        if(x in seen):continue
        seen.add(x)
        for i in gp[x]:
            if(i in seen):continue
            li[i]+=li[x]
            st.append(i)
    print(*li)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

stdin = sys.stdin
na = lambda: map(int, stdin.readline().split())

g = []
counter = []
ans = []

def dfs(cur, par, val):
  global counter, ans, g
  val += counter[cur]
  ans[cur] = val
  for e in g[cur]:
    if e == par:
      continue
    dfs(e, cur, val)

def main():
  global g, ans, counter
  N, Q = na()
  
  g = [[] for _ in range(N)]
  for _ in range(N - 1):
    a, b = na()
    g[a-1] += [b-1]
    g[b-1] += [a-1]

  counter = [0] * N
  for _ in range(Q):
    p, x = na()
    counter[p-1] += x

  ans = [0] * N
  dfs(0, -1, 0)
  print(*ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
r = [[] for i in range(n)]
v = [0 for i in range(n)]

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

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


for i in range(n):

    for y in r[i]:
        v[y] += v[i]

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

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
parentNodes = [0] * (N+1) #i番目のノードの親番号
counter = [0] * (N+1)

for i in range(N-1):
	a, b = map(int, input().split())
	parentNodes[b] = a
 
for _ in range(Q):
	p,x = map(int, input().split())
	counter[p] += x
 
for i in range(1,N+1):
	counter[i] += counter[parentNodes[i]]
 
print(*counter[1:])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split(" "))
A = [0]*N

B = [0 for j in range(N)]
for i in range(N-1):
    a,b = map(int,input().split(" "))
    A[b-1] = a-1
    
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]

for i in range(1,N):
        B[i] += B[A[i]]
for i in range(N):
        print(B[i],end=" ")

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
r = [[] for i in range(n+1)]
v = [0 for i in range(n+1)]

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

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


for i in range(1,n+1):

    for y in r[i]:
        v[y] += v[i]

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

Submission status: Accepted

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

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

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

values = [0] * (N+1)
for p,x in PX:
    values[p] += x
def dfs(v,parent,add):
    values[v]+=add
    for x in graph[v]:
        if x==parent:
            continue
        dfs(x,v,values[v])
        
dfs(1,0,0)
answer=' '.join(map(str,values[1:]))
print(answer)

Submission status: Accepted

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

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

ans = [0]*n  
for j in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
from collections import deque
s = deque()
s.append(0)

while s:
  v = s.pop()
  for v_ in g[v]:
    ans[v_] += ans[v]
    s.append(v_)

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

Submission status: Accepted

Solution code:
from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    counter = defaultdict(int)

    parents = deque()
    parents.append(0)
    while parents:
        parent = parents.popleft()
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        if parent in edges:
            for child in edges[parent]:
                if counter[child] != 0:
                    continue
                counter[child] = counter[parent]
                # print("child")
                # print(child, counter[child])
                parents.append(child)

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

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    edges = defaultdict(list)
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        edges[a_i-1].append(b_i-1)

    p = [0] * n
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

Submission status: Accepted

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

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

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

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

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

ans = [X[i] for i in range(N)]
for i in range(N):
    F[i] = 1
    for j in range(len(T[i])):
        if F[T[i][j]] == 1:
            continue
        ans[T[i][j]] += ans[i]

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split(" "))
A = [0]*N

B = [0 for j in range(N)]
for i in range(N-1):
    a,b = map(int,input().split(" "))
    A[b-1] = a-1
    
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]

for i in range(1,N):
        B[i] += B[A[i]]
for i in range(N):
        print(B[i],end=" ")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)


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

data={i+1:0 for i in range(N)}

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

relate = [list(map(int, input().split() )) for i in range(N-1)]
relate.sort(key=lambda x :x[0])
    
for i in range(Q):
    root, value = list(map(int, input().split() ))
    data[root]+=value

for a,b in relate:
    data[b]+=data[a]

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

Submission status: Accepted

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

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

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

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

ans = [X[i] for i in range(N)]
for i in range(N):
    F[i] = 1
    for j in range(len(T[i])):
        if F[T[i][j]] == 1:
            continue
        ans[T[i][j]] += ans[i]

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

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)

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

stack = [1]
while stack:
    label = stack.pop()
    for i in l[label]:
        value[i] += value[label]
    stack += l[label]
        
print(*value[1:])

Submission status: Accepted

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

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

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

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

for root, reaf in tree.items():
    for i in reaf:
        op[i] += op[root]

print(*op[1:])

Submission status: Accepted

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

# 遅延評価で加えてあげるだけ

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

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

Solution code:
def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        ab.sort()
        
        plus = [0 for _ in range(N)]
        for _ in range(Q):
        	p,x = map(int,input().split())
        	plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        print(*plus)

if __name__ == '__main__':
        main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC138 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    g[a-1].append(b-1)

ans = [0]*n
for _ in range(q):
    p,x = LI()
    ans[p-1] += x

que = deque()
que.append(0)
check = [True]*n
while que:
    v = que.popleft()
    for i in g[v]:
        if check[i]:
            check[i] = False
            que.append(i)
            ans[i] += ans[v]
print(*ans)

Submission status: Accepted

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

c = [0] * (n+1)
parent = [0] * (n+1)
for _ in range(n-1):
    a, b = map(int, input().split())
    parent[b] = a
    

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

for i in range(2, n+1):
    c[i] += c[parent[i]]
    
print(' '.join(map(str, c[1:])))

Submission status: Accepted

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

dictionary = [[] for i in range(N + 1)]

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

num = [0] * (N + 1)

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

for i in range(1, N + 1):
    print(num[i])
    for j in range(0, len(dictionary[i])):
        num[dictionary[i][j]] += num[i]

Submission status: Accepted

Solution code:
def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        ab.sort()
        
        plus = [0 for _ in range(N)]
        for _ in range(Q):
        	p,x = map(int,input().split())
        	plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

if __name__ == '__main__':
        main()

Submission status: Accepted

Solution code:
N,Q = map(int,input().split(' '))
out_put_list = [0] * N
tree_list = [[] for i in range(N)]

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

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

for i in range(len(tree_list)):
    for num in tree_list[i]:
        out_put_list[num] += out_put_list[i]

print(*out_put_list)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
edge = [[] for i in range(N)]
q = [0 for i in range(N)]
 
for i in range(N-1):
  a, b = map(int, input().split())
  edge[a-1].append(b)
for i in range(Q):
  a, v = map(int, input().split())
  q[a-1] += v
 
for i, v in enumerate(q):
  #print(i, v)
  for j in edge[i]:
    #print(j)
    q[j-1] += v
print(*q)

Submission status: Accepted

Solution code:
NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])
out_put_list = [0] * N
tree_list = [[] for i in range(N)]

for i in range(N-1):
    ab = input().split(' ')
    a = int(ab[0]) -1
    b = int(ab[1]) -1
    tree_list[a].append(b)

for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    out_put_list[p-1] += x

for i in range(len(tree_list)):
    for num in tree_list[i]:
        out_put_list[num] += out_put_list[i]

print(*out_put_list)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N-1)]
px = [list(map(int, input().split())) for i in range(Q)]
cnt = [0] * N

for p, x in px:
    cnt[p-1] += x
for a, b in sorted(ab):
    cnt[b-1] += cnt[a-1]

print(*cnt)