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
sys.setrecursionlimit(20000000)

n,q = map(int,input().split())
ab = [[int(v) for v in input().split()] for _ in range(n-1)]
px = [[int(v) for v in input().split()] for _ in range(q)]

adjacent_list = [[] for _ in range(n+1)]
visited = [True for _ in range(n+1)]

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

for query in px:
    p,x = query
    q_num[p] += x

for edge in ab:
    a,b = edge
    adjacent_list[a].append(b)

def dfs(cur,prev_state):
    now_state = q_num[cur] + prev_state
    n_num[cur] = now_state

    for next_node in adjacent_list[cur]:
        if visited[cur]:
                visited[cur] = False
                dfs(next_node,now_state)

dfs(1,0)

for ans in n_num[1:]:
    print(ans,end=' ')
print()

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
edges = [input().split() for _ in range(N-1)]
operations = [input().split() for _ in range(Q)]

tree = {}
counter = [0]*N
result = [0]*N

for o in operations:
    counter[int(o[0])-1] += int(o[1])

result[0] = counter[0]

# print(counter)

for e in edges:
    parent = e[0]
    sun = e[1]
    if sun in tree:
        tree[sun].append(parent)
    else:
        tree[sun] = [parent]

    if parent in tree:
        tree[sun].extend(tree[parent])

# print(tree)

for k in tree.keys():
    result[int(k)-1] += counter[int(k) - 1]
    for i in tree[k]:
        result[int(k)-1] += counter[int(i)-1]

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

Submission status: Wrong Answer

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

b = []
for j in range(q):
    b.append((input()))
    
aws = []
for k in range(n):
    aws.append(0)

for bn in b:
    aws[ int(bn.split()[0]) - 1] +=  int(bn.split()[1])
    for an in a:
        if  bn.split()[0]== an.split()[0]:
            tt = int(an.split()[1])
            aws[tt - 1] += int(bn.split()[1])
            
print(aws)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
child = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    child[a].append(b)
prog = [[i] for i in range(N)]
for i in range(N):
    if len(child[i]) == 0:
        continue
    for j in child[i]:
        prog[i].append(j)
        prog[i].extend(child[j])

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

Submission status: Wrong Answer

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

N, Q = map(int, input().split())
a = []
p = []
x = [0]*(N)
A = [0]*(N)

for i in range(N-1):
    t=input().split()
    if t[0]>t[1]:
        swap = t[1]
        t[1] = t[0]
        t[0] =swap
    a.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=input().split()
    p.append((int(t[0]),int(t[1])))

#a.sort()
#p.sort()

#print(a)
for i in range(Q):
    x[p[i][0]-1] += p[i][1]
A[0] = x[0]
for i in range(N-1):
    La = a[i][0]-1
    Lb = a[i][1]-1

    A[Lb] = A[La]+x[Lb]

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000000)


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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import collections


def main():
    [n, q] = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [-1] * (n-1)
    b = [-1] * (n-1)
    tree = collections.defaultdict(set)
    for i in range(n-1):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split()]
        tree[a[i]-1].add(b[i]-1)

    p = [-1] * q
    x = [-1] * q
    adds = [0] * n
    for i in range(q):
        p[i], x[i] = [int(s) for s in sys.stdin.readline().strip().split()]
        adds[p[i]-1] += x[i]

    results = [0] * n
    seen = set()

    def rec_add(node, cur, c):
        if c > 100:
            return
        cur += adds[node]
        results[node] = cur
        seen.add(node)
        for child in tree[node]:
            if child in seen:
                continue
            rec_add(child, cur, c+1)

    rec_add(0, 0, 0)
    print(' '.join([str(n) for n in results]))


main()

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
pa = [list(map(int, input().split())) for _ in range(N-1)]
glp = list(range(N + 1))

for i in range(N-1):
    if glp[pa[i][0]] > glp[pa[i][1]]:
        glp[pa[i][0]] = glp[pa[i][1]]
    else:
        glp[pa[i][1]] = glp[pa[i][0]]

tree = [[]for i in range(N + 1)]
counter = [0]*N
for a, b in pa:
    if glp[a] != a:
        tree[glp[a]].append(b)
        tree[a].append(b)
    else:
        tree[a].append(b)
        
for i in range(Q):
    p, x = map(int, input().split())
    for pi in tree[p]:
        counter[pi-1] += x
    counter[p-1] += x
    
print(" ".join(map(str, counter)))

Submission status: Wrong Answer

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

N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
R = defaultdict(set)
visit = [False]*N
full = set(range(N))

def dfs(v, road):
    if not visit[v]:
        R[v] = full - set(road)
        road.append(v)
        visit[v] = True
        for nxt in E[v]:
            dfs(nxt, road[:])


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

Submission status: Wrong Answer

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

ab = []

for i in range(N-1):
    ab.append(list(map(int, input().split())))

l = [[] for i in range(N)]

for pi in ab:
    l[pi[0]-1].append(pi[1]-1)

cou = [0] * N

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    cou[p] += x
    for j in l[p]:
        cou[j] += x
        for k in l[j]:
            cou[k] += x
            for h in l[k]:
                cou[h] += x

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

Submission status: Wrong Answer

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

N, Q = map(int, input().split())
a = []
p = []
x = [0]*(N)
A = [0]*(N)

for i in range(N-1):
    t=input().split()
    a.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=input().split()
    p.append((int(t[0]),int(t[1])))
#a.sort()
#p.sort()

#print(a)
for i in range(Q):
    x[p[i][0]-1] += p[i][1]
A[0] = x[0]
for i in range(N-1):
    La = a[i][0]-1
    Lb = a[i][1]-1

    A[Lb] = A[La]+x[Lb]

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

Submission status: Wrong Answer

Solution code:
class Node():
    def __init__(self):
        self.counter = 0
        self.child_num = 1

def main():

    n, q = map(int, input().split(' '))
    nodes = [Node() for _ in range(0, n)]
    ab = []
    for _ in range(0, n-1):
        a, b = map(int, input().split(' '))
        ab.append((a, b))

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

    # 構築
    for a, b in ab:
        nodes[b-1].counter += nodes[a-1].counter

    # for node in nodes[::-1]:
    #     if node.parent is not None:
    #         node.parent.child_num += node.child_num
    #     node.counter *= node.child_num
    #

    count = 0
    for node in nodes:
        count += 1
        print(node.counter, end='')
        if count != n:
            print(' ', end='')

    print()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
tree = defaultdict(list)
par = [-1]*N
par[0] = 0
zyunban = []
for a, b in ab:
	tree[a-1].append(b-1)
	tree[b-1].append(a-1)

	if par[a-1] != -1:  # 親が存在
		par[b-1] = a-1
	elif par[b-1] != -1:
		par[a-1] = b-1
	else:
		par[a-1] = b-1
		par[b-1] = a-1
		
px = [LIST() for _ in range(Q)]

counter = defaultdict(int)  # まとめる
for p, x in px:
	counter[p-1] += x

ans = [-1] * N  # 答え入れる
ans[0] = counter[0]

def DFS(n):
	if not n == 0:
		ans[n] = counter[n] + ans[par[n]]
	for child in tree[n]:
		if ans[child] == -1:
			DFS(child)

DFS(0)
print(*ans, sep=" ")

Submission status: Wrong Answer

Solution code:
line1 = input().split()
n = int(line1[0])
q = int(line1[1])

sahen = []
uhen = []

for num in range(n-1):
  inp =input().split()
  sahen.append(int(inp[0]))
  uhen.append(int(inp[1]))

j =[]
for num in range(q):
  inpt =input().split()
  j.append([int(inpt[0]),int(inpt[1])])

result = [0 for num in range(n)]

for num2 in j:
  if (num2[0] in sahen):
    start = sahen.index(num2[0])
    for num in range(start,n):
      result[num] += num2[1]
  else:
    ind = uhen.index(num2[0])
    result[ind] += num2[1]

print(*result)

Submission status: Wrong Answer

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

p = [0]*q
x = [0]*q

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

score = [0]*n

def down_tree(parent, add_score):
    global score
    judge_count = 0
    for i in range(q):
        if p[i]-1 == parent:
            add_score += x[i]
    for i in range(n-1):
        if a[i]-1 == parent:
            down_tree(b[i]-1, add_score)
            judge_count += 1

    score[parent] += add_score

    return 0

down_tree(0, 0)

print(score)

Submission status: Wrong Answer

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

def dfs(v,preval,Edges,Nodes,visited): 
    stack = []
    visited = set()
    stack.append(v)

    while len(stack)>0:
        current = stack.pop()
        if current in visited:
            continue
        visited.add(current)
        if current != 0:
            Nodes[current] += preval
        preval = Nodes[current]
        for i in Edges[current]:
            stack.append(i)
    return Nodes

visited = [False]*(len(Nodes)) 
Nodes = dfs(0,Nodes[0],Edges,Nodes,visited) 

print(" ".join(list(map(str,Nodes))))

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
a = []
b = []
for _ in range(N-1):
    s,t  = map(int,input().split())
    a.append(s)
    b.append(t)
p = {}
for _ in range(Q):
    s,t  = map(int,input().split())
    if s in p.keys():
        p[s] = p[s] + t
    else:
        p[s] = t
for i in range(N-1):
    s = a[i]
    t = b[i]
    if t in p.keys() and s in p.keys():
        p[t] += p[s]
    elif s in p.keys():
        p[t] = p[s]
    else:
        p[t] = 0
for v in p.values():
  print(str(v)+" ",end="")

Submission status: Wrong Answer

Solution code:
n, q = (int(i) for i in input().split())
tree = dict()
for i in range(n-1):
    p, c = (int(j) for j in input().split())
    child = tree.get(p-1, [])
    tree[p-1] = child + [c-1]
cnt = [0]*n
for i in range(q):
    p, x = (int(j) for j in input().split())
    cnt[p-1] = x
q = list([0])
while len(q) > 0:
    idx = q.pop(0)
    child = tree.get(idx, [])
    for c in child:
        cnt[c] = cnt[c] + cnt[idx]
    q = q + child
print(' '.join([str(c) for c in cnt]))

Submission status: Wrong Answer

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

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

ans = [0] * n


for i in range(q):
    p, x = map(int,input().split())
    if (p == 1):
        for j in range(n):
            ans[j] += x
    else:
        br = {p}
        for j in range(p,n-1):
            if(ab[j][0] in br):
                br.add(ab[j][1])

        for k in br:
            ans[k-1] += x

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

Submission status: Wrong Answer

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

parent={1:[1]}

for i in range(n-1):
    a, b = map(int,input().split( ))
    parent[b]=[b,a]
    if a in parent:
        parent[b]+=parent[a]
# print(parent)

top_counter=[0 for i in range(n)]

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

# print(top_counter)

counter=[0 for i in range(n)]
for i in range(n):
    check=set(parent[i+1])
    # print(check)
    for j in check:
        counter[i]+=top_counter[j-1]

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

Submission status: Wrong Answer

Solution code:
N, Q = map(int, raw_input().split())
ans = [0 for i in range(N)]
tree_s = ['' for i in range(N-1)]

for i in range(0, N-1):
    a, b = map(int, raw_input().split())
    tree_s[i] = str(a) + '-' + str(b)

tree_s.sort()

for i in range(0, Q):
    v, p = map(int, raw_input().split())
    ans[v-1] += p

for i in range(0, N-1):
    ab = tree_s[i].split("-")
    ans[int(ab[1])-1] += ans[int(ab[0])-1]


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

Submission status: Wrong Answer

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

N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
R = defaultdict(list)
visit = [False]*N


def dfs(v, road):
    if not visit[v]:
        R[v] = road
        road.append(v)
        visit[v] = True
        for nxt in E[v]:
            dfs(nxt, road[:])


dfs(0, [])

S = defaultdict(set)
full = set(range(N))
for i in range(N):
    S[i] = full - set(R[i])

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)

class Node:
    def __init__(self, key):
        self.key = key
        self.child = []
        self.point = 0

n, q = map(int, input().split())
a, b, p, x = [], [], [], []
nodes = []
nodes.append(None)
ans = []

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

for i in range(q):
    temp1, temp2 = map(int, input().split())
    p.append(temp1)
    x.append(temp2)

# Make node list
for i in range(1, n+1):
    node = Node(i)
    nodes.append(node)


for i in range(n-1):
    nodeParent = nodes[a[i]]
    nodeChild = nodes[b[i]]
    nodeParent.child.append(nodeChild)

def printNode(node):
#    print(node.point)
    ans.append(node.point)
    for child in node.child:
        printNode(child)

def addCount(node, point):
    node.point += point
    for child in node.child:
        addCount(child, point)

for i in range(q):
    node = nodes[p[i]]
    addCount(node, x[i])

printNode(nodes[1])

print(' '.join([str(i) for i in ans]))

Submission status: Wrong Answer

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

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

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

x = [LI() for _ in range(q)]
x.sort()
ans = [0]*n
for i,j in x:
    ans[i-1] = ans[g[i-1]] + j
for i in range(n):
    if ans[i] == 0:
        ans[i] = ans[g[i]]
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def dfs(graph, start):
    stack = [start]
    visited = []
    while stack:
        label = stack.pop(0)
        if label not in visited:
            visited.append(label)
            stack = graph.get(label, []) + stack
    return visited
  
tree = defaultdict(list)
N,Q = map(int, input().split())

lst1 = [list(map(int, input().split())) for i in range(N-1)]
lst2 = [list(map(int, input().split())) for i in range(Q)]
for i in range(N):
  dict(tree)[i+1] = []
for i in lst1:
  tree[i[0]].append(i[1])
ans = [0] * N
for i in lst2:
  start = i[0]
  for j in list(dfs(dict(tree), i[0])):
    if (start <= j):
      ans[j-1] += i[1]
print(ans)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
a=[{0}]
for x in range(n):
  a+=[{0}]
b=[0]*n
for i in range(n-1):
  x,y=map(int,input().split())
  a[x-1].add(x-1)
  a[y-1].add(x-1)
  a[y-1].add(y-1)
for i in range(q):
  z,w=map(int,input().split())
  b[z-1]+=w
for i in range(n):
  ans=0
  for j in a[i]:
    ans += b[j]
  if(i==n-1):
    print(ans)
  else:
    print(ans,end=" ")

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PQ = [list(map(int,input().split())) for _ in range(Q)]
l=[[] for _ in range(N)]
ans=[0]*N
for a,b in reversed(AB):
	l[int(a-1)].append(b)
	l[a-1].extend(l[b-1])
for p,q in PQ:
	ans[p-1]+=q
	for i in l[p-1]:
		ans[i-1]+=q
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)]
px.sort()
print(px)
ans = [0]*(n+1)
for i in range(q):
  if px[i][0]==1:
    ans[1] += px[i][1]
    
  for j in range(n-1):
    if ab[j][1] == px[i][0]:
      ans[px[i][0]] += ans[ab[j][0]] + px[i][1]
      
for k in range(1,n+1):
  if ans[k]==0:
    for x in range(n-1):
      if ab[x][1] == k:
          ans[k] += ans[ab[x][0]]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

ab = [list(map(int,input().split())) for i in range(N-1)]
ab = sorted(ab, reverse=True)
pq = [list(map(int,input().split())) for i in range(Q)]
tree = {}
ans = [0]*N

for pair in ab:
    if pair[0] not in tree:
        tree[pair[0]] = [pair[1]]
    else:
        tree[pair[0]].append(pair[1])
    if pair[1] in tree:
        for i in range(len(tree[pair[1]])):
            tree[pair[0]].append(tree[pair[1]][i])

for pair in pq:
    ans[pair[0]-1] += pair[1]

    if pair[0] in tree:
        for i in tree[pair[0]]:
            ans[i-1] += pair[1]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def DFS(n):
	if not n == 0:
		ans[n] = counter[n] + ans[par[n]]
	for child in tree[n]:
		if ans[child] == -1:
			DFS(child)

N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
tree = defaultdict(list)
for a, b in ab:
	tree[a-1].append(b-1)
	tree[b-1].append(a-1)

par = [-1]*N
par[0] = 0
zyunban = []
for a, b in ab:
	if par[a-1] != -1:  # 親が存在
		par[b-1] = a-1
	elif par[b-1] != -1:
		par[a-1] = b-1
	else:
		par[a-1] = b-1
		par[b-1] = a-1

px = [LIST() for _ in range(Q)]

counter = defaultdict(int)  # まとめる
for p, x in px:
	counter[p-1] += x

ans = [-1] * N  # 答え入れる
ans[0] = counter[0]
DFS(0)
print(*ans, sep=" ")

Submission status: Wrong Answer

Solution code:
import math

node_len, ope_count = [int(x) for x in input().split()]

node_path = {}
node_weight = {}

for i in range(node_len-1):
    parent, child = input().split()

    if i == 0:
        node_path[parent] = [parent]
        node_weight[parent] = 0

    if parent not in node_path:
        node_path[parent] = [parent]
        node_weight[parent] = 0

    if child not in node_path:
        node_path[child] = []
        node_weight[child] = 0
        if parent in node_path:
            node_path[child] = node_path[parent] + [child]
    else:
        node_path[child] = [parent] + node_path[child]

for i in range(ope_count):
    node_id, weight = input().split()
    node_weight[node_id] += int(weight)

for i in range(node_len):
    node_id = str(i + 1)
    value = sum([node_weight[id] for id in node_path[node_id]])
    print(value)
# print(node_path)
# print(node_weight)

Submission status: Wrong Answer

Solution code:
import sys
import collections


def main():
    [n, q] = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [-1] * (n-1)
    b = [-1] * (n-1)
    tree = collections.defaultdict(set)
    for i in range(n-1):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split()]
        tree[a[i]-1].add(b[i]-1)

    p = [-1] * q
    x = [-1] * q
    adds = [0] * n
    for i in range(q):
        p[i], x[i] = [int(s) for s in sys.stdin.readline().strip().split()]
        adds[p[i]-1] += x[i]

    results = [0] * n
    seen = set()

    # def rec_add(node, cur):
    #     cur += adds[node]
    #     results[node] = cur
    #     seen.add(node)
    #     for child in tree[node]:
    #         if child in seen:
    #             continue
    #         rec_add(child, cur)
    #
    # rec_add(0, 0)
    # print(' '.join([str(n) for n in results]))


main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000)
n,q=map(int,input().split())
g=[set() for i in range(n+1)]
for i in range(1,n+1):
    g[i].add(i)

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

for i in range(n+1):
    g[i]=list(g[i])

for i in range(n,0,-1):
    y=g[i][0]
    g[y]+=g[i]

for i in range(1,n+1):
    g[i].remove(g[i][0])
    g[i]=set(g[i])

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


print(*c[1:])

Submission status: Wrong Answer

Solution code:
a=[]
b=[]
c=[]
s=""
for x in input().split(" "):
    c.append(int(x))
i=0
il=[]
while i<c[0]-1:
    for x in input().split(" "):
        il.append(int(x))
    a.append(il)
    i+=1
    s=""
    il=[]
i=0
while i<c[1]:
    for x in input().split(" "):
        il.append(int(x))
    b.append(il)
    i+=1
    s=""
    il=[]

k=[]
kp=[]
kps=[]
i=0
while i<=c[0]:
    k.append([])
    kp.append(0)
    i+=1
for x in a:
    k[x[0]].append(x[1])
i=0
il=[]
for x in b:
    while i<c[0]:
        if i==x[0]:
            il.append(i)
            kp[i]+=x[1]
        if i>=x[0] and i in il:
            for y in k[i]:
                il.append(y)
                kp[y]+=x[1]
        i+=1
    i=0
    il=[]
del kp[0]
for x in kp:
    kps.append(str(x))
print(' '.join(kps))

Submission status: Wrong Answer

Solution code:
from collections import deque

n,q = map(int,input().split())
graph = [[] for _ in range(n)]
connected = [[i] for i in range(n)]
imos = [0] * (n + 1)
cnt = []

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

for i in range(n):
    que = deque(graph[i])
    while que:
        c = que.popleft()
        connected[i].append(c)
        que += deque(graph[c])

for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    l = connected[p][0]
    r = connected[p][-1]
    imos[l] += x
    imos[r+1] -= x

for i in range(n):
    if i==0:
        cnt.append(imos[i])
    else:
        cnt.append(cnt[i-1] + imos[i])

print(str(cnt).replace('[','').replace(']','').replace(',',''))

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

x_sorted = [0 for _ in range(n)]
for i in range(q):
    p = px[i][0]
    x = px[i][1]
    x_sorted[p - 1] += x

start = 0
inf = float('inf')
cost = dict() # コストテーブル
for i, j in ab:
    c = x_sorted[i - 1]
    cost[i - 1] = cost.get(i - 1, []) + [(j - 1, c)]

d = [inf for i in range(n)] # 最短距離
d[start] = 0

qq = [[d[0], 0]]
while qq:
    print(qq)
    [du, u] = qq.pop(0) # 最短距離とその頂点
    for v, weight in cost.get(u, []):
        alt = du + weight
        d[v] = alt
        qq.append([alt, v])

ans = ''
for i in range(n):
    ans += str(d[i] + x_sorted[i]) + ' '

print(ans[:-1])

Submission status: Wrong Answer

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

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

n,q = LI()
g = [0]*n
for _ in range(n-1):
    a,b = LI()
    g[b-1] = a-1
x = [LI() for _ in range(q)]
x.sort()
ans = [0]*n
for i,j in x:
    ans[i-1] = ans[g[i-1]] + j
for i in range(n):
    if ans[i] == 0:
        ans[i] = ans[g[i-1]]
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

for i in range(n-1):
    a, b = map(int, input().split( ))
    Edg[a].append(b)
Ans=[0 for i in range(n+1)]
P = [0 for i in range(n+1)]
for i in range(q):
    p, x = map(int, input().split( ))
    P[p]+=x

Task=deque()
for p in range(n+1):
    Task.append(p)
    tmp=P[p]
    while True:
        try:
            p_=Task.popleft()
            Ans[p_]+=tmp
            for child in Edg[p_]:
                Task.append(child)
        except:
            break
print(*Ans[1:])

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10000*10000)

from collections import defaultdict, Counter
from queue import deque

def increment(key, count, adj_list, inc_num, visited):
    que = deque()
    que.append(key)

    while que:
        for _ in range(len(que)):
            node = que.popleft()
            if node in visited:
                continue
            count[node] += inc_num
            visited.add(node)
            for num in adj_list[node]:
                que.append(num)

N, Q = map(int, input().split())
adj_list = defaultdict(list)
count = Counter()

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

for i in range(Q):
    c, d = map(int, input().split())
    increment(c, count, adj_list, d, set([]))

count = sorted(count.items(), key=lambda x: x[0])
print(' '.join([str(num[1]) for num in count]))

Submission status: Wrong Answer

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

parent={}

for i in range(n-1):
    a, b = map(int,input().split( ))
    parent[b]=[a]
    if a in parent:
        parent[b]+=parent[a]
# print(parent)

top_counter=[0 for i in range(n)]

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

# print(top_counter)

counter=[0 for i in range(n)]
for i in range(n):
    if i==0:
        counter[i]=top_counter[i]
    else:
        counter[i]=top_counter[i]
        check=set(parent[i+1])
        # print(check)
        for j in check:
            counter[i]+=top_counter[j-1]

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

Submission status: Wrong Answer

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

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
ab = [None] * (N - 1)
for i in range(N - 1):
    ab[i] = list(map(int, input().split()))
# ab = sorted(ab, key=lambda x: (x[0], x[1]))

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

ans = [0] * N
ans[0] = px_n[0]
for (a, b) in ab:
    ans[b-1] += ans[a-1] + px_n[b-1]

print(*ans)