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 sys

sys.setrecursionlimit(10 ** 9)

def main():
  input = sys.stdin.buffer.readline
  read = sys.stdin.buffer.read
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())
  ABPX = list(map(int, read().split()))
  AB = iter(ABPX[:N+N-2])
  PX = iter(ABPX[N+N-2:])

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = [[] for _ in range(N)]
  shown = set()

  for a, b in zip(AB, AB):
    a -= 1
    b -= 1
    relations[a].append(b)
    relations[b].append(a)

  points = [0] * N
  result = [0] * N

  for p, x in zip(PX, PX):
    p -= 1
    points[p] += x

  def solve(parent, relations, points, result):
    result[parent] += points[parent]
    shown.add(parent)
    for child in relations[parent]:
      if child not in shown:
        result[child] += result[parent]
        solve(child, relations, points, result)
      
  solve(0, relations, points, result)
  print(*result)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
arr=[[] for _ in range(n)]
ans=[0]*n
for i in range(n-1):
    a,b=map(int,input().split())
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)

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

que=deque([0])

visited=[0]*n
while que:
    x=que.popleft()
    visited[x]=-1
    for i in arr[x]:
        if visited[i]>-1:
            ans[i]+=ans[x]
            que.append(i)

print(*ans)

Submission status: Accepted

Solution code:
import sys

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

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

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

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

def dfs(x, d, s): # x:計算する頂点（上側）, d:計算済み(0)か否か(1), s:頂点xの値
  for y in T[x]: # 頂点xとつながる各頂点yの計算を行う
    if d[y] == 1: # 頂点yが計算未了の場合
      s += cnt[y] # 頂点xの値sに頂点yの値を足す
      ans[y] = s # 頂点yの値はsに確定
      d[y] = 0 # 頂点yの計算は終わったのでd[y]=0とする
      dfs(y, d, s) # 頂点yの下層についても再帰的に計算
      s -= cnt[y] # 頂点yの下層の計算が終わったので、sを頂点xの値に戻す

d = [1] * N
d[0] = 0

ans[0] = cnt[0]
s = cnt[0]

dfs(0, d, s)

print(*ans)

Submission status: Accepted

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]

n,q = LI()

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

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

def dfs(x,d,s):
	for y in v[x]:
		if d[y]:
			s += f[y]
			ans[y] = s
			d[y] = 0
			dfs(y,d,s)
			s -= f[y]

ans = [0]*n
d = [1]*n
d[0] = 0
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans)

Submission status: Accepted

Solution code:
def main():
    from collections import deque, defaultdict

    n, q, *abpx = map(int, open(0).read().split())

    g = defaultdict(list)
    for u, v in zip(*[iter(abpx[:2 * (n - 1)])] * 2):
        g[u].append(v)
        g[v].append(u)

    f = defaultdict(int)

    for p, x in zip(*[iter(abpx[2 * (n - 1):])] * 2):
        f[p] += x

    vis = {i: False for i in range(1, n + 1)}

    q = deque([])
    q.append([1, 0])
    res = [0 for i in range(n+1)]
    while q:
        i, c = q.pop()
        if vis[i]:
            continue
        vis[i] = True
        ch = g[i]
        w = c + f[i]
        res[i] = w
        for u, v in zip(ch, [w] * len(ch)):
            q.appendleft([u, v])

    ans = ' '.join(map(str, res[1:]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    n, q, *abpx = map(int, open(0).read().split())

    g = [[] for _ in range(n + 1)]
    for u, v in zip(*[iter(abpx[:2 * (n - 1)])] * 2):
        g[u].append(v)
        g[v].append(u)

    f = [0 for _ in range(n + 1)]

    for p, x in zip(*[iter(abpx[2 * (n - 1):])] * 2):
        f[p] += x

    k = [0 for _ in range(n + 1)]
    vis = [False for _ in range(n + 1)]

    q = deque([])
    q.append([1, 0])
    while q:
        i, c = q.pop()
        if vis[i]:
            continue
        vis[i] = True
        ch = g[i]
        w = c + f[i]
        k[i] = w
        for u, v in zip(ch, [w] * len(ch)):
            q.appendleft([u, v])

    ans = ' '.join(map(str, k[1:]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(300000)
    n, q, *abpx = map(int, sys.stdin.read().split())

    g = [[] for _ in range(n + 1)]
    for u, v in zip(*[iter(abpx[:2 * (n - 1)])] * 2):
        g[u].append(v)
        g[v].append(u)

    f = [0 for _ in range(n + 1)]

    for p, x in zip(*[iter(abpx[2 * (n - 1):])] * 2):
        f[p] += x

    k = [0 for _ in range(n + 1)]
    vis = [False for _ in range(n + 1)]

    def c(i, p):
        if vis[i]:
            return
        vis[i] = True
        w = f[i] + p
        k[i] = w
        ch = g[i]
        for x in ch:
            c(x, w)
    c(1, 0)
    ans = ' '.join(map(str, k[1:]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def c(i, p, f, g, k, vis):
    if vis[i]:
        return
    vis[i] = True
    w = f[i] + p
    k[i] = w
    ch = g[i]
    for x in ch:
        c(x, w, f, g, k, vis)


def main():
    import sys
    sys.setrecursionlimit(300000)
    n, q, *abpx = map(int, sys.stdin.read().split())

    g = [[] for _ in range(n + 1)]
    for u, v in zip(*[iter(abpx[:2 * (n - 1)])] * 2):
        g[u].append(v)
        g[v].append(u)

    f = [0 for _ in range(n + 1)]

    for p, x in zip(*[iter(abpx[2 * (n - 1):])] * 2):
        f[p] += x

    k = [0 for _ in range(n + 1)]
    vis = [False for _ in range(n + 1)]

    c(1, 0, f, g, k, vis)
    ans = ' '.join(map(str, k[1:]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

neighbors = {v: [] for v in range(n)}
for a, b in es:
    neighbors[a - 1] += [b - 1]
    neighbors[b - 1] += [a - 1]

queue = [(0, 0)]  # vertex, sum so far
counter = [None for _ in range(n)]

while queue:
    v, s = queue.pop()
    cv = s + xs[v]
    counter[v] = cv
    for n in neighbors[v]:
        if counter[n] is None:
            queue.append((n, cv))

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

Submission status: Accepted

Solution code:
from collections import deque
import sys

n, q = map(int, input().split())
Edges = [[] for _ in range(n)]

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

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

Ans = [0]*n
q = deque([0])
Ans[0] = Q[0]
Visited = [False]*n
Visited[0] = True
while q:
    fr = q.pop()
    for to in Edges[fr]:
        if Visited[to]:
            continue
        Ans[to] = Ans[fr]+Q[to]
        Visited[to] = True
        q.append(to)

print(*Ans)

Submission status: Accepted

Solution code:
from collections import deque 
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)
    G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x
que=deque([(0,-1)])
#print(que)
while que:
    now, pre=que.popleft()
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

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

Submission status: Accepted

Solution code:
from collections import deque 
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)
    G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x
que=deque([(0,-1)])
#print(que)
while que:
    now, pre=que.pop()
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

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

Submission status: Accepted

Solution code:
from collections import deque 
#スタック
s = deque([])

N,Q = map(int,input().split())
node = [[]for i in range(0,N+1,1)]
for i in range(0,N-1,1):
    a,b = map(int,input().split())
    node[a].append(b)
    node[b].append(a)
node_score = [0]*(N+1)#スコア
for i in range(0,Q,1):
    p,x = map(int,input().split())
    node_score[p] += x

ans = [0]*(N+1)

s.append([1,0])
while len(s) > 0:
    n,preN = s.pop()
    ans[n] = ans[preN]+node_score[n]
    for to in node[n]:
        if to != preN:
            s.append([to,n])

print(" ".join(list(map(str,ans[1:N+1]))))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
input = sys.stdin.readline

def dfs(v,p): #点vについての処理。p：vの親
    if (p != -1): res[v] += res[p]
    
    for e in edges[v]:
        if (e == p): continue
        dfs(e,v)
#--------------------------------
N, Q = map(int, input().split())
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
#print(edges)
px = [list(map(int, input().split())) for _ in range(Q)]

res = [0]*(N+1) #点数リスト
for i in range(Q): #点数リストに初期値を格納
    p,x = px[i]
    res[p] += x

dfs(1,-1)
print(*res[1:])

Submission status: Accepted

Solution code:
import sys

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

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

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))

Submission status: Accepted

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

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
    xx=[0]*n
    for i in range(q):
        xx[p[i]]=xx[p[i]]+x[i]
#ans:100 110 111 110
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
        
#q = deque([0])
stack=[0]
parent=[-1]*n
while stack:
#    print(q)
    state = stack.pop()
#    print("------------- stack:",stack,"state:",state,"g:",g[state])
    for v in g[state]:
#        print("state:",state,"v:",v,"q:",q)
        if parent[state] == v:
            continue
        else:
            parent[v]=state
            stack.append(v)
            xx[v]+=xx[state]
#            print("parent:",parent,"xx:",xx,"stack",stack)

print(" ".join(map(str,xx[0: ])))

Submission status: Accepted

Solution code:

from collections import deque

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
    xx=[0]*n
    for i in range(q):
        xx[p[i]]=xx[p[i]]+x[i]
#ans:100 110 111 110
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
        
#q = deque([0])
stack=[0]
parent=[-1]*n
while stack:
#    print(q)
    state = stack.pop()
#    print("------------- stack:",stack,"state:",state,"g:",g[state])
    for v in g[state]:
#        print("state:",state,"v:",v,"q:",q)
        if parent[state] == v:
            continue
        else:
            parent[v]=state
            stack.append(v)
            xx[v]+=xx[state]
#            print("parent:",parent,"xx:",xx,"stack",stack)

print(" ".join(map(str,xx[0: ])))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline  # これを使わないとTLEしてしまう
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)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for p, x in PX:
    P[p] += x

Count = [0] * (N+1)


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    Count[v] = point + P[v]
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x, v, Count[v])


dfs(1, 0, 0)

res = ' '.join(map(str, Count[1:]))
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.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)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for p, x in PX:
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

Submission status: Accepted

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

seen=[]
#seen=dict()
path=[]

def dfs(g, v,add):
    xx[v]+=add
#    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v,xx[v])
#    path.append(v)

    return

icase=0
if icase==0:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
#        g[ai-1].append(bi-1)
#        g[bi-1].append(ai-1)
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:100 110 111 110

#c=[0]*n

seen=[False]*n
#for i in range(n):
#    seen[i]=False
dfs(g,0,0)

#print(path)

'''
seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()
'''

ans=" ".join(map(str,xx[0:]))
print(ans)

Submission status: Accepted

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

seen=[]
#seen=dict()
path=[]

def dfs(g, v,add):
    xx[v]+=add
#    path.append(v)
    seen[v]=True
    for next_v in g[v]:
        if seen[next_v]:
            continue
        dfs(g, next_v,xx[v])
#    path.append(v)

    return

icase=-1
if icase==-1:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    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 = [set() for _ in range(n)]
    for ai,bi in ab:
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)

    xx=[0]*n
    for pi,xi in px:
        xx[pi-1]=xx[pi-1]+xi
if icase==0:
    n,q=map(int,input().split())
#    g = [deque([]) for _ in range(n)]
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
#        g[ai-1].append(bi-1)
#        g[bi-1].append(ai-1)
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
#ans:100 110 111 110

#c=[0]*n

seen=[False]*n
#for i in range(n):
#    seen[i]=False
dfs(g,0,0)

#print(path)

'''
seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()
'''

ans=" ".join(map(str,xx[0:]))
print(ans)

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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

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

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

ans = [0]*N

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

check = [1]*N
check[0] = 0

q = deque([0])

while q:
	n = q.popleft()
	for node in graph[n]:
		if check[node]:
			ans[node] += ans[n]
			check[node] = 0
			q.append(node)

print(*ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

graph = defaultdict(list)

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

ans = [0]*N

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

check = [1]*N
check[0] = 0

q = deque([0])

while q:
	n = q.popleft()
	for node in graph[n]:
		if check[node]:
			ans[node] += ans[n]
			check[node] = 0
			q.append(node)

print(*ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

graph = defaultdict(list)

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

dic = defaultdict(int)

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

check = [0]*N
check[0] = 1

ans = [0]*N

q = deque([0])

while q:
	n = q.popleft()
	ans[n] += dic[n]
	for node in graph[n]:
		if check[node]:
			continue
		ans[node] += ans[n]
		check[node] = 1
		q.append(node)

print(*ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
	N, Q = MAP()
	ab = [LIST() for _ in range(N-1)]
	px = [LIST() for _ in range(Q)]

	graph = defaultdict(list)

	for a, b in ab:
		graph[a-1].append(b-1)
		graph[b-1].append(a-1)

	dic = defaultdict(int)

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

	ans = [0]*N

	checked = [0]*N
	checked[0] = 1

	q = deque([])
	q.append(0)
	
	while q:
		n = q.popleft()
		ans[n] += dic[n]
		for node in graph[n]:
			if checked[node]:
				continue
			ans[node] += ans[n]
			checked[node] = 1
			q.append(node)

	print(*ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

graph = [[] for _ in range(N)]
for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)
#print(graph)

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

check = [1]*N
check[0] = 0

q = deque([0])

while q:
	p = q.popleft()
	for x in graph[p]:
		if check[x]:
			cnt[x] += cnt[p]
			check[x] = 0
			q.append(x)



print(*cnt)

Submission status: Accepted

Solution code:
n,q=[int(x) for x in input().rstrip().split()]
ab=[[]for j in range(n)]

for i in range(n-1):
  a,b=[int(x) for x in input().rstrip().split()]
  ab[a-1].append(b-1)
  ab[b-1].append(a-1)
cnt=[0]*(n)


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

done=[False]*n
stack=[0]
done[0]=True
while(stack):
  q=stack.pop()
  for i in ab[q]:
    if done[i]==False:
      stack.append(i)
      done[i]=True
      cnt[i]+=cnt[q]

print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

counted = [0] * (N)

queue = deque()
queue.append(0)
#print("links", links)
#print("counter", counter)
while queue:
  v = queue.pop()
  #print("v", v)
  counted[v] = 1
  for q in links[v]:
    if not(counted[q] == 1):
      counter[q] += counter[v]
      queue.append(q)
      #print("q",  q, counter)

print(" ".join([str(i) for i in counter]))

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

tree = defaultdict(set)
for _ in range(1, N):
    a, b = map(int, input().split(' '))
    tree[a].add(b)
    tree[b].add(a)

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

stack = deque([1])
searched = set()

while len(stack) > 0:
    node = stack.popleft()
    searched.add(node)
    for child in tree[node]:
        if child not in searched:
            stack.append(child)
            results[child] += results[node]

print(' '.join([str(result) for result in results[1:]]))

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    n, q = map(int, input().split())
    childs = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        childs[b - 1].append(a - 1)
        childs[a - 1].append(b - 1)
    counter = [0] * n
    for _ in range(q):
        p, x = list(map(int, input().split()))
        counter[p - 1] += x
    ans = [-1] * n
    ans[0] = counter[0]
    q = [(0, x) for x in childs[0]]
    while q:
        p, i = q.pop()
        if ans[i] >= 0:
            continue
        ans[i] = ans[p] + counter[i]
        for j in childs[i]:
            q.append((i, j))
    print(*ans)


if __name__ == '__main__':
    resolve()