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:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    edge = [[] for _ in range(N)]
    for i in ab:
        edge[i[0]-1].append(i[1]-1)
        edge[i[1]-1].append(i[0]-1)
    cnt = [0]*N
    for i in px:
        cnt[i[0]-1] += i[1]

    stk = []
    visited = set()
    stk.append(0)
    par = -1
    while len(stk):
        v = stk.pop()
        if not v in visited:
            visited.add(v)
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par and not i in visited:
                stk.append(i)
        par = v

    print(*cnt)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    edge = [[] for _ in range(N)]
    for i in ab:
        edge[i[0]-1].append(i[1]-1)
        edge[i[1]-1].append(i[0]-1)
    cnt = [0]*N
    for i in px:
        cnt[i[0]-1] += i[1]

    stk = []
    visited = set()
    stk.append(0)
    par = -1
    while len(stk):
        v = stk.pop()
        if not v in visited:
            visited.add(v)
            if v>0:
                cnt[v] += cnt[par]
        for j in edge[v]:
            if j!=par and not j in visited:
                stk.append(j)
        par = v

    print(*cnt)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,q = [int(i) for i in input().split()]

def find(x):
    if par[x][0] < 0:
        return x
    else:
        px = find(par[x][0])
        par[x][0] = px
        return px

def unite(x,y):      
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x][0] > par[y][0]:
            x,y = y,x
        par[x][0] += par[y][0]
        par[y][0] = x
        return True

memo = [True]*n
par = [[-1,0,i] for i in range(n)]
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1)
  if memo[a-1] and memo[b-1]:
      par[b-1][1] += 1
  elif memo[b-1] and not memo[a-1]:
    par[b-1][1] += 1+par[a-1][1]
  elif memo[a-1] and not memo[b-1]:
    par[a-1][1] += 1+par[b-1][1]
  memo[a-1] = False
  memo[b-1] = False
  
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

from operator import itemgetter
par = sorted(par,key=itemgetter(1))
par = sorted(par,key=itemgetter(0))
#print(par)
cnt = 0
for i in range(1,n):
  if par[i][0] >= 0 and par[i][1]==1:
    chk[par[i][2]] += chk[par[i][0]]
    cnt = 0
  elif par[i][0] >= 0 and par[i][1]>=2:
    if par[i][0] == par[i-1][0] and par[i][1] > par[i-1][1]:
      chk[par[i][2]] += chk[par[i-1][2]]
      cnt = 0
    if par[i][0] == par[i-1][0] and par[i][1] == par[i-1][1]:
      cnt += 1
      chk[par[i][2]] += chk[par[i-1-cnt][2]]
  else:
    cnt = 0
      
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,q = [int(i) for i in input().split()]

def find(x):
    if par[x][0] < 0:
        return x
    else:
        px = find(par[x][0])
        par[x][0] = px
        return px

def unite(x,y):      
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x][0] > par[y][0]:
            x,y = y,x
        par[x][0] += par[y][0]
        par[y][0] = x
        return True

memo = [True]*n
par = [[-1,0,i] for i in range(n)]
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1)
  if memo[a-1] and memo[b-1]:
      par[b-1][1] += 1
  elif memo[b-1] and not memo[a-1]:
    par[b-1][1] += 1+par[a-1][1]
  elif memo[a-1] and not memo[b-1]:
    par[a-1][1] += 1+par[b-1][1]
  memo[a-1] = False
  memo[b-1] = False
  
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

from operator import itemgetter
par = sorted(par,key=itemgetter(1))
par = sorted(par,key=itemgetter(0))
#print(par)
cnt = 0
for i in range(1,n):
  if par[i][0] >= 0 and par[i][1]==1:
    chk[par[i][2]] += chk[par[i][0]]
    cnt = 0
  if par[i][0] >= 0 and par[i][1]>=2:
    if par[i][0] == par[i-1][0] and par[i][1] > par[i-1][1]:
      chk[par[i][2]] += chk[par[i-1][2]]
      cnt = 0
    if par[i][0] == par[i-1][0] and par[i][1] == par[i-1][1] and par[i][1]>=2:
      cnt += 1
      chk[par[i][2]] += chk[par[i-1-cnt][2]]
      
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,q = [int(i) for i in input().split()]

def find(x):
    if par[x][0] < 0:
        return x
    else:
        px = find(par[x][0])
        par[x][0] = px
        return px

def unite(x,y):      
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x][0] > par[y][0]:
            x,y = y,x
        par[x][0] += par[y][0]
        par[y][0] = x
        return True

memo = [True]*n
par = [[-1,0,i] for i in range(n)]
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1)
  if memo[a-1] and memo[b-1]:
      par[b-1][1] += 1
  elif memo[b-1] and not memo[a-1]:
    par[b-1][1] += 1+par[a-1][1]
  elif memo[a-1] and not memo[b-1]:
    par[a-1][1] += 1+par[b-1][1]
  memo[a-1] = False
  memo[b-1] = False
  
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

from operator import itemgetter
par = sorted(par,key=itemgetter(1))
par = sorted(par,key=itemgetter(0))
#print(par)
cnt = 0
for i in range(1,n):
  if par[i][0] >= 0 and par[i][1]==1:
    chk[par[i][2]] += chk[par[i][0]]
    cnt = 0
  if par[i][0] >= 0 and par[i][1]>=2:
    if par[i][0] == par[i-1][0] and par[i][1] > par[i-1][1]:
      chk[par[i][2]] += chk[par[i-1][2]]
      cnt = 0
    if par[i][0] == par[i-1][0] and par[i][1] == par[i-1][1]:
      cnt += 1
      chk[par[i][2]] += chk[par[i-1-cnt][2]]
      
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    edge = [[] for _ in range(N)]
    for i in ab:
        edge[i[0]-1].append(i[1]-1)
    cnt = [0]*N

    stk = []
    for i in px:
        visited = set()
        stk.append(i[0]-1)
        while len(stk):
            v = stk.pop()
            if not v in visited:
                cnt[v] += i[1]
                visited.add(v)
            for j in edge[v]:
                stk.append(j)

    print(*cnt)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,q = [int(i) for i in input().split()]

def find(x):
    if par[x][0] < 0:
        return x
    else:
        px = find(par[x][0])
        par[x][0] = px
        return px

def unite(x,y):      
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x][0] > par[y][0]:
            x,y = y,x
        par[x][0] += par[y][0]
        par[y][0] = x
        return True

memo = [True]*n
par = [[-1,0,i] for i in range(n)]
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1)
  if memo[a-1] and memo[b-1]:
      par[b-1][1] += 1
  elif memo[b-1] and not memo[a-1]:
    par[b-1][1] += 1+par[a-1][1]
  elif memo[a-1] and not memo[b-1]:
    par[a-1][1] += 1+par[b-1][1]
  memo[a-1] = False
  memo[b-1] = False
  
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

from operator import itemgetter
par = sorted(par,key=itemgetter(1))
par = sorted(par,key=itemgetter(0))

par = tuple(par)
cnt = 0
for i in range(1,n):
  if par[i][0] < 0:
    cnt = 0
  if par[i][0] >= 0 and par[i][1]==1:
    chk[par[i][2]] += chk[par[i][0]]
    cnt = 0
  if par[i][0] >= 0 and par[i][1]>=2:
    if par[i][0] == par[i-1][0] and par[i][1] > par[i-1][1]:
      chk[par[i][2]] += chk[par[i-1][2]]
      cnt = 0
    if par[i][0] == par[i-1][0] and par[i][1] == par[i-1][1]:
      cnt += 1
      chk[par[i][2]] += chk[par[i-1-cnt][2]]
      
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

Solution code:
f=lambda:map(int,input().split())
n,q=f()
p=list(range(n))
for i in range(n-1):
  a,b=f()
  p[b-1]=a-1
c=[0]*n
for i in range(q):
  v,x=f()
  c[v-1]+=x
for i in range(n):
  if p[i]<i:
    c[i]+=c[p[i]]
print(*c)

Submission status: Wrong Answer

Solution code:
n,q = [int(i) for i in input().split()]

per = []
for i in range(n):
  array = [i,i,0]
  per_append = per.append
  per.append(array)

for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  per[b-1][1] = a-1
  per[b-1][2] += per[a-1][2]+1

from operator import itemgetter
per = sorted(per,key=itemgetter(2))
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

#print(per)
for i in range(n):
  if per[i][0]!=per[i][1]:
    chk[per[i][0]] += chk[per[i][1]]
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

Solution code:
n,q = [int(i) for i in input().split()]


per = []
for i in range(n):
  array = [i,i,0]
  per_append = per.append
  per.append(array)

for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  per[b-1][1] = a-1
  per[b-1][2] += per[a-1][2]+1

from operator import itemgetter
per = sorted(per,key=itemgetter(2))
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

#print(per)
for i in range(n):
  if per[i][0]!=per[i][1] and per[i][2]>per[per[i][1]][2]:
    chk[per[i][0]] += chk[per[i][1]]
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
node = [[] for _ in range(n)]
ans = [0] * n

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

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

not_yet = [True] * n
not_yet[0] = False
stack = [0]
while stack:
    parent = stack.pop()
    for child in node[parent]:
        if not_yet[child]:
            ans[child] += ans[parent]
            not_yet[child] = False
            stack.append(child)

print(*ans)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
node = [[]] * n
ans = [0] * n

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

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

not_yet = [True] * n
not_yet[0] = False
stack = [0]
while stack:
    parent = stack.pop()
    for child in node[parent]:
        if not_yet[child]:
            ans[child] += ans[parent]
            not_yet[child] = False
            stack.append(child)

print(*ans)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
node = [[]] * n
ans = [0] * n

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

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

not_yet = [True] * n
not_yet[0] = False
stack = [0]
while stack:
    parent = stack.pop()
    for child in node[parent]:
        if not_yet[child]:
            ans[child] += ans[parent]
            not_yet[child] = False

print(*ans)

Submission status: Wrong Answer

Solution code:
n,q = [int(i) for i in input().split()]


per = []
for i in range(n):
  array = [i,-1,0]
  per_append = per.append
  per.append(array)

for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  per[b-1][1] = a-1
  per[b-1][2] += per[a-1][2]+1

from operator import itemgetter
per = sorted(per,key=itemgetter(2))
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

#print(per)
for i in range(n):
  if per[i][0]!=per[i][1] and per[i][2]>per[per[i][1]][2]:
    chk[per[i][0]] += chk[per[i][1]]
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

Solution code:
n,q = [int(i) for i in input().split()]


per = [-1]*n
wei = [0]*n
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  per[b-1] = a-1
  wei[b-1] += wei[a-1]+1
  
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

#print(per,wei)
for i in range(n):
  if i!=per[i] and wei[i]>wei[per[i]]:
    chk[i] += chk[per[i]]
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

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

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

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

ans = []
q = [0]
while q:
    root = q.pop(0)
    counter = branch[root][0]
    ans.append(counter)
    for child in branch[root][1]:
        branch[child][0] += counter
        q.append(child)

print(*ans)

Submission status: Wrong Answer

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

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

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

ans = []
for i in range(n):
    counter = branch[i][0]
    ans.append(counter)
    for child in branch[i][1]:
        branch[child][0] += counter

print(*ans)

Submission status: Wrong Answer

Solution code:
n,q = [int(i) for i in input().split()]

def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

def weight(x):
    find(x)
    return wei[x]

def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

def same(x,y):
    return find(x) == find(y)
      
par = [-1]*n
wei = [0]*n
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1,1)
  
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  for j in range(n):
    if same(p-1,j) and wei[p-1]<wei[j]:
      chk[j] += x
  chk[p-1] += x

chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

Solution code:
# Problem D - Ki

# input
N, Q = map(int, input().split())
tree_list = {}
for i in range(N):
    tree_list[i+1] = []
for i in range(N-1):
    a, b = map(int, input().split())
    tree_list[a].append(b)
cost_list = [0]*N

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

# search
search_queue = []
search_queue.append(1)
while len(search_queue)>0:
    q = search_queue.pop()
    childs = tree_list[q]
    if len(childs)<=0:
        continue
    for c in childs:
        cost_list[c-1] += cost_list[q-1]
        search_queue.append(c)

# output
print(" ".join(list(map(str,cost_list))))

Submission status: Wrong Answer

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

work_q = deque([1])
used = set()
used.add(1)
ans[1] = cost[1]
cnt = 0
while work_q:
    here = work_q.popleft()
    cnt += cost[here]
    for i in edge[here]:
        if i not in used:
            work_q.append(i)
            used.add(i)
            ans[i] = cnt + cost[i]
print(*ans[1:])

Submission status: Wrong Answer

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

def resolve():

    def dfs(v, score):
        ans[v] += score
        for nv in G[v]:
            if nv != v:
                dfs(nv, score)

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

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

    VS = [list(map(int, input().split())) for _ in range(Q)]
    ans = [0]*N
    for v, s in VS:
        dfs(v-1, s)

    print(*ans)
    
if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)
for _ in range(n-1):
    a,b = map(int,input().split())
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)

from collections import defaultdict
dicp = defaultdict(int)

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


ansl = [0 for i in range(n)]
used = [0 for i in range(n)]
quu = [0]
while quu:
    k = quu.pop()
    for p in dic[k]:
        if used[p] == 0:
            quu.append(p)
            used[p] = 1
            ansl[p] = ansl[k] + dicp[k]



for a in ansl:
    print(a)

Submission status: Wrong Answer

Solution code:
import queue
import sys
sys.setrecursionlimit(5*10**5)

N, Q = map(int, input().split())
ab=[]
for _ in range(N-1):
    ab.append(tuple(map(int, input().split())))
px=[]
for _ in range(Q):
    px.append(tuple(map(int, input().split())))

cnt=[0]*(N+1)
for el in px:
    cnt[el[0]]+=el[1]
#print(cnt)


lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
    lst[el[0]].append(el[1])
#print(lst)

seen = [False] * (N + 1)
def dfs(n):
    seen[n] = True
    for child in lst[n]:
        if seen[child] == False:
            cnt[child]+=cnt[n]
            dfs(child)

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

Submission status: Wrong Answer

Solution code:
import queue
import sys
sys.setrecursionlimit(5*10**5)

N, Q = map(int, input().split())
ab=[]
for _ in range(N-1):
    ab.append(tuple(map(int, input().split())))
px=[]
for _ in range(Q):
    px.append(tuple(map(int, input().split())))

cnt=[0]*(N+1)
for el in px:
    cnt[el[0]]+=el[1]
#print(cnt)

todo=queue.Queue()


lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
#print(lst)

seen = [False] * (N + 1)
def bfs(n):
    seen[n] = True
    for child in lst[n]:
        if seen[child] == False:
            cnt[child]+=cnt[n]
            todo.put(child)
    if not todo.empty():
        bfs(todo.get())
    else:
        return None

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[list(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
#print(dirtree)
for i in range(Q):
    score[points[i][0]-1]=score[points[i][0]-1]+points[i][1]
#print(score)
v=0
d=deque()
d.append(v)
for i in range(N):
    dirtree[i]=tuple(dirtree[i])
dirtree=tuple(dirtree)
print(dirtree)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")

Submission status: Wrong Answer

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

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

def update(p):
    for pp in tree[p]:
        counter[pp] += counter[p]
        update(pp)
    
tree = {i: [] for i in range(N)}
counter = [0] * N
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
update(0)
print(" ".join(map(str, counter)))

Submission status: Wrong Answer

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

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

def update(p):
    for pp in tree[p]:
        counter[pp] += counter[p]
        update(pp)
    
tree = {i: [] for i in range(N)}
counter = [0] * N
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
update(0)
print(" ".join(map(str, counter)))

Submission status: Wrong Answer

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

def dfs(G,v,p):
    for next in G[v]:
        if next == p:
            continue
        dfs(G,next,v)
    
    for c in G[v]:
        if c == p:
            continue
        subtree[v].append(c)
        subtree[v]+=subtree[c]

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

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

subtree = [[] for _ in range(N)]
dfs(G,0,-1)
print(subtree)
for _ in range(Q):
    p,x = map(int, input().split())
    p-=1
    counter[p]+=x
    for i in subtree[p]:
        counter[i]+=x
counter = map(str,counter)
print(' '.join(counter))

Submission status: Wrong Answer

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

def dfs(G,v,x):
    counter[v]+=x
    for next in G[v]:
        dfs(G,next,x)

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

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

for _ in range(Q):
    p,x = map(int, input().split())
    p-=1
    dfs(G,p,x)
counter = map(str,counter)
print(' '.join(counter))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
V = [[] for _ in range(N)]
X = [0 for _ in range(N)]

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

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x
# p親、n現在、s合計
def dfs(p, n):
    X[n] += X[p]
    for i in V[n]:
        if i == p:
            continue
        else:
            dfs(n, i)
dfs(-1,0)
for i in range(N):
    print(X[i], end=" ")

Submission status: Wrong Answer

Solution code:
#26　AtCoder Beginner Contest 138 D - Ki
from collections import deque
n, q = map(int, input().split())
edge = [[] for _ in range(n)]
counter  = [0]*n
for _ in range(n-1):
    u, v = map(int, input().split())
    edge[u-1].append(v-1)
for _ in range(q):
    u, v = map(int, input().split())
    counter[u-1] += v
que = deque([0])
check = [0]*n
while que:
    k = que.pop()
    check[k] = 1
    for i in edge[k]:
        if check[i]: continue
        counter[i] += counter[k]
        que.append(i)
print(*counter)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque

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

d = defaultdict(list)
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 0-indexed
    d[a].append(b)
# print('d', d)

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

# print(P)

ans = [0] * N
for i in range(N):
    p = P[i]
    if p != 0:
        ans[i] += p
        q = deque(d[i])
        while len(q) > 0:
            j = q.popleft()
            ans[j] += p
            for k in d[j]:
                q.append(k)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque

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

d = defaultdict(list)
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 0-indexed
    d[a].append(b)
# print('d', d)

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

# print(P)

ans = [0] * N
for i in range(N):
    p = P[i]
    if p != 0:
        ans[i] += p
        q = deque(d[i])
        while len(q) > 0:
            j = q.popleft()
            ans[j] += p
            for k in d[j]:
                q.append(k)
print(*ans)

Submission status: Wrong Answer

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

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

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

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

counter = [-1] * n


def calculate(i, v):
    if counter[i] != -1:
        return counter[i]

    total = operations[i] + v
    for c in children[i]:
        calculate(c, total)

    counter[i] = total


calculate(0, 0)
print(' '.join(list(map(str, counter))))

Submission status: Wrong Answer

Solution code:
from _collections import deque

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

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

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

ans = [0]*N
q = deque()
q.append((0,0))
while(len(q)>0):
    a,parent = q.popleft()
    ans[a] = ans[parent] + point[a]
    for i in K[a]:
        q.append((i,a))

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

Submission status: Wrong Answer

Solution code:
from _collections import deque

N,Q = map(int,input().split())
K = [[] for _ in range(N)]
parents = [0]*N
point = [0]*N

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

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

ans = [0]*N
q = deque()
q.append(0)
while(len(q)>0):
    a = q.popleft()
    parent = parents[a]
    ans[a] = ans[parent] + point[a]
    for i in K[a]:
        q.append(i)

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import OrderedDict

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


class Graph():
    def __init__(self):
        self.adjacency_dict = {}
        self.counter_dict = OrderedDict()

    def add_vertex(self, v):
        self.adjacency_dict[v] = set()
        self.counter_dict[v] = 0

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].add(v2)
        self.adjacency_dict[v2].add(v1)

    def add_count(self, v, count):
        self.counter_dict[v] += count

    def dfs_stack(self, start):
        stack = [start]
        visited = set()

        parent_vertex = 0
        while stack != []:
            current_vertex = stack.pop()
            if parent_vertex != 0:
                self.counter_dict[current_vertex] += self.counter_dict[parent_vertex]
            visited.add(current_vertex)
            for v in self.adjacency_dict[current_vertex]:
                if v not in visited and v != parent_vertex:
                    stack.append(v)
            parent_vertex = current_vertex

    def dfs_rec(self, v, pv):
        for nv in self.adjacency_dict[v]:
            if nv != pv:
                self.counter_dict[nv] += self.counter_dict[v]
                self.dfs(nv, v)

    def print_counters(self):
        print(*self.counter_dict.values())


def main():
    n, q = map(int, input().split())
    tree = Graph()
    for v in range(1, n+1):
        tree.add_vertex(v)
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree.add_edge(a, b)
    for _ in range(q):
        p, x = map(int, input().split())
        tree.add_count(p, x)
    tree.dfs_stack(1)
    # tree.dfs_rec(1, 0)
    tree.print_counters()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import OrderedDict
sys.setrecursionlimit(2*(10**5))


class Graph():
    def __init__(self):
        self.adjacency_dict = OrderedDict()
        self.counter_dict = OrderedDict()
        self.x_dict = OrderedDict()

    def add_vertex(self, v):
        self.adjacency_dict[v] = []
        self.counter_dict[v] = 0
        self.x_dict[v] = 0

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)

    def add_x(self, v, x):
        self.x_dict[v] += x

    def dfs(self, start, count=None, visited=None):
        if visited is None:
            visited = []
        if count is None:
            count = self.x_dict[start]
        self.counter_dict[start] = count
        visited.append(start)
        for v in self.adjacency_dict[start]:
            if v in visited:
                continue
            self.dfs(v, count + self.x_dict[v], visited)

    def print_counters(self):
        print(*self.counter_dict.values())


def main():
    n, q = map(int, input().split())
    tree = Graph()
    for v in range(1, n+1):
        tree.add_vertex(v)
    for _ in range(n-1):
        a, b = map(int, input().split())
        a = min(a, b)
        b = max(a, b)
        tree.add_edge(a, b)
    for _ in range(q):
        p, x = map(int, input().split())
        tree.add_x(p, x)
    tree.dfs(1)
    tree.print_counters()


if __name__ == "__main__":
    main()