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(10**6)

def DFS(v):
  global v_count
  for u in adj[v]:
    v_count[u] += v_count[v]
    DFS(u)

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

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

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

# 0起点に親ノードの数字を子ノードに足していく
DFS(0)
print(*v_count)

Submission status: Wrong Answer

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

def DFS(v,i,count):
  global ans
  if v == i:# 探索終了
    #print('ans:{}, v:{}'.format(ans,v_count[v]))
    ans[i] = count + v_count[v]
    #print('tmp:{}'.format(tmp))
  for u in adj[v]:
    DFS(u,i,count + v_count[v])

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

adj = [[] for _ in range(N)]
v_count = [0] * N

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

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

# print(v_count)
ans = [None] * N
for i in range(N):
  # iを探索で見つけ出す, そこまで通った頂点のv_count
  # の総和を出力
  DFS(0,i,0)
print(*ans)

Submission status: Wrong Answer

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

def DFS(v,i,count):
  global ans
  if v == i:# 探索終了
    #print('ans:{}, v:{}'.format(ans,v_count[v]))
    ans[i] = count + v_count[v]
    #print('tmp:{}'.format(tmp))
    return 
  for u in adj[v]:
    DFS(u,i,count + v_count[v])

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

adj = [[] for _ in range(N)]
v_count = [0] * N

for i in range(N-1):
  a, b = map(int, input().split())
  adj[a-1].append(b-1)
  
p = [None] * Q
x = [None] * Q

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

# print(v_count)
ans = [None] * N
for i in range(N):
  # iを探索で見つけ出す, そこまで通った頂点のv_count
  # の総和を出力
  DFS(0,i,0)
print(*ans)

Submission status: Wrong Answer

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

def DFS(v,x):
  global v_count
  
  for u in adj[v]:
    v_count[u] += x
    DFS(u,x)

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

adj = [[] for _ in range(N)]
v_count = [0] * N

for i in range(N-1):
  a, b = map(int, input().split())
  adj[a-1].append(b-1)
  
p = [None] * Q
x = [None] * Q

for j in range(Q):
  p[j], x[j] = map(int, input().split())
  
# print(adj,p,x)

for j in range(Q):
  # p[j]を根とする部分木を探索して見つけた頂点にx[j]を足す
  v_count[p[j]-1] += x[j]
  DFS(p[j]-1,x[j])

print(*v_count)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
Nlist = [list(map(int, input().split())) for i in range(N-1)]
Qlist = [list(map(int, input().split())) for i in range(Q)]
anslist = [int("0") for _ in range(N)]
ptrlist = [[] for _ in range(N)]

for i in range(N-1):
    ptrlist[Nlist[i][0]-1].append(Nlist[i][1]-1)

for i in range(Q):
    anslist[Qlist[i][0]-1] += Qlist[i][1]

for i in range(N-1):
    for j in ptrlist[i]:
        anslist[j] += anslist[i]

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

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
Nlist = [list(map(int, input().split())) for i in range(N-1)]
Qlist = [list(map(int, input().split())) for i in range(Q)]
anslist = [int("0") for _ in range(N)]
ptrlist = [[] for _ in range(N)]

for i in range(N-1):
    ptrlist[Nlist[i][0]-1].append(Nlist[i][1]-1)

print(ptrlist)
for i in range(Q):
    anslist[Qlist[i][0]-1] += Qlist[i][1]

for i in range(N-1):
    for j in ptrlist[i]:
        anslist[j] += anslist[i]

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

Submission status: Wrong Answer

Solution code:
#python3
from collections import deque
NIL = -1

class Node:
    def __init__(self):
        self.c = []
        self.p = NIL
        self.cnt = 0

def main():
    n, q = map(int, input().split())
    nodes = [Node() for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        nodes[a].c.append(b)
        nodes[b].p = a
        
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        nodes[p].cnt += x

    deq = deque()
    deq.append(nodes[0])
    while len(deq) > 0:
        node = deq.popleft()
        if node.p != NIL:
            node.cnt += nodes[node.p].cnt
        for i in node.c: 
            deq.append(nodes[i]) 
    
    for i in range(n):
        v = nodes[i].cnt
        if i == n-1:
            print(v)
        else:
            print(v, end=' ')
main()

Submission status: Wrong Answer

Solution code:
#python3
from collections import deque
NIL = -1

class Node:
    def __init__(self):
        self.c = []
        self.p = NIL
        self.cnt = 0

def main():
    n, q = map(int, input().split())
    nodes = [Node() for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        nodes[a].c.append(b)
        nodes[b].p = a
        
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        nodes[p].cnt += x

    deq = deque()
    deq.append(nodes[0])
    while len(deq) > 0:
        node = deq.popleft()
        node.cnt += nodes[node.p].cnt
        for i in node.c: 
            deq.append(nodes[i]) 
    
    for i in range(n):
        v = nodes[i].cnt
        if i == n-1:
            print(v)
        else:
            print(v, end=' ')
main()

Submission status: Wrong Answer

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

rank = {i: 0 for i in range(n)}
nodes = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    nodes[a].append(b)
    rank[b] += 1

dp = [0]*n

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

it = [x for x, y in sorted(rank.items(), key=lambda x: x[1])]
for i in it:
    for idx in nodes[i]:
        dp[idx] += dp[i]

print(*dp)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
Nlist = [list(map(int, input().split())) for i in range(N-1)]
Qlist = [list(map(int, input().split())) for i in range(Q)]
anslist = [int("0") for _ in range(N)]
for i in range(Q):
    anslist[Qlist[i][0]-1] += Qlist[i][1]

for i in range(N-1):
    anslist[Nlist[i][1]-1] += anslist[Nlist[i][0]-1]

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

Submission status: Wrong Answer

Solution code:
def dfs(v):
    stack = [v]
    list = []
    while stack:
        v = stack[-1]
        if v in list:
            stack.pop(-1)
        else:
            if tree[v] == []:
                stack.pop(-1)
            else:
                for t in tree[v]:
                    stack.append(t)
            
            list.append(v)
 
    return list
    
 
N,Q = map(int, input().split())
tree = [[] for i in range(N)]
dfs_ans = [[] for i in range(N)]
 
ans =[0]*N
 
for _ in range(N-1):
    a,b = map(int, input().split())
    tree[a-1].append(b-1)
 
for i in range(N):
    dfs_ans[i] = dfs(i)

P=[0]*N
for _ in range(Q):
    p,x = map(int, input().split())
    P[p-1] += x
    
for i in range(N):
    if P[i] != 0:
        for t in dfs_ans[i]:
            ans[t] += P[i]
 
for i in range(N):
    if i != N-1:
        print(ans[i], end=" ")
    else:
        print(ans[i], end="")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
n, q = map(int, input().split())

outs = defaultdict(list)
ins = defaultdict(int)

nodes = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    nodes[a].append(b)
    outs[a].append(b)
    ins[b] += 1


d = deque(v1 for v1 in range(n) if ins[v1] == 0)
res = []
while d:
    v1 = d.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            d.append(v2)


dp = [0]*n

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

for i in res:
    for idx in nodes[i]:
        dp[idx] += dp[i]

print(*dp)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
Nlist = [list(map(int, input().split())) for i in range(N-1)]
Qlist = [list(map(int, input().split())) for i in range(Q)]
anslist = [int("0") for _ in range(N)]
ptrlist = [[i] for i in range(N)]
Nlist.sort()
for i in range(Q):
    anslist[Qlist[i][0]-1] += Qlist[i][1]

for i in range(N-1):
    anslist[Nlist[i][1]-1] += anslist[Nlist[i][0]-1]

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

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
nodes = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    nodes[a].append(b)
    
dp = [0]*n

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

for i in range(n):
    for idx in nodes[i]:
        dp[idx] += dp[i]

print(*dp)

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(v):
    stack = [v]
    list = []
    while stack:
        v = stack[-1]
        if v in list:
            stack.pop(-1)
        else:
            if tree[v] == []:
                stack.pop(-1)
            else:
                for t in tree[v]:
                    stack.append(t)
            
            list.append(v)

    return list
    

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

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

for i in range(N):
    dfs_ans[i] = dfs(i)

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(v):
    stack = [v]
    list = []
    while stack:
        v = stack[-1]
        if v in list:
            stack.pop(-1)
        else:
            if tree[v] == []:
                stack.pop(-1)
            else:
                for t in tree[v]:
                    stack.append(t)
            
            list.append(v)

    return list
    

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

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

for i in range(N):
    dfs_ans[i] = dfs(i)

for _ in range(Q):
    p,x = map(int, input().split())
    if dfs_ans[p-1]:
        for t in dfs_ans[p-1]:
            ans[t] += x
    
print(ans)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
Nlist = [list(map(int, input().split())) for i in range(N-1)]
Qlist = [list(map(int, input().split())) for i in range(Q)]
anslist = [int("0") for _ in range(N)]
ptrlist = [[i] for i in range(N)]

for i in range(Q):
    anslist[Qlist[i][0]-1] += Qlist[i][1]

for i in range(N-1):
    anslist[Nlist[i][1]-1] += anslist[Nlist[i][0]-1]

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

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
Nlist = [list(map(int, input().split())) for i in range(N-1)]
Qlist = [list(map(int, input().split())) for i in range(Q)]
anslist = [int("0") for _ in range(N)]
ptrlist = [[i] for i in range(N)]

for i in range(Q):
    for j in ptrlist[Qlist[i][0]-1]:
        anslist[j] += Qlist[i][1]

for i in range(N-1):
    anslist[Nlist[i][1]-1] += anslist[Nlist[i][0]-1]

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        memo[nv] += memo[v]
        dfs(nv, v)

n, q = na()
g = [deque() for _ in range(n)]
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
memo = [0] * n
for i in range(q):
    #seen = [False] * n
    p, x = na()
    p -= 1
    memo[p] += x

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def dfs(g, v, x):
    #seen[v] = True
    s[v] += x
    for nv in g[v]:
        #if seen[nv]: continue
        dfs(g, nv, x)

n, q = na()
g = [deque() for _ in range(n)]
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
s = [0] * n
for i in range(q):
    #seen = [False] * n
    p, x = na()
    p -= 1
    dfs(g, p, x)
print(*s)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def dfs(g, v, x):
    seen[v] = True
    s[v] += x
    for nv in g[v]:
        if seen[nv]: continue
        dfs(g, nv, x)

n, q = na()
g = [deque() for _ in range(n)]
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
s = [0] * n
for i in range(q):
    seen = [False] * n
    p, x = na()
    p -= 1
    dfs(g, p, x)
print(*s)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def dfs(g, v, x):
    seen[v] = True
    s[v] += x
    for nv in g[v]:
        if seen[nv]: continue
        dfs(g, nv, x)

n, q = na()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
s = [0] * n
for i in range(q):
    seen = [False] * n
    p, x = na()
    p -= 1
    dfs(g, p, x)
print(*s)

Submission status: Wrong Answer

Solution code:
m=lambda:map(int,input().split())
n,q=m()
edges=[set()for _ in range(n)]
for i in range(n-1):
    a,b=m()
    a-=1;b-=1
    edges[a].add(b);edges[b].add(a)
rank={}
R=[0]
par={}
r=0;rep=[];pre=[0]
cnt=n-1
ok=[0]*n
ok[0]=1
while cnt!=0:
    ret=0;r+=1
    for i in pre:
        for j in edges[i]:
            if ok[j]:continue
            ok[j]=1
            rank[j]=r
            ret+=1
            par[j]=i
            rep.append(j)
    cnt-=ret
    pre=rep;rep=[]
    R+=pre
cou=[0]*n
for _ in range(q):
    root,v=m()
    root-=1
    cou[root]+=v
rcou=[0]*n;rcou[0]=cou[0]
print(cou[0])
for i in R[1:]:
    p=cou[i]+rcou[par[i]]
    print(p)
    rcou[i]=p

Submission status: Wrong Answer

Solution code:
#import deque
import sys

sys.setrecursionlimit(10**6)

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

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

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

ans = [0] * N
def dfs(v, counter):
    counter += score[v]
    ans[v] = counter
    for u in Graph[v]:
        dfs(u, counter)

dfs(0, 0)

print(*ans)

Submission status: Wrong Answer

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

for op in operations:
    p, x = op
    counts[p-1] += x
    
for point in range(1, N+1):
    for e in edges:
        a, b = e
        if a == point:
            counts[b-1] += counts[a-1]

res = ""
for c in counts:
    res += " " + str(c)
    
print(res[1:])

Submission status: Wrong Answer

Solution code:
#import deque
import sys

sys.setrecursionlimit(10**6)

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

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

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

ans = [0] * N
def dfs(v, counter):
    tmpscore = score[v] + counter
    ans[v] = tmpscore
    tolist = Graph[v]
    for u in tolist:
        dfs(u, tmpscore)

dfs(0, 0)

print(*ans)

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

PATH = [[] for _ in range(N + 1)]

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

POINT = [0] * (N + 1)

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


ans = [0] * (N+1)


def dfs(s, plus):
    p = POINT[s]
    pt = p + plus
    ans[s] += pt

    for v in PATH[s]:
        if ans[v] > 0:
            continue
        dfs(v, pt)


dfs(1, 0)
print(" ".join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
ki = [[] for i in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  ki[a-1].append(b-1)

score = [0] * n
for i in range(q):
  a, b = map(int, input().split())
  score[a-1] += b
def dfs(now):
  for i in ki[now]:
    score[i] += score[now]
    dfs(i)
dfs(0)
print(*score)

Submission status: Wrong Answer

Solution code:

from collections import deque


def read_input():
    n, q = map(int, input().split())
    
    # 有向辺を整理
    edges = {i: [] for i in range(n)}
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edges[a - 1].append(b - 1)
    # カウントを整理
    counter = {i: 0 for i in range(n)}
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p - 1] += x
    
    return n, edges, counter


def submit():
    n, edges, counter = read_input()

    # 深さ優先探索で各頂点のカウントを調べる
    v_count = {i: -1 for i in range(n)}
    q = deque()
    q.append((0, 0))
    while len(q):
        p, c = q.pop()
        if v_count[p] > 0:
            continue

        v_count[p] = c + counter[p]    
        for e in edges[p]:
            q.append((e, v_count[p]))

    res = []
    for i in range(n):       
        res.append(v_count[i])
    print(" ".join(map(str, res)))


submit()

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
ab = [list(map(int,input().split())) for _ in range(n-1)]

ab.sort()
li = [0]*n

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

for i in range(n-1):
    a, b = ab[i]
    li[b-1] += li[a-1]

for j in li:
    print(j, end=" ")

Submission status: Wrong Answer

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

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

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

def dfs(now, last, x):
    global node
    node[now]+=x
    for nxt in edge[now]:
        dfs(nxt, now, x)

node=[0] * (n)
for _ in range(q):
    p,x=[int(i) for i in input().split()]
    dfs(p-1, -1, x)
        
print(*node)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
desc = [None] + [set() for _ in range(N)]
for _ in range(N - 1):
    ai, bi = map(int, input().split())
    desc[ai].add(bi)

counter = [None] + [0] * N
for _ in range(Q):
    pi, xi = map(int, input().split())
    counter[pi] += xi
for p in range(1, N + 1):
    for d in desc[p]:
        counter[d] += counter[p]

print(*counter[1:])

Submission status: Wrong Answer

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

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

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

def dfs(now, last, x):
    global node
    node[now]+=x
    for nxt in edge[now]:
        if nxt == last: continue
        if nxt > now: dfs(nxt, now, x)

node=[0] * (n)
for _ in range(q):
    p,x=[int(i) for i in input().split()]
    dfs(p-1, -1, x)
print(*node)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

que=deque([0])
while que:
    s=que.popleft()
    V[s]=True
    for ni in E[s]:
        if V[ni]==False:
            P[ni]+=P[s]
            que.append(ni)
print(*P)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,q=map(int,input().split())
E=[[]for _ in range(n)]
P=[0]*n
V=[False]*n
for i in range(n-1):
    a,b=map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
for i in range(q):
    p,x=map(int,input().split())
    P[p-1]=x

que=deque([0])
while que:
    s=que.popleft()
    V[s]=True
    for ni in E[s]:
        if V[ni]==False:
            P[ni]+=P[s]
            que.append(ni)
print(*P)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,q=map(int,input().split())
E=[set()for _ in range(n)]
P=[0]*n
V=[False]*n
for i in range(n-1):
    a,b=map(int,input().split())
    E[a-1].add(b-1)
    E[b-1].add(a-1)
for i in range(q):
    p,x=map(int,input().split())
    P[p-1]=x

que=deque([0])
while que:
    s=que.popleft()
    V[s]=True
    for ni in E[s]:
        if V[ni]==False:
            P[ni]+=P[s]
            que.append(ni)
print(*P)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,q=map(int,input().split())
E=[set()for _ in range(n)]
P=[0]*n
V=[False]*n
for i in range(n-1):
    a,b=map(int,input().split())
    E[a-1].add(b-1)
for i in range(q):
    p,x=map(int,input().split())
    P[p-1]=x

que=deque([0])
while que:
    s=que.popleft()
    V[s]=True
    for ni in E[s]:
        if V[ni]==False:
            P[ni]+=P[s]
            que.append(ni)
print(*P)

Submission status: Wrong Answer

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

import sys
from collections import defaultdict

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


class Graph(object):
    """ Graph data structure, undirected by default. """

    def __init__(self, connections, directed=False):
        self._graph = defaultdict(set)
        self._directed = directed
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections (list of tuple pairs) to graph """

        for u, v in connections:
            self.add(u, v)

    def add(self, u, v):
        """ Add connection between node u and node v """

        self._graph[u].add(v)
        if not self._directed:
            self._graph[v].add(u)

    def get_adj(self, v):
        """ Get adjacency list of node v """
        return self._graph[v]

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._graph))


# -----
N, Q = map(int, input().split())
connections = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    connections.append((a, b))
query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])
# print(N, Q)
# print(connections, query)

keys = [v for v in range(1, N + 1)]
values = [0 for _ in range(N)]
counter = dict(zip(keys, values))
# print(counter)
for p, x in query:
    counter[p] += x


def dfs(v, parent):
    for v_next in g.get_adj(v):
        if v_next != parent:
            counter[v_next] += counter.get(v)
            dfs(v_next, v)


g = Graph(connections)
# print(g)

root = 1
dfs(root, None)

print(*counter)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
N, Q = map(int, input().split())
#G = dict([[i, -1] for i in range(N)])
G2 = dict([[i, []] for i in range(N)])
for _ in range(N-1):
    a, b = map(int, input().split())
    #G[b-1] = a-1
    G2[a-1].append(b-1)
P = [list(map(int, input().split())) for _ in range(Q)]
# print(G)
C = [0] * N
# print(G2)
visited = [False] * N


def dfs(v):
    visited[v] = True
    for nv in G2[v]:
        if not visited[nv]:
            C[nv] += C[v]
            dfs(nv)


# 1
C = [0] * N

# 2
for p, x in P:
    C[p-1] += x
# print(C)
# 3
dfs(0)
# 4
print(*C)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
N, Q = map(int, input().split())
#G = dict([[i, -1] for i in range(N)])
G2 = dict([[i, []] for i in range(N)])
for _ in range(N-1):
    a, b = map(int, input().split())
    #G[b-1] = a-1
    G2[a-1].append(b-1)
P = [list(map(int, input().split())) for _ in range(Q)]
# print(G)
C = [0] * N
# print(G2)


def dfs(v):
    for nv in G2[v]:
        C[nv] += C[v]
        dfs(nv)


# 1
C = [0] * N

# 2
for p, x in P:
    C[p-1] += x
# print(C)
# 3
dfs(0)
# 4
print(*C)

Submission status: Wrong Answer

Solution code:
#abc138d
n,q=map(int,input().split())
t=[0]*(n+1)
v=[0]*(n+1)
for i in range(n-1):
 a,b=map(int,input().split())
 t[b]=a
for i in range(q):
 p,x=map(int,input().split())
 v[p]+=x
for i in range(1,n+1):
 v[i]+=v[t[i]]
print(*v[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
N, Q = map(int, input().split())
G = dict([[i, -1] for i in range(N)])
for _ in range(N-1):
    a, b = map(int, input().split())
    G[b-1] = a-1
P = [list(map(int, input().split())) for _ in range(Q)]
# print(G)
# 1
C = [0] * N

# 2
for p, x in P:
    C[p-1] += x
# print(C)
# 3
for i in range(1, N):
    C[i] += C[G[i]]
# 4
print(*C)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
N, Q = map(int, input().split())
G = dict([[i, []] for i in range(N)])
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
C = [0] * N
visited = [False] * N
# print(G)


def dfs(p, x):
    if visited[p]:
        return

    C[p] += x

    for v in G[p]:
        dfs(v, x)


for _ in range(Q):
    p, x = map(int, input().split())
    visited = [False] * N
    dfs(p-1, x)

print(*C)

Submission status: Wrong Answer

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

n,q = map(int,input().split())
costs = [0]*n
net = [[] for _ in range(n)]
for _ in range(1,n):
	a,b = map(int,input().split())	
	a -= 1
	b -= 1
	net[a].append(b)
#	net[b].append(a)
	
for _ in range (q):
	p,x = map(int,input().split())
	costs[p-1] += x

def dfs(parents,checked_par):
	for children in net[parents]:
		if children == checked_par:
			continue
		costs[children] += costs[parents]
		dfs(children,parents)
dfs(0,-1)

print(*costs)

Submission status: Wrong Answer

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

n,q = map(int,input().split())
costs = [0]*n
net = [[] for _ in range(n)]
for _ in range(1,n):
	a,b = map(int,input().split())	
	a -= 1
	b -= 1
	net[a].append(b)
#	net[b].append(a)
	
for _ in range (q):
	p,x = map(int,input().split())
	costs[p-1] += x

def dfs(parents):
	for children in net[parents]:
		if children == -1:
			continue
		costs[children] += costs[parents]
		dfs(children)
dfs(0)

print(*costs)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
tree = {}
for _ in range(n-1):
  root , node = map(lambda x:int(x)-1, input().split())
  if root not in tree:
    tree[root] = [node]
  else:
    tree[root].append(node)

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    if now in tree:
      for root in tree[now]:
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
tree = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    for root in tree:
      if root[0] == now:
        ans[root[1]] += tmp
        will_go.append(root[1])
        
print(*ans)

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(1,n)]
a.sort()
costs = [0]*(n+1)
for _ in range (q):
	p,x = map(int,input().split())
	costs[p] += x

for i in range(n-1):
	costs[a[i][1]] += costs[a[i][0]]	
print(*costs[1:])

Submission status: Wrong Answer

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

for i in range(n-1):
	costs[a[i][1]-1] += costs[a[i][0]-1]	
print(*costs)

Submission status: Wrong Answer

Solution code:

N, Q=map(int, input().split())
value=[0]*N
#各ノードの下につくノード

oya=[-1]*N
for i in range(N-1):
  a,b=map(int, input().split())
  
  oya[b-1]=a-1
  
#adds=[0]*N



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

for i in range(N):
  if i >0:
    value[i]+=value[oya[i]]
    ans=value[i]
  else:
    ans=value[i]
  print(ans, end=" ")

Submission status: Wrong Answer

Solution code:
N, Q=map(int, input().split())
value=[0]*N
#各ノードの下につくノード

oya=[-1]*N
for i in range(N-1):
  a,b=map(int, input().split())
  
  oya[b-1]=a-1
  
#adds=[0]*N



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

for i in range(N):
  if i >0:
    value[i]+=value[oya[i]]
    ans=value[i]
  else:
    ans=value[i]
  print(ans, end=" ")