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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, Q = LI()
    A, B, P, X = [], [], [], []
    memo = [0 for _ in range(N)]
    ans = [0 for _ in range(N)]
    for _ in range(N-1):
        _a, _b = LI()
        A.append(_a-1)
        B.append(_b-1)
    for _ in range(Q):
        _p, _x = LI()
        memo[_p-1] += _x
        #P.append(_p-1)
        #X.append(_x)
    ans[0] += memo[0]
    for i in range(N-1):
        a_nodenum = A[i]
        b_nodenum = B[i]
        ans[b_nodenum] += (ans[a_nodenum] + memo[b_nodenum])
    for i in ans:
        print(i, end=" ")
    print()
main()

Submission status: Wrong Answer

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

tree = [set([i]) for i in range(N+1)]
tree_parent = [set() for i in range(N+1)]
points = [0] * N

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

for i in range(Q):
  p, x = map(int, input().split())
  for node in tree[p]:
    points[node-1] += x
    
for point in points:
  print(point, end=" ")

Submission status: Wrong Answer

Solution code:
from sys import stdin

ntree = []
ans = []


def culceach(n, sum):
    ans[n-1] += sum
#    for i in range(len(ntree[n-1])):
#        culceach(ntree[n-1][i], ans[n-1])

n, q = [int(x) for x in stdin.readline().rstrip().split()]

for i in range(n):
    ntree.append([])
    ans.append(0)

for i in range(n-1):
  a, b = [int(x) for x in stdin.readline().rstrip().split()]
  ntree[a-1].append(b)

for i in range(q):
  p, x = [int(x) for x in stdin.readline().rstrip().split()]
  ans[p-1] += x

culceach(1, 0)

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
N, Q = list(map(int, stdin.readline().rstrip().split(' ')))
edge = [list(map(int, stdin.readline().rstrip().split(' '))) for _ in range(N-1)]
vals = [list(map(int, stdin.readline().rstrip().split(' '))) for _ in range(Q)]

res = [0] * N
for i, v in vals:
    res[i-1] = res[i-1] + v

for p, d in edge:
    res[d-1] = res[d-1] + res[p-1]

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

Submission status: Wrong Answer

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

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

    if a not in tree_dict:
        tree_dict[a] = [b]
    else:
        tree_dict[a].append(b)

value_dict = {k:0 for k in list(set(ab_list))}

p_list = []
x_list = []
for i in range(Q):
    p, x = map(int, input().split())
    p_list.append(p)
    x_list.append(x)

for p, x in zip(p_list, x_list):
    f = 0
    for k, v in value_dict.items():
        if k == p:
            kk_list = [k]
            while(1):
                if len(kk_list) == 0:
                    f = 1
                    break
                k = kk_list[0]
                value_dict[k] += x
                if k in tree_dict:
                    kk_list += tree_dict[k]
                kk_list.pop(0)
        if f == 1:
            break

print(value_dict)

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

# print(x_sorted)

start = 0
# コストテーブルの作成
from heapq import heappop, heappush
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)]
# print(cost)

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

qq = [] # min-heap, (距離, 頂点)
heappush(qq, (d[start], start))
while qq:
    du, u = heappop(qq) # 最短距離とその頂点
    if d[u] < du:
        continue
    for v, weight in cost.get(u, []):
        alt = du + weight
        if d[v] > alt:
            d[v] = alt
            heappush(qq, (alt, v))

Submission status: Wrong Answer

Solution code:
import copy
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
l2=[list(map(int,input().split())) for i in range(q)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[0 for i in range(n)]
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
oya=0
L2=[]
L3=[]
ct=1
while len(L2)!=3*n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[L[j]+1]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
  ct+=1
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))

Submission status: Wrong Answer

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

from collections import defaultdict, Counter
def increment(key, count, adj_list, inc_num, visited):
    if key in visited:
        return
    count[key] += inc_num
    visited.add(key)
    for num in adj_list[key]:
        visited = increment(num, count, adj_list, inc_num, visited)
    return visited

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

print(' '.join([str(num) for num in count.values()]))

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
Ki_p = [0 for i in range(N+1)]
Ki_ch = [[] for i in range(N+1)]
Ki_co = [0 for i in range(N+1)]
v = set([1])

for i in range(N-1):
    a,b = map(int,input().split())
    if a in v:    
        Ki_p[b] = a
        Ki_ch[a].append(b)
        v.add(b)
    elif b in v:
        Ki_p[a] = b
        Ki_ch[b].append(a)
        v.add(a)

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

ans = [0 for i in range(N+1)]
vc = [1]
while len(vc) > 0:
    vi = vc.pop(0)
    ans[vi] = Ki_co[vi] + ans[Ki_p[vi]]
    vc += Ki_ch[vi]

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

Submission status: Wrong Answer

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

from collections import defaultdict, Counter
def increment(key, count, adj_list, inc_num, visited):
    if key in visited:
        return
    count[key] += inc_num
    visited.add(key)
    for num in adj_list[key]:
        increment(num, count, adj_list, inc_num, visited)

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

print(' '.join([str(num) for num in count.values()]))

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(N-1)]
px=[list(map(int,input().split())) for i in range(Q)]
c=[[] for i in range(N)]
for a,b in ab:
    c[a-1].append(b-1)
    c[b-1].append(a-1)
X=[0]*N
for p,x in px:
    X[p-1]+=x
A=[0]*N
A[0]+=X[0]
import sys
sys.setrecursionlimit(10**6)
def dfs(p,A):
    for n in c[p]:
        if A[n]==0:
            A[n]=X[n]+A[p]
            dfs(n,A)
dfs(0,A)
print(*A)

Submission status: Wrong Answer

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

Tree = dict()
for _ in range(1, N):
    a, b = map(int, input().split())
    if not a in Tree.keys():
        Tree[a] = [b]
    else:
        Tree[a].append(b)

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

scores = [0 for _ in range(N)]
for i in range(Q):
    p = P[i]
    x = X[i]
    scores[p - 1] += x
    if p in Tree.keys():
        adder = Tree[p].copy()
        while adder:
            for add in adder:
                adder.remove(add)
                scores[add - 1] += x
                if add in Tree.keys():
                    adder.extend(Tree[add])

print(scores)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
ko=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int, input().split())
    ko[a-1].append(b-1)
ans=[0]*n
for i in range(q):
    a,b=map(int, input().split())
    ans[a-1]+=b
nex=[0]
while nex:
    p=nex.pop()
    for i in ko[p]:
        ans[i]+=ans[p]
        nex+=ko[i-1]
print(*ans)

Submission status: Wrong Answer

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

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

V = [0]*(N+1)

A = []
for i in range(N-1):
    a,b = map(int, input().split())
    A.append((a,b))
P = []
for i in range(Q):
    x,y = map(int, input().split())
    P.append((x,y))
P.sort()

#print(V)
#print(A)
#print(P)

for p in P:
    V[p[0]] += p[1]
for a in A:
    V[a[1]] += V[a[0]]
V.remove(V[0])

print(*V)

Submission status: Wrong Answer

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

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

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

#print(edge,add_list)

ans = [0] * n
edge_list = [[] for i in range(n)]

for e in edge:
    edge_list[e[1]-1].append(e[0]-1)

add_value = [0]*n
for v in add_list:
    add_value[v[0]-1] += v[1]

#print(edge_list)
#print(add_value)


dp = [-1] * n
def get_value(i):
    if(dp[i]!=-1):
        return dp[i]
    tmp = add_value[i]
    for e in edge_list[i]:
        tmp += get_value(e)
    dp[i] = tmp
    return dp[i]

for i in range(n):
    ans[i] = get_value(i)
    #print(i,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline

dic = defaultdict(list)
n, q = map(int, input().split())

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

tree = [0]*(n+1)

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

for i in range(1, n-1):
    count = tree[i]
    for to in dic[i]:
        tree[to] += count

print(' '.join(map(str, tree)).lstrip(' 0 '))

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(n-1):
            if(ab[j][0] in br):
                br.add(ab[j][1])
        
        for k in br:
            ans[k-1] += x
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)]

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

# x_sorted

start = 0
# コストテーブルの作成
from heapq import heappop, heappush
inf = float('inf')
prev = [None] * n # 経路をたどるときに使う
cost = dict() # コストテーブル
for i, j in ab:
    c = x_sorted[i - 1]
    cost[i - 1] = cost.get(i - 1, []) + [(j - 1, c)]
# print(cost)

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

qq = [] # min-heap, (距離, 頂点)
heappush(qq, (d[start], start))
while qq:
    # print(q, d, prev)
    du, u = heappop(qq) # 最短距離とその頂点
    if d[u] < du:
        continue
    for v, weight in cost.get(u, []):
        alt = du + weight
        if d[v] > alt:
            d[v] = alt
            prev[v] = u
            heappush(qq, (alt, v))


ans = [0] * n
for i in range(n):
    ans[i] = d[i] + x_sorted[i]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,Q = map(int,input().split())
d = defaultdict(list)

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

c = defaultdict(int)

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

ans = defaultdict(int)
que = [(1,0)]
while len(que)>0:
    tmp = []
    for v,x in que:
        x += c[v]
        ans[v] = x
        for w in d[v]:
            if ans[w]==0:
                tmp.append((w,x))
    que = tmp

s = ''
for i in range(1,N):
    s += str(ans[i]) + ' '
s += str(ans[N])
print(s)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]
ans = [0 for _ in range(n)]
for p, x in px:
  ans[p-1] += x
for a, b in ab:
  ans[b-1] += ans[a-1]
print(" ".join(map(str, ans)))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
g=[set() for _ in range(n+1)]

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

for i in range(n,0,-1):
    y=min(g[i])
    g[y]=g[y]|g[i]
    g[y].add(i)

c=[0]*(n+1)

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

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(N-1)]
px=[list(map(int,input().split())) for i in range(Q)]
c=[[] for i in range(N)]
for a,b in ab:
    c[a-1].append(b-1)
    c[b-1].append(a-1)
v=[0]*N
v[0]=1
P=[-1]*N
import sys
sys.setrecursionlimit(10**6)
def dfs(p,v,P):
    for n in c[p]:
        if v[n]==0:
            P[n]=p
            v[n]=1
            dfs(n,v,P)
dfs(0,v,P)
print(P)
X=[0]*N
for p,x in px:
    X[p-1]+=x
print(X)
A=[0]*N
for i in range(N):
    A[i]+=X[i]
    j=i
    while P[j]!=-1:
        j=P[j]
        A[i]+=X[j]
print(*A)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab2=sorted(ab, key=lambda x:x[0])
pq2=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for p,q in pq2:
	res[p-1]+=q
for a,b in ab2:
	res[b-1]+=res[a-1]
ans=[]
for i in range(n):
	ans.append(str(res[i]))
#print(" ".join(ans))

Submission status: Wrong Answer

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

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, Q = LI()
    A, B, P, X = [], [], [], []
    memo = [0 for _ in range(N)]
    ans = [0 for _ in range(N)]
    for _ in range(N-1):
        _a, _b = LI()
        A.append(_a-1)
        B.append(_b-1)
    for _ in range(Q):
        _p, _x = LI()
        memo[_p-1] += _x
        #P.append(_p-1)
        #X.append(_x)
    ans[0] += memo[0]
    for i in range(N-1):
        a_nodenum = A[i]
        b_nodenum = B[i]
        ans[b_nodenum] = ans[a_nodenum] + memo[b_nodenum]
    for i in ans:
        print(i, end=" ")
    print()
main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict
from bisect import bisect_left


class Solution:
    def main(self):
        path = defaultdict(list)
        N, Q = map(int, input().split())
        freq = [0] * N
        for i in range(N-1):
            ai, bi = map(int, input().split())
            path[ai-1].append(bi-1)
            path[bi-1].append(ai-1)

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

        stack = [(0, 0)]
        seen = set()
        res = [0] * N
        while stack:
            node, cum = stack.pop(0)
            seen.add(node)
            val = freq[node] + cum
            res[node] = val
            for other in path[node]:
                if other not in seen:
                    stack.append((other, val))
        print(res)

if __name__ == '__main__':
    Solution().main()

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 + 1)
for i in range(Q):
    score[p[i]] += x[i]

for i in range(2, N+1):
    score[i] +=  score[a[i-2]]

for i in range(len(score)):
    score[i] = str(score[i])

score.pop(0)

ans = ' '.join(score)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,Q = map(int,input().split())
d = defaultdict(list)

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

c = defaultdict(int)

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

ans = defaultdict(int)
que = [(1,0)]
while len(que)>0:
    tmp = []
    for v,x in que:
        x += c[v]
        ans[v] = x
        for w in d[v]:
            if ans[w]==0:
                tmp.append((w,x))
    que = tmp
ans = [str(ans[i]) for i in range(1,N+1)]
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(N-1)]
px=[list(map(int,input().split())) for i in range(Q)]
c=[[] for i in range(N)]
for a,b in ab:
    c[a-1].append(b-1)
    c[b-1].append(a-1)
v=[0]*N
v[0]=1
P=[-1]*N
import sys
sys.setrecursionlimit(10**6)
def dfs(p,v,P):
    for n in c[p]:
        if v[n]==0:
            P[n]=p
            v[n]=1
            dfs(n,v,P)
dfs(0,v,P)
X=[0]*N
for p,x in px:
    X[p-1]+=x
A=[0]*N
for i in range(N):
    A[i]+=X[i]
    j=i
    while j!=-1:
        j=P[j]
        A[i]+=X[j]
print(*A)

Submission status: Wrong Answer

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

for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    if not a in path:
        path[a]= {b}
    else:
        path[a].add(b)
    if not b in path:
        path[b] = {a}
    else:
        path[b].add(a)

# print(path)
visited = set()
ques = {}

for i in range(q):
    p,x = map(int,input().split())
    p-=1
    if p not in ques:
        ques[p] = x
    else:
        ques[p] += x
# print(ques)

dep = set()
dep.add(0)
ans = [0 for i in range(n)]
while True:
    temp = set()
    for key in dep:
        if key in ques:
            aditional = ques[key]
        else:
            aditional = 0
        ns = path[key]
        for p in ns:
            if p not in visited:
                temp.add(p)
                visited.add(p)
                ans[p] = ans[key]+aditional
            else:
                continue
        # ans[key] += aditional
    if not dep:
        break
    dep = temp
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    g = Graph(N)
    for aa, bb in zip(a, b):
        g.add_edge([aa-1, bb-1])

    P = [0]*N
    for pp, xx in zip(p, x):
        P[pp-1] += xx

    visit = deque()
    counter = [0]*N
    visit.append((0, None))
    while len(visit) > 0:
        # print(visit)
        if counter[0] > 1000:
            break
        curr, par = visit.popleft()
        counter[curr] += P[curr]
        for t, w in g.E[curr]:
            if t == par:
                continue
            visit.append((t, curr))
            counter[t] += counter[curr]
    print(*counter)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    x = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p-1]+=x
q = deque([0])
flag = [False]*N
while q:
    v = q.pop()
    flag[v] = True
    for e in G[v]:
        if flag[e]:
            continue
        count[e]+=count[v]
        q.append(e)
print(count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

N, Q = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    es[a].append(b)
cnt = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x
print(111)
def EulerTour(v, p, c):
    for u in es[v]:
        if u != p:
            EulerTour(u, v, c+cnt[v])
    cnt[v] += c
EulerTour(1, 0, 0)
print(*cnt[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        point[u] += point[v]
        dfs(u,v)

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

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

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

dfs(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,q=map(int,input().split())
tree=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a) # 無向グラフなので
ans=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x

stack=deque([[0,-1]]) # 根の位置、現位置の元になる根
visited=[0]*n
visited[0]=1

while stack:
    cur,rot=stack[-1]
    for i in tree[cur]:
        if visited[i]==0 and i!=rot:
            visited[i]=1
            ans[i]+=ans[cur]
            stack.append([i,cur])
            break
    else:
        stack.pop()
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = mapint()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
late = [0]*N

for _ in range(Q):
    v, p = mapint()
    late[v-1] += p

ans = [0]*N
checked = [0]*N

def dfs(v, plus):
    plus += late[v]
    checked[v] = 1
    ans[v] = plus
    for nx in tree[v]:
        if not checked[nx]:
            dfs(nx, plus)

dfs(0, 0)
print(*ans)

Submission status: Time Limit Exceeded

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


class Node:
    def __init__(self, index):
        self.index = index
        self.leaf = {}
        self.score = 0

    def set_parent(self, parent):
        self.leaf.pop(parent)
        for l in self.leaf.values():
            l.set_parent(self.index)

    def add_score(self, score):
        self.score += score
        for l in self.leaf.values():
            l.add_score(score)


N, Q = map(int, input().split())
tree = {i: Node(i) for i in range(1, N + 1)}
tree[1].leaf[1] = tree[1]

for i in range(N-1):
    n1, n2 = map(int, input().split())
    tree[n1].leaf[n2] = tree[n2]
    tree[n2].leaf[n1] = tree[n1]

tree[1].set_parent(1)
for _ in range(Q):
    p, x = map(int, input().split())
    tree[p].add_score(x)
# [tree[p].add_score(x) for p, x in map(int, input().split())]

print(' '.join([str(t.score) for t in tree.values()]))

Submission status: Time Limit Exceeded

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


class Node:
    def __init__(self, index):
        self.index = index
        self.leaf = set()
        self.score = 0

    def set_parent(self, parent):
        self.leaf.remove(parent)
        for l in self.leaf:
            tree[l].set_parent(self.index)

    def add_score(self, score):
        self.score += score
        for l in self.leaf:
            tree[l].add_score(score)


N, Q = map(int, input().split())
tree = {i: Node(i) for i in range(1, N + 1)}
tree[1].leaf.add(1)

for i in range(N-1):
    n1, n2 = map(int, input().split())
    tree[n1].leaf.add(n2)
    tree[n2].leaf.add(n1)

tree[1].set_parent(1)

for _ in range(Q):
    p, x = map(int, input().split())
    tree[p].add_score(x)

print(' '.join([str(t.score) for t in tree.values()]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import sys
def input():
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b
# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue
        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]
        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    ans = A[i]
    v = i
    while v != 0:
        v = P[v]
        ans += A[v]
    print(ans, end=' ')

print()