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: Wrong Answer

Solution code:
n,q=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
for i in range(n-1,0,-1):
    m=min(edge[i])
    for j in edge[i]:
        if j!=m and (not j in edge[m]):
            edge[m].append(j)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
    for j in edge[p-1]:
        if j<p-1:
            continue
        ans[j]+=x
print(*ans)

Submission status: Wrong Answer

Solution code:
import collections

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

value = [0] * (n+1)

connected = [set() for i in range(n+1)]

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

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

queue = collections.deque(connected[1])

for i in queue:
  value[i] += value[1]
  value[i] = -value[i]

value[1] = -value[1]

while queue:
  s = queue.popleft()
  v = value[s]
  for i in connected[s]:
    vi = value[i]
    if vi <= 0:
      value[i] = -(vi-v)
      queue.append(i)
    
print(' '.join(str(i) for i in value[1:]))

Submission status: Wrong Answer

Solution code:
n,q=map(int, input().split())
go_list=[[] for i in range(n+1)]
cnt=[0]*(n+1)
Oya=[False]*(n+1)
Oya[1]=True
for i in range(n-1):
    a,b=map(int, input().split())
    if Oya[a]:
        go_list[a].append(b)
        Oya[b]=True
    elif Oya[b]:
        go_list[b].append(a)
        Oya[a]=True


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

from collections import deque
que=deque()

que.append(1)

while que:
    ne=que.popleft()
    for i in go_list[ne]:
        cnt[i]+=cnt[ne]
        que.append(i)

cnt.pop(0)
print(*cnt)

Submission status: Wrong Answer

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

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

from collections import deque
que=deque()

que.append(1)

while que:
    ne=que.popleft()
    for i in go_list[ne]:
        cnt[i]+=cnt[ne]
        que.append(i)

cnt.pop(0)
print(*cnt)

Submission status: Wrong Answer

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

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

from collections import deque
que=deque()

que.append(1)

while que:
    ne=que.popleft()
    for i in go_list[ne]:
        cnt[i]+=cnt[ne]
        que.append(i)

ans=str(cnt[1])
for i in range(2,n+1):
    ans+=" "+str(cnt[i])
print(ans)

Submission status: Wrong Answer

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

from collections import deque

que=deque()

for i in range(q):
    p,x=map(int, input().split())
    cnt[p]+=x
    for j in go_list[p]:
        que.append(j)
    while que:
        a=que.popleft()
        cnt[a]+=x
        for j in go_list[a]:
            que.append(j)

ans=str(cnt[i])
for i in range(2,n+1):
    ans+=" "+str(cnt[i])
print(ans)

Submission status: Wrong Answer

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)]
ans = [0]*n
for i in range(q):
    ans[px[i-1][0]-1] += px[i-1][1]
ab.sort()
for i in range(n-1):
    ans[ab[i][1]-1] += ans[ab[i][0]-1]
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
import math

#https://atcoder.jp/contests/agc008/submissions/15248942
sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

counts = []

class Node:
    def __init__(self):
        self.child = []
        self.count = 0

def dfs(tree,node,p_count):
    count = tree[node].count + p_count
    counts[node] = count
    for x in tree[node].child:
        if x == node:
            continue
        dfs(tree,x,count)

N,Q = inm()

tree = []
for _ in range(N):
    tree.append(Node())

#node = Node()
#tree = [node]*N

for _ in range(N-1):
    a,b = inm()
    tree[a-1].child.append(b-1)

for _ in range(Q):
    p,x = inm()
    tree[p-1].count += x

for _ in range(N):
    counts.append(0)

dfs(tree,0,0)

counts_str = [str(n) for n in counts]
s = " ".join(counts_str)
print(s)

Submission status: Wrong Answer

Solution code:
import sys
import math

#https://atcoder.jp/contests/agc008/submissions/15248942
sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

counts = []

class Node:
    def __init__(self):
        self.child = []
        self.count = 0

def dfs(tree,node,p_count):
    count = tree[node].count + p_count
    counts[node] = count
    for x in tree[node].child:
        dfs(tree,x,count)

N,Q = inm()

tree = []
for _ in range(N):
    tree.append(Node())

#node = Node()
#tree = [node]*N

for _ in range(N-1):
    a,b = inm()
    tree[a-1].child.append(b-1)

for _ in range(Q):
    p,x = inm()
    tree[p-1].count += x

for _ in range(N):
    counts.append(0)

dfs(tree,0,0)

counts_str = [str(n) for n in counts]
s = " ".join(counts_str)
print(s)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, Q = map(int,input().split())
Tree = defaultdict(list)
hasParent = set()
for i in range(N-1):
  a, b = map(int,input().split())
  if b not in hasParent:
    Tree[a].append(b)
    hasParent.add(b)
    
  else:
    Tree[b].append(a)
    hasParent.add(a)
ans = [0]*(N+1)
for i in range(Q):
  a, x = map(int,input().split())
  ans[a]+=x
stack = [1]
while stack:
  root = stack.pop()
  lst = Tree[root]
  x = ans[root]
  for val in lst:
    ans[val]+=x
  stack+=lst
print(" ".join(map(str,ans[1:])))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, Q = map(int,input().split())
Tree = defaultdict(list)
for i in range(N-1):
  a, b = map(int,input().split())
  Tree[a].append(b)
ans = [0]*(N+1)
for i in range(Q):
  a, x = map(int,input().split())
  ans[a]+=x
stack = [1]
while stack:
  root = stack.pop()
  lst = Tree[root]
  x = ans[root]
  for val in lst:
    ans[val]+=x
  stack+=lst
print(" ".join(map(str,ans[1:])))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, Q = map(int,input().split())
Tree = defaultdict(list)
for i in range(N-1):
  a, b = map(int,input().split())
  Tree[a].append(b)
ans = [0]*(N+1)
for i in range(Q):
  a, x = map(int,input().split())
  ans[a]+=x
for i in range(1,N+1):
  lst = Tree[i]
  x = ans[i]
  for val in lst:
    ans[val]+=x
print(" ".join(map(str,ans[1:])))

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
score=[0]*N
d=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    d[min(a,b)].append(max((a,b)))

for i in range(N):
    for j in range(len(d[i])):
        d[i]+=d[d[i][j]]

for i in range(Q):
    p,q=map(int,input().split())
    p-=1
    score[p]+=q
    for j in d[p]:
        score[j]+=q
print(*score)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q=map(int,input().split())
trees=[0 for _ in range(N)]
numbers=[]
for _ in range(N-1):
    a,b=map(int,input().split())
    numbers.append([a,b])
numbers=deque(numbers)
while numbers:
    number=numbers.popleft()
    a=number[0]
    b=number[1]
    if a!=1 and trees[a-1]==0 and trees[b-1]==0:
        numbers.append([a,b])
    elif trees[b-1]==0:
        trees[b-1]=a
    else:
        trees[a-1]=b
answers=[0 for _ in range(N)]
for _ in range(Q):
    p,x=map(int,input().split())
    answers[p-1]+=x
answers_dict={}
for n in range(N):
    answers_dict[n]=trees[n]
sort_answers=sorted(answers_dict.items(), key=lambda x:x[1])
for n in range(N):
    num=sort_answers[n][0]
    if trees[num]==0:
        continue
    answers[num]+=answers[sort_answers[n][1]-1]
print(*answers)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
trees=[0 for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    if trees[b-1]==0:
        trees[b-1]=a
    else:
        trees[a-1]=b
answers=[0 for _ in range(N)]
for _ in range(Q):
    p,x=map(int,input().split())
    answers[p-1]+=x
answers_dict={}
for n in range(N):
    answers_dict[n]=trees[n]
sort_answers=sorted(answers_dict.items(), key=lambda x:x[1])
for n in range(N):
    num=sort_answers[n][0]
    if trees[num]==0:
        continue
    answers[num]+=answers[sort_answers[n][1]-1]
print(*answers)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
trees=[0 for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    trees[b-1]=a
answers=[0 for _ in range(N)]
for _ in range(Q):
    p,x=map(int,input().split())
    answers[p-1]+=x
for n in range(N):
    if trees[n]==0:
        continue
    answers[n]+=answers[trees[n]-1]
print(*answers)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
trees=[0 for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    trees[b-1]=a
answers=[0 for _ in range(N)]
for _ in range(Q):
    p,x=map(int,input().split())
    answers[p-1]+=x
for n in range(N):
    if trees[n]==0:
        continue
    answers[n]+=answers[trees[n]-1]
for answer in answers:
    print(answer)

Submission status: Wrong Answer

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

for i in range(N):
    for j in range(len(d[i])):
        d[i]+=d[d[i][j]]

for i in range(Q):
    p,q=map(int,input().split())
    p-=1
    score[p]+=q
    for j in d[p]:
        score[j]+=q
print(*score)

Submission status: Wrong Answer

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b の方が根に近いとき
    else:
        G[b].append(a)
    root.add(b)
lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))
        
cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
seen = [False]*N
def dfs(v):
    seen[v] = True# v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)

Submission status: Wrong Answer

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b が根と繋がっているとき
    else:
        G[b].append(a)
    if a == 0:
        root.add(b)
lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))
        
cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
seen = [False]*N
def dfs(v):
    seen[v] = True# v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)

Submission status: Wrong Answer

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b の方が根に近いとき
    else:
        G[b].append(a)
    root.add(b)

lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
def dfs(v):
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)

Submission status: Wrong Answer

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b の方が根に近いとき
    else:
        G[b].append(a)
    root.add(b)

lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
seen = [False]*N
def dfs(v):
    seen[v] = True# v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)

Submission status: Wrong Answer

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**6)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b が根と繋がっているとき
    else:
        G[b].append(a)
    if a == 0:
        root.add(b)

lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

cnt = [0]*N
def dfs(v,point):
    cnt[v] += point
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        dfs(next_v,point)

for p,x in lst:
    dfs(p,x)
print(*cnt)

Submission status: Wrong Answer

Solution code:
# D - Ki
import sys
sys.setrecursionlimit(10**6)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)

lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

seen = [False]*N
cnt = [0]*N
def dfs(v,point,seen):
    seen[v] = True# v を訪問済みにする
    cnt[v] += point
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        dfs(next_v,point,seen)

for p,x in lst:
    seenC = seen.copy()
    dfs(p,x,seenC)
print(*cnt)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

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)
add = [0]*n
for _ in range(q):
    pp, xx = map(int, input().split())
    add[pp-1] += xx
print(add)


def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in ab[v]:
        if c == p:
            continue
        dfs(c, v, value)


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

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)
p, x = [], []
px = dict()
for _ in range(q):
    pp, xx = map(int, input().split())
    p.append(pp-1)
    x.append(xx)
    px[pp-1] = xx


def dfs(now):
    for i in ab[now]:
        if d[i] == -1:
            d[i] = d[now]+1
            dfs(i)


d = [-1]*n
d[0] = 0
dfs(0)
ans = [0]*n
for i in range(len(p)):
    for j in range(n):
        if d[j] >= d[p[i]]:
            ans[j] += x[i]

print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

node = [[] for _ in range(n+1)]
counter = [0 for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
point_dic = defaultdict(int)

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

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

def dfs(now,before):
    global counter
    global visited

    if visited[now]:
        return
    
    if point_dic[now]:
        point = point_dic[now]+before
    else:
        point = before
    
    visited[now] = 1
    counter[now] += point

    for i in node[now]:
        if visited[i]:
            continue

        dfs(i,point)

dfs(1,0)

print(counter[1:])

Submission status: Wrong Answer

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

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

ans = [0] * N
for i in range(1, N + 1):
    ans[i-1] = s[i] + ans[t[i]-1]
    print(ans[i-1])

Submission status: Wrong Answer

Solution code:
def abc138d_ki():
    import heapq
    n, q = map(int, input().split())
    cnt = [0] * n
    graph = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        graph[a - 1].append(b - 1)
    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p - 1] += x
    qu = [(0, 0)]
    heapq.heapify(qu)
    while len(qu) != 0:
        h, no = heapq.heappop(qu)
        for nxt in graph[no]:
            cnt[nxt] += cnt[no]
            heapq.heappush(qu, (h + 1, nxt))
    for c in cnt:
        print(c, end=' ')


abc138d_ki()

Submission status: Wrong Answer

Solution code:
def abc138d_ki():
    from collections import deque
    n, q = map(int, input().split())
    cnt = [0] * n
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        graph[a-1].append(b-1)
    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p-1] += x
    qu = deque([0])
    while len(qu) != 0:
        no = qu.popleft()
        for nxt in graph[no]:
            cnt[nxt] += cnt[no]
            qu.append(nxt)
    for c in cnt:
        print(c, end=' ')
abc138d_ki()

Submission status: Wrong Answer

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

stack=deque([0])
visited=[0]*n
visited[0]=1

while stack:
    cur=stack[-1]
    for i in tree[cur]:
        if visited[i]==0:
            cnt[i]+=cnt[cur]
            stack.append(i)
            visited[i]=1
            break
    else:
        stack.pop()

print(cnt)

Submission status: Wrong Answer

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

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

t = dict()
for i in range(1, n+1):
    t[i] = []
for a, b in ab:
    t[a].append(b)

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

def solve(p):
    for c in t[p]:
        cnt[c-1] += cnt[p-1]
        solve(c)
solve(1)
print(*cnt, sep=' ')

Submission status: Wrong Answer

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

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

#n = 2*10**5
#ab = [[i, i+1] for i in range(1, n)]
#q = 2*10**5
#px = [[1, 10] for _ in range(q)]

t = dict()
for i in range(1, n+1):
    t[i] = [[], 0]
for a, b in ab:
    t[a][0].append(b)

def solve(p, x):
    if t[p][0] == []:
        t[p][1] += x
        return
    t[p][1] += x
    for c in t[p][0]:
        solve(c, x)

for p, x in px:
    solve(p, x)
print(*[a[1] for a in t.values()], sep=' ')

Submission status: Wrong Answer

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

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

#n = 2*10**5
#ab = [[i, i+1] for i in range(1, n)]
#q = 2*10**5
#px = [[1, 10] for _ in range(q)]

t = dict()
for i in range(1, n+1):
    t[i] = [[], 0]
for a, b in ab:
    t[a][0].append(b)

def solve(p, x):
    if t[p][0] == []:
        t[p][1] += x
        return
    t[p][1] += x
    print(t[p][0])
    for c in t[p][0]:
        solve(c, x)

for p, x in px:
    solve(p, x)
print(*[a[1] for a in t.values()], sep=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

link = [[] for _ in range(N)]
for i in range(N-1):
    link[A[i][0]-1].append(A[i][1]-1)
    link[A[i][1]-1].append(A[i][0]-1)

dist = [-1 for _ in range(N)]
ans = [0 for _ in range(N)]
parent = [0 for _ in range(N)]
dist[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(len(link[now])):
        if dist[link[now][i]] == -1:
            dist[link[now][i]] = now + 1
            d.append(link[now][i])
            parent[link[now][i]] = now

for i in range(Q):
    ans[P[i][0] - 1] += P[i][1]

arg_dist = list(np.argsort(np.array(dist)))
for i in range(N):
    if i != 0:
        ans[arg_dist[i]] = ans[arg_dist[i]] + ans[parent[arg_dist[i]]]

for i in range(N):
    if i != N - 1:
        print(ans[i], end=" ")
    else:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

link = [[] for _ in range(N)]
for i in range(N-1):
    link[A[i][0]-1].append(A[i][1]-1)
    link[A[i][1]-1].append(A[i][0]-1)

dist = [-1 for _ in range(N)]
ans = [0 for _ in range(N)]
parent = {}
dist[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(len(link[now])):
        if dist[link[now][i]] == -1:
            dist[link[now][i]] = now + 1
            d.append(link[now][i])
            parent[link[now][i]] = now

'''
for i in range(Q):
    ans[P[i][0] - 1] += P[i][1]

arg_dist = list(np.argsort(np.array(dist)))
for i in range(N):
    if i != 0:
        ans[arg_dist[i]] = ans[arg_dist[i]] + ans[parent[arg_dist[i]]]
'''
for i in range(N):
    if i != N - 1:
        print(ans[i], end=" ")
    else:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

link = [[] for _ in range(N)]
for i in range(N-1):
    link[A[i][0]-1].append(A[i][1]-1)
    link[A[i][1]-1].append(A[i][0]-1)

dist = [-1 for _ in range(N)]
ans = [0 for _ in range(N)]
parent = {}
dist[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(len(link[now])):
        if dist[link[now][i]] == -1:
            dist[link[now][i]] = now + 1
            d.append(link[now][i])
            parent[link[now][i]] = now


for i in range(Q):
    ans[P[i][0] - 1] += P[i][1]

arg_dist = list(np.argsort(np.array(dist)))
for i in range(N):
    if i != 0:
        ans[arg_dist[i]] = ans[arg_dist[i]] + ans[parent[arg_dist[i]]]

for i in range(N):
    if i != N - 1:
        print(ans[i], end=" ")
    else:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

dist = [-1 for _ in range(N)]
ans = [0 for _ in range(N)]
parent = {}
dist[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(N-1):
        if A[i][0] - 1 == now and dist[A[i][1] - 1] == -1:
            dist[A[i][1] - 1] = now + 1
            d.append(A[i][1] - 1)
            parent[A[i][1] - 1] = dist[A[i][0] - 1]

        if A[i][1] - 1 == now and dist[A[i][0] - 1] == -1:
            dist[A[i][0] - 1] = now + 1
            d.append(A[i][0] - 1)
            parent[A[i][0] - 1] = dist[A[i][1] - 1]
'''
for i in range(Q):
    ans[P[i][0] - 1] += P[i][1]

arg_dist = list(np.argsort(np.array(dist)))
for i in range(N):
    if i != 0:
        ans[arg_dist[i]] = ans[arg_dist[i]] + ans[parent[arg_dist[i]]]
'''
for i in range(N):
    if i != N - 1:
        print(ans[i], end=" ")
    else:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

dist = [-1 for _ in range(N)]
ans = [0 for _ in range(N)]
parent = {}
dist[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(N-1):
        if A[i][0] - 1 == now and dist[A[i][1] - 1] == -1:
            dist[A[i][1] - 1] = now + 1
            d.append(A[i][1] - 1)
            parent[A[i][1] - 1] = dist[A[i][0] - 1]

        if A[i][1] - 1 == now and dist[A[i][0] - 1] == -1:
            dist[A[i][0] - 1] = now + 1
            d.append(A[i][0] - 1)
            parent[A[i][0] - 1] = dist[A[i][1] - 1]

for i in range(Q):
    ans[P[i][0] - 1] += P[i][1]

arg_dist = list(np.argsort(np.array(dist)))
for i in range(N):
    if i != 0:
        ans[arg_dist[i]] = ans[arg_dist[i]] + ans[parent[arg_dist[i]]]

for i in range(N):
    if i != N - 1:
        print(ans[i], end=" ")
    else:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

dist = [-1 for _ in range(N)]
ans = [0 for _ in range(N)]
parent = [[] for _ in range(N)]
dist[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(N-1):
        if A[i][0] - 1 == now and dist[A[i][1] - 1] == -1:
            dist[A[i][1] - 1] = now + 1
            d.append(A[i][1] - 1)
            parent[A[i][1] - 1].append(dist[A[i][0] - 1])

        if A[i][1] - 1 == now and dist[A[i][0] - 1] == -1:
            dist[A[i][0] - 1] = now + 1
            d.append(A[i][0] - 1)
            parent[A[i][0] - 1].append(dist[A[i][1] - 1])


for i in range(Q):
    ans[P[i][0] - 1] += P[i][1]

arg_dist = list(np.argsort(np.array(dist)))
for i in range(N):
    for j in range(len(parent[arg_dist[i]])):
        ans[arg_dist[i]] = ans[arg_dist[i]] + ans[parent[arg_dist[i]][j]]

for i in range(N):
    if i != N - 1:
        print(ans[i], end=" ")
    else:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

dist = [-1 for _ in range(N)]
ans = [0 for _ in range(N)]
parent = [[] for _ in range(N)]
dist[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(N-1):
        if A[i][0] - 1 == now and dist[A[i][1] - 1] == -1:
            dist[A[i][1] - 1] = now + 1
            d.append(A[i][1] - 1)
            parent[A[i][1] - 1].append(dist[A[i][0] - 1])

        if A[i][1] - 1 == now and dist[A[i][0] - 1] == -1:
            dist[A[i][0] - 1] = now + 1
            d.append(A[i][0] - 1)
            parent[A[i][0] - 1].append(dist[A[i][1] - 1])

arg_dist = np.argsort(np.array(dist))

for i in range(Q):
    ans[P[i][0] - 1] += P[i][1]

for i in range(N):
    for j in range(len(parent[arg_dist[i]])):
        ans[arg_dist[i]] = ans[arg_dist[i]] + ans[parent[arg_dist[i]][j]]

for i in range(N):
    if i != N - 1:
        print(ans[arg_dist[i]], end=" ")
    else:
        print(ans[arg_dist[i]])

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(tree, cost, root):
    q = deque([root])
    dist = [0]*N

    dist[root] = cost[root]

    while q:
        v = q.pop()
        for n_v in tree[v]:
            dist[n_v] = dist[v] + cost[n_v]
            q.append(n_v)

    return dist

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]

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

pts = [0]*N

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

dist = dfs(tree, pts, 0)

for i in range(N):
    print(dist[i])

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/abc138/tasks/abc138_d
#再帰の限度を拡張
import sys
sys.setrecursionlimit(1000000)


#入力受付
N,Q = map(int, input().split())

connection_dict = {i:set() for i in range(1,N+1)}

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

#一個ずつ操作する必要はないので、まとめて実施する
#入力受付
px_list = [0 for i in range(0,N+1)]
for i in range(Q):
    p,x = map(int, input().split())
    px_list[p] += x

#実施
ans = [0 for _ in range(0,N+1)]
#1から始めて下流に値を流していく
def add_counter(node,from_upstream):
    ans[node] = from_upstream + px_list[node]
    for downstream in connection_dict[node]:
        add_counter(downstream,ans[node])

add_counter(1,0)

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