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


n, q = map(int, input().split())
tree = [[] for _ in range(n + 1)]
score = [0 for _ in range(n + 1)]

dq = deque()
dq.append((1, 0))

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

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

while(dq):
    k = dq.popleft()
    score[k[0]] += score[k[1]]
    for i in tree[k[0]]:
        if not i == k[1]:
            dq.append((i, k[0]))

print(*score[1:])

Submission status: Accepted

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

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

N,Q = map(int,readline().split())
AB = (tuple(int(x) for x in readline().split()) for _ in range(N-1))
PX = (tuple(int(x) for x in readline().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

par = [None] * (N+1)
q = [1]
while q:
    x = q.pop()
    for y in graph[x]:
        if y == par[x]:
            continue
        value[y] += value[x]
        q.append(y)
        par[y] = x

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

Submission status: Accepted

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

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

N,Q = map(int,readline().split())
AB = [tuple(int(x) for x in readline().split()) for _ in range(N-1)]
PX = [tuple(int(x) for x in readline().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

par = [None] * (N+1)
q = [1]
while q:
    x = q.pop()
    for y in graph[x]:
        if y == par[x]:
            continue
        value[y] += value[x]
        q.append(y)
        par[y] = x

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

Submission status: Accepted

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

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

N,Q = map(int,readline().split())
lines = readlines()
AB = (tuple(int(x) for x in line.split()) for line in lines[:N-1])
PX = (tuple(int(x) for x in line.split()) for line in lines[-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

par = [None] * (N+1)
q = [1]
while q:
    x = q.pop()
    for y in graph[x]:
        if y == par[x]:
            continue
        value[y] += value[x]
        q.append(y)
        par[y] = x

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

Submission status: Accepted

Solution code:
import collections

n, q = map(int, input().split())
cnt = [0] * (n + 1)

# adjacency list for tree graph
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)

# calc cnt
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:
def main():
    import sys
    import sys
    sys.setrecursionlimit(10 ** 7)
    input=sys.stdin.readline
    N,Q = map(int,input().split())
    AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
    PX = [[x for x in map(int,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
    for p,x in PX:
        cnt[p-1] += x
    
    color = ["WHITE"] * N
    def dfs(u):
        color[u-1] = "GRAY"
        for u_next in G[u]:
            if color[u_next-1] == "WHITE":
                cnt[u_next-1] += cnt[u-1]
                dfs(u_next)
        color[u-1] == "BLACK"

    dfs(1)
    print(*cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n, q = f.read_int_list()
    g = collections.defaultdict(list)
    for _ in xrange(n-1):
        a, b = f.read_int_list()
        g[a].append(b)
        g[b].append(a)

    c = [0] * (n+1)

    for _ in xrange(q):
        p, x = f.read_int_list()
        c[p] += x

    vis = [False] * (n+1)
    que = [(1, 0)]
    while len(que) > 0:
        vi, vp = que.pop()
        vis[vi] = True
        c[vi] += c[vp]
        for vii in g[vi]:
            if not vis[vii]:
                que.append((vii, vi))

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


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, qq = list(map(int, input().rstrip('\n').split()))

    ls = collections.defaultdict(list)
    ls[1]
    for i in range(n-1):
        a, b = map(int, input().rstrip('\n').split())
        ls[a] += [b]
        ls[b] += [a]

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

    q = collections.deque()
    q.append(1)
    fq = collections.defaultdict(list)
    while True:
        if len(q) != 0:
            p = q.popleft()
            fq[p]
            for i in ls[p]:
                if i not in fq:
                    q.append(i)
                    ans[i-1] += ans[p-1]
        else:
            break
    print(*ans)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, qq = list(map(int, input().rstrip('\n').split()))

    ls = collections.defaultdict(list)
    ls[1]
    for i in range(n-1):
        a, b = map(int, input().rstrip('\n').split())
        ls[a] += [b]
        ls[b] += [a]

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

    q = collections.deque()
    q.append(1)
    fq = collections.defaultdict(list)
    while True:
        if len(q) != 0:
            p = q.popleft()
            fq[p]
            for i in ls[p]:
                if i not in fq:
                    q.append(i)
                    ans[i-1] += ans[p-1]
        else:
            break
    print(*ans)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, qq = list(map(int, input().rstrip('\n').split()))

    ls = collections.defaultdict(list)
    ls[1]
    for i in range(n-1):
        a, b = list(map(int, input().rstrip('\n').split()))
        ls[a] += [b]
        ls[b] += [a]

    ans = [0 for _ in range(n)]
    for i in range(qq):
        p, x = list(map(int, input().rstrip('\n').split()))
        ans[p-1] += x

    q = collections.deque()
    q.append(1)
    fq = collections.defaultdict(list)
    while True:
        if len(q) != 0:
            p = q.popleft()
            fq[p]
            for i in ls[p]:
                if i not in fq:
                    q.append(i)
                    ans[i-1] += ans[p-1]
        else:
            break
    print(*ans)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

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

#B
def B():
    II()
    a = LI()
    ans = 0
    for ai in a:
        ans += 1 / ai
    print(1/ans)
    return

#C
def C():
    n = II()
    v = LI()
    q = []
    for vi in v:
        heappush(q, vi)
    while 1:
        a = heappop(q)
        if q:
            b = heappop(q)
            heappush(q, (a + b) / 2)
        else:
            print(a)
            return

#D
def D():
    n, q = LI()
    tree = [[] for i in range(n)]
    for _ in range(n - 1):
        a, b = LI_()
        tree[a].append(b)
        tree[b].append(a)
    ans = [0] * n
    c = defaultdict(int)
    for _ in range(q):
        p, x = LI_()
        x += 1
        ans[p] += x
    c[0] = 1
    q = deque([0])
    while q:
        p = q.pop()
        for nex in tree[p]:
            if c[nex]:
                continue
            c[nex] += 1
            ans[nex] += ans[p]
            q.append(nex)
    print(*ans)
    return

#E
def E():
    return

#F
def F():
    return

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

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

#B
def B():
    II()
    a = LI()
    ans = 0
    for ai in a:
        ans += 1 / ai
    print(1/ans)
    return

#C
def C():
    n = II()
    v = LI()
    q = []
    for vi in v:
        heappush(q, vi)
    while 1:
        a = heappop(q)
        if q:
            b = heappop(q)
            heappush(q, (a + b) / 2)
        else:
            print(a)
            return

#D
def D():
    n, q = LI()
    tree = [[] for i in range(n)]
    for _ in range(n - 1):
        a, b = LI_()
        tree[a].append(b)
        tree[b].append(a)
    ans = [0] * n
    c = defaultdict(int)
    for _ in range(q):
        p, x = LI_()
        x += 1
        ans[p] += x
    c[0] = 1
    q = deque([0])
    while q:
        p = q.pop()
        for nex in tree[p]:
            if c[nex]:
                continue
            c[nex] += 1
            ans[nex] += ans[p]
            q.appendleft(nex)
    print(*ans)
    return

#E
def E():
    return

#F
def F():
    return

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

Submission status: Accepted

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

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

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)

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

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

def dfs(n,r):
    for i in T[n]:
        if i!=r:
            O[i]+=O[n]

            dfs(i,n)

dfs(0,-1)

print(*O)

Submission status: Accepted

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

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

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)

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

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

def dfs(n):
    for i in T[n]:
        if r[i]:continue
        r[i]=1
        O[i]+=O[n]
        dfs(i)

r=[1]+[0]*(N-1)

dfs(0)

print(*O)

Submission status: Accepted

Solution code:
#D
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=[0]*(n+1)
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
done=[0]*(n+1)
while h:
    a=h.pop()
    for l in data[a]:
        if done[l]==0:
            counter[l]+=counter[a]
            h.append(l)
    done[a]=1
print(*counter[1:])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q = [int(x) for x in input().split()]
E ={i: [] for i in range(1, N+1)}
q = []
for _ in range(N-1):
  u,v = [int(x) for x in input().split()]
  E[u].append(v)
  E[v].append(u)
for _ in range(Q):
  u,v = [int(x) for x in input().split()]
  q.append((u,v))
ans = [0]*(N)
for i in range(Q):
  ans[q[i][0]-1] += q[i][1]
stk = [1]
memo = [0]*(N)
while stk:
  l = stk.pop()
  if type(l) is int:
    l = [l]
  for i in l:
    if memo[i-1]!=0:
      continue
    memo[i-1]=1
    for j in E[i]:
      if memo[j-1]==0:
        #print(i,j)
        ans[j-1] += ans[i-1]
    stk.append(E[i])
    #print(stk)
print(*ans)

Submission status: Accepted

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


def dfs(v, x, G, X, visited, ans):
    visited[v] = True
    ans[v] = x
    # print(visited)

    for nv in G[v]:
        if visited[nv]:
            continue
        dfs(nv, x+X[nv], G, X, visited, ans)


def main():
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ 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 _ in range(Q):
        p, x = map(int, input().split())
        X[p-1] += x
    # print(G)
    # print(X)
    
    visited = [False]*N
    ans = [0]*N
    dfs(0, X[0], G, X, visited, ans)
    print(' '.join(list(map(str, ans))))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n,q=[int(_) for _ in input().split()]
ki=[[] for _ in range(n)]
ans=[0]*n
 
def dfs(numQ,parent):
    for child in ki[numQ]:
        if child==parent:
            continue
        ans[child]+=ans[numQ]
        dfs(child,numQ)
 
for i in range(n-1):
    a,b=[int(_) for _ in input().split()]
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
 
for i in range(q):
    p,x=[int(_) for _ in input().split()]
    ans[p-1]+=x
 
dfs(0,-1)
print(*ans)

Submission status: Accepted

Solution code:
n, q = list(map(int, input().split()))
nodes = [[] for _ in range(n)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    nodes[ai-1].append(bi-1)
    nodes[bi-1].append(ai-1)
    
cnts = [0]*n
for _ in range(q):
    pi, xi = list(map(int, input().split()))
    cnts[pi-1] += xi
    
stack = []
visited = set()
stack.append(0)
while stack:
    current = stack.pop(-1)
    visited.add(current)
    for j in nodes[current]:
        if j in visited:
            continue
        cnts[j] += cnts[current]
        stack.append(j)
        
print(*cnts)

Submission status: Accepted

Solution code:
# def main():
#     N, Q = list(map(int, input().split()))
#     parents = [[] for i in range(N+1)]
#     ans = [0] * (N+1)

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

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

#     print(parents[1:])

#     for i in range(1, N+1):
#         for p in parents[i]:
#             ans[i] += ans[p]

#     print(*ans[1:])

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    tree = [[] for i in range(N+1)]
    ans = [0] * (N+1)
    visit = [False]*(N+1)

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

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

    visit[1] = True
    q = [1]

    while len(q) != 0:
        n = q.pop()
        # print(tree[n])
        for i in tree[n]:
            if visit[i] is False:
                ans[i] += ans[n]
                # print(i, '+=', n)
                visit[i] = True
                q.append(i)

    print(*ans[1:])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import queue
input = sys.stdin.readline
N, Q = map(int, input().split())
 
tree = [[] for i in range(N+1)]
values = [0] * (N+1)
visit = [False]*(N+1)
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
 
for _ in range(Q):
    p, x = map(int, input().split())
    values[p] += x
 
 
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]:
            values[next] += values[now]
            visit[next] = True
            q.put(next)
 
values = values[1:]
print(" ".join(map(str, values)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import collections
N,Q = map(int,input().split())
Graph = [[] for i in range(N + 1)]

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

counter = [0] * (N + 1)

for i in range(Q): #counterに値を入れていく．
    a,b = map(int,input().split())
    counter[a] += b

seen = [False] * (N + 1)
todo = collections.deque()

seen[1] = True
todo.append(1)

while len(todo) != 0:
    v = todo.pop()
    for next_v in Graph[v]:
        if seen[next_v]:
            continue
        seen[next_v] = True
        todo.append(next_v)
        counter[next_v] += counter[v]

print(*counter[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n,q=[int(_) for _ in input().split()]
ki=[[] for _ in range(n)]
ans=[0]*n

def dfs(numQ,parent):
    for child in ki[numQ]:
        if child==parent:
            continue
        ans[child]+=ans[numQ]
        dfs(child,numQ)

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

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

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

Submission status: Accepted

Solution code:
import collections

def main():
    N, Q = map(int, input().split())
    saw_list = [False] * (N+1)
    relation = [[] for _ in range(N+1)]
    values = [0] * (N+1)

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

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

    deque = collections.deque()
    deque.append(1)
    saw_list[1] = True
    while deque:
        node = deque.pop()
        for val in relation[node]:
            if not saw_list[val]:
                deque.append(val)
                values[val] += values[node]
                saw_list[val] = True

    ret = ""
    for i in range(1, len(values)):
        ret += str(values[i]) + " "
    print(ret)

main()

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

n, q = [int(x) for x in input().split()]

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

counter = [0] * n

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

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

parent = [0]
set_parent = {0}
for i in parent:
    for v in edge[i]:
        if v in set_parent:
            continue
        set_parent.add(v)
        parent.append(v)
        counter[v] += counter[i]
        
print(" ".join(map(str, counter)))

Submission status: Accepted

Solution code:

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

# edge = [[] for _ in range(n)]

# counter = [0] * n

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

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

# parent = [0]
# visited = []

# for i in parent:
#     visited.append(i)
#     for v in edge[i]:
#         if v in visited:
#             continue
#         parent.append(v)
#         counter[v] += counter[i]
        
# for i in range(n):
#     print(counter[i], end=" ")
# print("")

import sys
input = sys.stdin.readline
 
N, Q = [int(x) for x in input().split()]
 
edge = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
 
cost = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    cost[p - 1] += x
 
next = [0]
s_next = {0}
for i in next:
    for v in edge[i]:
        if v in s_next:
            continue
        s_next.add(v)
        next.append(v)
        cost[v] += cost[i]
 
print(" ".join(map(str, cost)))

Submission status: Accepted

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

def g(ab: list, ans: list, check: list, i: int = 0):
    if len(ab[i]) == 1 and i != 0:
        return
    check[i] = False
    for j in ab[i]:
        if check[j]:
            ans[j] += ans[i]
            g(ab, ans, check, j)

def main():
    N, Q = map(int, input().split())
    ab = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    ans = [0] * N
    check = [True] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
    g(ab, ans, check)
    print(' '.join(list(map(str, ans))))
    

if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
lp=[0]#リストをスタックとして用いる
#lp=collections.deque([0])#デキューをスタックorキューとして用いる
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    p=lp.pop()#リスト・デキューをスタックとして使う
    #p=lp.popleft()#デキューをキューとして使う
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])

Submission status: Accepted

Solution code:
import collections
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
#lp=[0]
lp=collections.deque([0])
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    #p=lp.pop()
    p=lp.popleft()
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])
#スタックだとリストかデキューかは関係ない

Submission status: Accepted

Solution code:
import collections
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
#lp=[0]
lp=collections.deque([0])
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    p=lp.pop()
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])

Submission status: Accepted

Solution code:
#import collections
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
lp=[0]
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    p=lp.pop()
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])

Submission status: Accepted

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

def main():
    N,Q = map(int, input().split())

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

    P = []
    for i in range(Q):
        x,y = map(int, input().split())
        P.append((x,y))

    V = [0]*N
    for p in P:
        V[p[0]-1] += p[1]

    parent = {1}
    done = {1}
    while parent:
        children = set()
        for p in parent:
            for i in edge[p]:
                if i not in done:
                    V[i-1] += V[p-1]
                    children.add(i)
                    done.add(i)
        parent = children

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

P = []
for i in range(Q):
    x,y = map(int, input().split())
    P.append((x,y))

V = [0]*N
for p in P:
    V[p[0]-1] += p[1]

parent = {1}
done = {1}
while parent:
    children = set()
    for p in parent:
        for i in edge[p]:
            if i not in done:
                V[i-1] += V[p-1]
                children.add(i)
                done.add(i)
    parent = children

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

Submission status: Accepted

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

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

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

P = []
for i in range(Q):
    x,y = map(int, input().split())
    P.append((x,y))

V = [0]*N
for p in P:
    V[p[0]-1] += p[1]

parent = {1}
done = {1}
while parent:
    children = set()
    for p in parent:
        for i in edge[p]:
            if i not in done:
                V[i-1] += V[p-1]
                children.add(i)
                done.add(i)
    parent = children

print(*V)

Submission status: Accepted

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

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

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

P = []
for i in range(Q):
    x,y = map(int, input().split())
    P.append((x,y))

V = [0]*N
for p in P:
    V[p[0]-1] += p[1]

parent = {1}
done = {1}
while parent:
    children = set()
    for p in parent:
        child = set()
        for i in edge[p]:
            if i not in done:
                V[i-1] += V[p-1]
                child.add(i)
                done.add(i)
        children |= child
    parent = children

print(*V)

Submission status: Accepted

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

import sys

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

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

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, p, add):
    value[v] += add
    for x in graph[v]:
        if x == p:
            continue
        dfs(x, v, value[v])


dfs(1, 0, 0)

ans = value[1:]
print(*ans)