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
from collections import deque
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N, Q = MAP()
	G = [[[],0] for _ in range(N)]
	for _ in range(N-1):
		a, b = MAP()
		a -= 1
		b -= 1
		G[a][0].append(b)

	T = [MAP() for _ in range(Q)]
	T = [[t[0]-1,t[1]] for t in T]
	
	for t in T:
		s, p = t
		# print(s, p)
		queue = deque()
		queue.append(s)
		added = [0] * N
		while queue:
			v = queue.popleft()
			if not added[v]:
				G[v][1] += p
				added[v] = 1
			for nv in G[v][0]:
				# print("v, nv: {}, {}".format(v, nv))
				G[nv][1] += p
				added[nv] = 1
				queue.append(nv)
	
	# print(G)
	print(' '.join([str(g[1]) for g in G]))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
import queue


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

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

    has_noparent = {i : True for i in range(1, N+1)}
    has_noparent[1] = False
    
    q = queue.Queue()
    q.put(1)
    
    children = {i : [] for i in range(1, N+1)}
    while not q.empty():
        parent = q.get()
        for child in edges[parent]:
            if has_noparent[child]:
                children[parent].append(child)
                q.put(child)
                has_noparent[child] = False

    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x

    ret = []
    for i in range(1, N+1):
        value_parent = values[i]
        for child in children[i]:
            values[child] += value_parent
        ret.append(value_parent)

    ret = [str(i) for i in ret]
    ret = ' '.join(ret)
    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import queue


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

    edges = {i : [] for i in range(1, N+1)}
    for i in range(N-1):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
        
    q = queue.Queue()
    q.put(1)

    has_noparent = {i : True for i in range(1, N+1)}
    has_noparent[1] = False
    
    q = queue.Queue()
    q.put(1)
    
    children = {i : [] for i in range(1, N+1)}
    while not q.empty():
        parent = q.get()
        for child in edges[parent]:
            if has_noparent[child]:
                children[parent].append(child)
                q.put(child)
                has_noparent[child] = False

    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x

    ret = []
    for i in range(1, N+1):
        value_parent = values[i]
        for child in children[i]:
            values[child] += value_parent
        ret.append(value_parent)

    ret = [str(i) for i in ret]
    ret = ' '.join(ret)
    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


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

    edges = {i : [] for i in range(1, N+1)}
    for i in range(N-1):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
        
    is_parentfix = {i : False for i in range(1, N+1)}
    is_parentfix[1] = True
    
    children = {i : [] for i in range(1, N+1)}
    for i in range(1, N+1):
        if is_parentfix[i]:
            _children = children[i]
            for child in edges[i]:
                if not is_parentfix[child]:
                    _children.append(child)
                    is_parentfix[child] = True

    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x

    ret = []
    for i in range(1, N+1):
        value_parent = values[i]
        for child in children[i]:
            values[child] += value_parent
        ret.append(value_parent)

    ret = [str(i) for i in ret]
    ret = ' '.join(ret)
    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


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

    edges = {i : [] for i in range(1, N+1)}
    for i in range(N-1):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
        
    isnot_parentfix = {i : True for i in range(1, N+1)}
    isnot_parentfix[1] = False
    
    children = {i : [] for i in range(1, N+1)}
    for i in range(1, N+1):
        _children = children[i]
        for child in edges[i]:
            if isnot_parentfix[child]:
                _children.append(child)
                isnot_parentfix[child] = False

    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x

    ret = []
    for i in range(1, N+1):
        value_parent = values[i]
        for child in children[i]:
            values[child] += value_parent
        ret.append(value_parent)

    ret = [str(i) for i in ret]
    ret = ' '.join(ret)
    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


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

    edges = {i : [] for i in range(1, N+1)}
    for i in range(N-1):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
        
    isnot_parentfix = {i : True for i in range(1, N+1)}
    isnot_parentfix[0] = False
    
    children = {i : [] for i in range(1, N+1)}
    for i in range(1, N+1):
        _children = children[i]
        for child in edges[i]:
            if isnot_parentfix[child]:
                _children.append(child)
                isnot_parentfix[child] = False

    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x

    ret = []
    for i in range(1, N+1):
        value_parent = values[i]
        for child in children[i]:
            values[child] += value_parent
        ret.append(value_parent)

    ret = [str(i) for i in ret]
    ret = ' '.join(ret)
    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


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

    edges = {i : [] for i in range(1, N+1)}
    for i in range(N-1):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
        
    isnot_parentfix = {i : True for i in range(1, N+1)}
    isnot_parentfix[0] = False
    
    children = {i : [] for i in range(1, N+1)}
    for i in range(1, N+1):
        _children = children[i]
        for child in edges[i]:
            if isnot_parentfix[child]:
                _children.append(child)

    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x

    ret = []
    for i in range(1, N+1):
        value_parent = values[i]
        for child in children[i]:
            values[child] += value_parent
        ret.append(value_parent)

    ret = [str(i) for i in ret]
    ret = ' '.join(ret)
    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


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

    children = {i : [] for i in range(1, N+1)}
    for i in range(N-1):
        a, b = map(int, input().split())
        children[min(a, b)].append(max(a, b))

    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x

    ret = []
    for i in range(1, N+1):
        value_parent = values[i]
        for child in children[i]:
            values[child] += value_parent
        ret.append(value_parent)

    ret = [str(i) for i in ret]
    ret = " ".join(ret)
    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


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

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

    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x

    ret = []
    for i in range(1, N+1):
        value_parent = values[i]
        for child in children[i]:
            values[child] += value_parent
        ret.append(value_parent)

    ret = [str(i) for i in ret]
    ret = " ".join(ret)
    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


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

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

    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x

    ret = []
    for i in range(1, N+1):
        value_parent = values[i]
        for child in children[i]:
            values[child] += value_parent
        ret.append(value_parent)

    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2 *(10**5) + 1)
def main():
    N, Q = map(int, input().split())
    d = {}
    for _ in range(N-1):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    dc = {}
    for _ in range(Q):
        p, x = map(int, input().split())
        if p in dc:
            dc[p] += x
        else:
            dc[p] = x
    v = set()
    l = [0] * N
    def dfs(n, p):
        v.add(n)
        if n in dc:
            p += dc[n]
        for i in d[n]:
            print(n, i)
            if i not in v:
                dfs(i, p)
        l[n-1] = p
    dfs(1, 0)
    a = ''
    for i in l:
        a += str(i) + ' '
    return a[:-1]

print(main())

Submission status: Wrong Answer

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

stack = [0]
while stack:
    node = stack.pop()
    for snode in tree[node]:
        c[snode] += c[node]
        stack.append(snode)

print(*c)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, q = map(int, input().split())
tree = [list() for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
c = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    subtree = deque(tree[p-1])
    c[p-1] += x
    while subtree:
        snode = subtree.pop()
        c[snode] += x
        subtree += tree[snode]
print(*c)

Submission status: Wrong Answer

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

for i, subnode in enumerate(tree):
    for s in subnode:
        c[s] += c[i]

print(*c)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
tree = [list() for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
c = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    subtree = tree[p-1].copy()
    c[p-1] += x
    while subtree:
        snode = subtree.pop()
        c[snode] += x
        subtree += tree[snode]
print(*c)

Submission status: Wrong Answer

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

N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
# 親も子も入れる（親子関係なくエッジを　ぶちこむ）
for ab in AB:
    graph[ab[0]].append(ab[1])
val = [0] * (N+1)
# 同じノードに加算するのはひとまとめに
for px in PX:
    val[px[0]] += px[1]
# 親リスト（？）
parent = [0] * (N+1)
# cueの初期化
Q  = [1]
while Q:
    # 左端を取る
    q = Q.pop()
    # 関係するノードすべてをループ
    for c in graph[q]:
        Q.append(c)
        val[c] += val[q]
print(*val[1:])

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
from collections import deque
Q  = deque([1])
while Q:
    q = Q.pop()
    for c in graph[q]:
#         if c == parent[q]:
#             continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
AB = sorted(AB,key=lambda x:(x[0],x[1]))
PX = sorted(PX,key=lambda x:(x[0],x[1]))
value = dict()
for px in PX:
    value.setdefault(px[0],0)
    value[px[0]] += px[1]
tree = dict()
for ab in AB:
    tree.setdefault(ab[0],[])
    tree[ab[0]].append(ab[1])
from collections import deque
Q = deque([1])
while Q:
    q = Q.pop()
    tree.setdefault(q,[])
    for c in tree[q]:
        value.setdefault(c,0)
        value.setdefault(q,0)
        value[c] += value[q]
        Q.append(c)
ans = []
for n in range(N):
    ans.append(value[n+1])
print(*ans)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
from collections import defaultdict as ddict
value = ddict(int)
for px in PX:
    value[px[0]] += px[1]
tree = ddict(list)
for ab in AB:
    tree[ab[0]].append(ab[1])
from collections import deque
Q = deque([1])
while Q:
    q = Q.pop()
    for c in tree[q]:
        value[c] += value[q]
        Q.append(c)
ans = []
for n in range(N):
    ans.append(value[n+1])
print(*ans)

Submission status: Wrong Answer

Solution code:

from collections import deque

n, q = map(int, input().split())
t = {}
rt = {}
tp = {1: 0}

for i in range(n-1):
    a, b = map(int, input().split())
    if a in t.keys():
        t[a].append(b)
    else:
        t.setdefault(a, [b])
        if a != 1:
            rt.setdefault(b, [a])
    tp.setdefault(b, 0)
    tp.setdefault(a, 0)

#print(t)
#print(rt)
#print(tp)

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


#print(tp)

####
stack=deque()
stack.append(1)
visitted={}

while stack:
    cur = stack.popleft()
    visitted.setdefault(cur, 1)
    #print(stack)
    #print(cur)
    if cur not in t.keys():
        if cur not in rt.keys():
            continue
        for w in rt[cur]:
            if w in visitted.keys():
                continue
            stack.append(w)
            tp[w]=tp[w]+tp[cur]
        continue
    for v in t[cur]:
        if v in visitted.keys():
            continue
        stack.append(v)
        tp[v]=tp[v]+tp[cur]

print(*tp.values(), sep=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque

n, q = map(int, input().split())
t = {}
rt = {}
tp = {1: 0}

for i in range(n-1):
    a, b = map(int, input().split())
    if a in t.keys():
        t[a].append(b)
    else:
        t.setdefault(a, [b])
        if a != 1:
            rt.setdefault(b, a)
    tp.setdefault(b, 0)
    tp.setdefault(a, 0)

#print(t)
#print(rt)
#print(tp)

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


#print(tp)

####
stack=deque()
stack.append(1)
visitted={}

while stack:
    cur = stack.popleft()
    visitted.setdefault(cur, 1)
    #print(stack)
    #print(cur)
    if cur not in t.keys():
        continue
    for v in t[cur]:
        if v in visitted.keys():
            continue
        stack.append(v)
        tp[v]=tp[v]+tp[cur]

print(*tp.values(), sep=' ')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, Q = map(int, input().split())
tree = defaultdict(list)
counter = [0] * N
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)

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

queue = deque()
queue.append(0)
while queue:
    parent = queue.popleft()
    for child in tree[parent]:
        counter[child] += counter[parent]
        queue.append(child)
print(' '.join(map(str, counter)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, Q = map(int, input().split())
tree = defaultdict(list)
is_root = [True] * N
counter = [0] * N
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    is_root[b-1] = False

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

root = is_root.index(True)
queue = deque()
queue.append(root)
while queue:
    parent = queue.popleft()
    for child in tree[parent]:
        counter[child] += counter[parent]
        queue.append(child)
print(' '.join(map(str, counter)))

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
AB = []
for _ in range(N-1):
    AB.append(list(map(int,input().split())))
PX = []
for _ in range(M):
    PX.append(list(map(int,input().split())))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
for ab in AB:
    tree[ab[0]].append(ab[1])
ans = [0]*N
for px in PX:
    Q = deque([px[0]])
    ans[px[0]-1] += px[1]
    while Q:
        q = Q.popleft()
        for c in tree[q]:
            ans[c-1] += px[1]
            Q.append(c)
print(" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from collections import deque
n,q = map(int,input().split())
nei_mat = []
nei_list = [[0]]
score_list = [0] * (n+1)
for i in range(n+1):
    nei_mat.append([0]*(n+1))
for i in range(n-1):
    a,b = map(int,input().split())
    nei_mat[a][b] = 1
for i in range(1,n+1):
    work_q = deque([])
    work_q.append(i)
    visited = []
    while work_q:
        cal = work_q.popleft()
        visited.append(cal)
        for j in range(cal, n+1):
            if nei_mat[cal][j] == 1:
                work_q.append(j)
    nei_list.append(visited)
for i in range(q):
    p,x = map(int,input().split())
    for j in range(len(nei_list[p])):
        score_list[nei_list[p][j]] += x
print(*score_list[1:])

Submission status: Wrong Answer

Solution code:
from collections import deque
n,q = map(int,input().split())
nei_mat = []
nei_list = [[0]]
score_list = [0] * (n+1)
for i in range(n+1):
    nei_mat.append([0]*(n+1))
for i in range(n-1):
    a,b = map(int,input().split())
    nei_mat[a][b] = 1
for i in range(1,n+1):
    work_q = deque([])
    work_q.append(i)
    visited = []
    while work_q:
        cal = work_q.popleft()
        visited.append(cal)
        for j in range(cal, n+1):
            if nei_mat[cal][j] == 1:
                work_q.append(j)
    nei_list.append(visited)
print(nei_list)
for i in range(q):
    p,x = map(int,input().split())
    for j in range(len(nei_list[p])):
        score_list[nei_list[p][j]] += x
print(*score_list[1:])

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
ab_lis = []
for i in range(n - 1):
    ab_lis.append(list(map(int, input().split())))
p_lis = []    
for i in range(q):
    p_lis.append(list(map(int, input().split())))
import collections
d = collections.defaultdict(list)
for i in range(n - 1):
    for tmp_key in d.keys():
        if (ab_lis[i][0] in d[tmp_key] or ab_lis[i][0] == tmp_key) and ab_lis[i][1] not in d[tmp_key]:
            d[tmp_key].append(ab_lis[i][1])
    if ab_lis[i][0] not in d:
        d[ab_lis[i][0]].append(ab_lis[i][1])
ans = [0] * n
for i in range(q):
    tmp_num, tmp_add = p_lis[i][0], p_lis[i][1]
    ans[tmp_num - 1] += tmp_add
    for tmp_val in d[tmp_num]:
        ans[tmp_val - 1] += tmp_add
for tmp_ans in ans:
    print(tmp_ans)

Submission status: Wrong Answer

Solution code:
N,Q = list(map(int,input().split()))
AB = []
for _ in range(N-1):
    AB.append(list(map(int,input().split())))
PX = []
for _ in range(Q):
    PX.append(list(map(int,input().split())))
from collections import defaultdict as ddict
tree = ddict(list)
for ab in AB:
    tree[ab[0]].append(ab[1])
from collections import deque
ans = [0] * N
for px in PX:
    Q = deque([px[0]])
    ans[px[0]-1] += px[1]
    while Q:
        q = Q.popleft()
        for child in tree[q]:
            Q.append(child)
            ans[child-1] += px[1]
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
N,Q = list(map(int,input().split()))
AB = []
for _ in range(N-1):
    AB.append(list(map(int,input().split())))
PX = []
for _ in range(Q):
    PX.append(list(map(int,input().split())))
from collections import defaultdict as ddict
tree = ddict(list)
for ab in AB:
    tree[ab[0]].append(ab[1])
from collections import deque
ans = [0] * N
for px in PX:
    Q = deque([px[0]])
    while Q:
        q = Q.popleft()
        for child in tree[q]:
            Q.append(child)
            ans[child-1] += px[1]
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

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

N,Q = map(int,input().split())
# child[i]: 頂点iの子ノードの集合
child = [[] for _ in range(N+1)]
# parent[i]: 頂点iの親ノード
parent = [0]*(N+1)
for _ in range(N-1):
    a,b = map(int,input().split())
    child[a].append(b)
    parent[b] = a

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

# nowを根とする子ノードにanswer[now]を足す
# O(N)
def dfs(now):
    # nowが葉のとき
    if not child[now]:
        return
    for i in child[now]:
        answer[i] += answer[now]
        dfs(i)

dfs(1)

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

Submission status: Wrong Answer

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

A=[[0]*2 for i in range(N-1)]
Ans=[0]*N
P=[[0]*2 for i in range(Q)]

for i in range(N-1):
    A[i][0],A[i][1] = map(int, input().split())
for i in range(Q):
    P[i][0],P[i][1] = map(int, input().split())
    Ans[P[i][0]-1]+=P[i][1]
A=sorted(A,key=lambda x: x[0])

for i in range (N-1):
    Ans[A[i][1]-1]+=Ans[A[i][0]-1]
print(*Ans)

Submission status: Wrong Answer

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

A=[[0]*2 for i in range(N-1)]
Ans=[0]*N
P=[[0]*2 for i in range(Q)]

for i in range(N-1):
    A[i][0],A[i][1] = map(int, input().split())
for i in range(Q):
    P[i][0],P[i][1] = map(int, input().split())
A=sorted(A,key=lambda x: x[0])
P=sorted(P,key=lambda x: x[0])

for i in range (Q):
    Ans[P[i][0]-1]+=P[i][1]
for i in range (N-1):
    Ans[A[i][1]-1]+=Ans[A[i][0]-1]
print(*Ans)

Submission status: Wrong Answer

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

A=[[0]*2 for i in range(N-1)]
Ans=[0]*N
P=[[0]*2 for i in range(Q)]

for i in range(N-1):
    A[i][0],A[i][1] = map(int, input().split())
for i in range(Q):
    P[i][0],P[i][1] = map(int, input().split())
A=sorted(A,key=lambda x: x[0])
P=sorted(P,key=lambda x: x[0])

for i in range (Q):
    Ans[P[i][0]-1]+=P[i][1]
for i in range (N-1):
    Ans[A[i][1]-1]+=Ans[A[i][0]-1]
for i in range(N-1):
    print(Ans[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
E = [MAP() for _ in range(N-1)]
O = [MAP()for _ in range(Q)]

G = [[] for _ in range(N)]
for e in E:
	G[e[0]-1].append(e[1]-1)
	
#print(G)
C = [0 for _ in range(N)]

for v, p in O:
	c = deque()
	c.append(v-1)
	while c:
		target = c.pop()
		C[target] += p
		for g in G[target]:
			c.append(g)

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
E = [MAP() for _ in range(N-1)]
O = [MAP()for _ in range(Q)]

G = [[] for _ in range(N)]
for e in E:
	G[e[0]-1].append(e[1]-1)
	
#print(G)
C = [0 for _ in range(N)]

for v, p in O:
	c = []
	heapq.heapify(c)
	heapq.heappush(c,v-1)
	while c:
		target = heapq.heappop(c)
		C[target] += p
		for g in G[target]:
			heapq.heappush(c, g)

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

Submission status: Wrong Answer

Solution code:
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
E = [MAP() for _ in range(N-1)]
O = [MAP()for _ in range(Q)]

G = [[] for _ in range(N)]
for e in E:
	G[e[0]-1].append(e[1]-1)
	
#print(G)
C = [0 for _ in range(N)]

for v, p in O:
	child = []
	child.append(v-1)
	while child:
		target = child[0]
		C[target] += p
		child.pop(0)
		for c in G[target]:
			child.append(c)

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n ,q = list(map(int,input().split()))
tree = [[] for i in range(n)]
for i in range(n-1):
    ai,bi = list(map(int,input().split()))
    tree[ai-1].append(bi)
#print(tree)
cnt = [0]*n
for j in range(q):
    pj,xj = list(map(int,input().split()))
    cnt[pj-1] += xj
    
    tips = []
    for i in range(len(tree[pj-1])):
        tips.append(tree[pj-1][i])
    k = 0 
    while len(tips) > k:
        current = tips[k]
#        print(j,pj,tips,cnt)
        cnt[current - 1] += xj
        tips.extend(tree[current - 1])
#        print(tree,tree[current - 1])
        k += 1
print(*cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,q = map(int,input().split())
ki = [[] for _ in range(n)]
qi = [0]*max(n,q)
ans = [0]*n
for i in range(n-1):
    a,b = map(lambda x:int(x)-1,input().split())
    ki[min(a,b)].append(max(a,b))
for i in range(q):
    p,x = map(int,input().split())
    qi[p-1] += x
que1 = deque([0])
que2 = deque([0])
while len(que1)>0:
    i = que1.popleft()
    i2 = que2.popleft()
    ans[i] = i2 + qi[i]
    que1.extend(ki[i])
    que2.extend([ans[i] for _ in range(len(ki[i]))])
print(*ans)

Submission status: Wrong Answer

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

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

# 1に近い順にソート
edges.sort()

for i in range(N-1):
    a, b = edges[i]
    counters[b-1] += counters[a-1]

for i in range(N):
    print(counters[i], end=' ')

Submission status: Wrong Answer

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

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

# 1に近い順にソート
edges.sort(key=lambda x:x[1])
edges.sort()

for i in range(N-1):
    a, b = edges[i]
    a-=1; b-=1;
    counters[b] += counters[a]

for i in range(N):
    print(counters[i], end=' ')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)

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

    Q=deque([0])
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            C[nv]+=C[v]
            Q.append(nv)

    print(*C)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
    
    C=[0]*n
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        C[p]+=x

    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            C[nv]+=C[v]
            Q.append(nv)

    print(*C)
resolve()