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:
n,q=map(int,input().split())


tree={}
result={}

temp=[]
#print(n-1)
for _ in range(n-1):
  temp.append(list(map(int,input().split())))

temp=temp[::-1]
#print(temp)
  
for a,b in temp:
  if a in tree:
    tree[a].append(b)
  else:
    tree[a]=[b]
  if b in tree:
    for k in tree[b]:
      tree[a].append(k)
  else:
    tree[b]=[]
 # print(a,b,tree)


  
for _ in range(q):
  no,value=map(int,input().split())
  if no in result:
    result[no]+=value
  else:
    result[no]=value

  for j in tree[no]:
    if j in result:
      result[j]+=value
    else:
      result[j]=value
    
  
#print(result) 
print(*result.values())

Submission status: Wrong Answer

Solution code:
import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}
for i in range(N) :
    dic[i+1] = []

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

SUM = np.zeros(N, dtype=np.int)

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

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

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

cnt = [0] * n
ver = [[i+1] for i in range(n)]
adder = {}

for i in range(n-2, -1, -1):
    ver[ab[i][0]-1] += ver[ab[i][1]-1]

for i in range(q):
    adder.setdefault(px[i][0], 0)
    adder[px[i][0]] += px[i][1]

for i in adder:
    for j in ver[i-1]:
        cnt[j-1] += adder[i]
        
print(" ".join(map(str, cnt)))

Submission status: Wrong Answer

Solution code:
import numpy as np
NQ=list(map(int, input().split()))
N,Q=NQ[0],NQ[1]
ab=[]#np.zeros(N-1)
px=[]#np.zeros(Q)
count=np.zeros(N)
for i in range(N-1):
    ab.append(list(map(int, input().split())))
for i in range(Q):
    px.append(list(map(int, input().split())))

for i in range(Q):
    temp=[]
    count[px[i][0]-1] +=px[i][1]
    for j in range(N-1):
        if ab[j][0] == px[i][0] or ab[j][0] in temp:
            #count[ab[j][1]-1] +=px[i][1]
            temp.append(ab[j][1])
    for j in range(len(temp)):
        count[temp[j]-1] +=px[i][1]

print(count)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
dic = {}
amari = {}
for i in range(N-1):
  k, v = map(int, input().split())
  if dic.get(k) is None:
    dic[k] = [v]
  else:
    dic[k].append(v)
  if amari.get(k):
    amari.pop(k)
  amari[v] = []
dic.update(amari)
counter = [list(map(int, input().split())) for i in range(Q)]
q = {i: 0 for i in dic.keys()}
 
def child_sum(q,v, child):
  if child == []:
    return q
  else:
    for j in child:
      q[j] += v
      child = dic[j]
      q = child_sum(q, v, child)
  return q
    
for i, v in counter:
  q[i] += v
  child = dic[i]
  #print(q, i, child)
  q = child_sum(q, v, child)
print(*q.values())

Submission status: Wrong Answer

Solution code:
import numpy as np

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

tree_np = np.array(tree)

for i, _ in enumerate(tree):
    for node, _ in enumerate(tree[i]):
        if tree[i][node] == 1:
            tree[i] = np.array(tree[i]) + np.array(tree[node])

print(tree)

ans = np.array([0] * N)
for q in range(Q):
    p, x = map(int, input().split())
    ans += np.array(np.array(tree[p-1]) * x)
    
print(ans)

# 無理だった。グラフ理論とか分からんす。記念提出

Submission status: Wrong Answer

Solution code:
import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}
for i in range(N) :
    dic[i+1] = []

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

SUM = np.zeros(N, dtype=np.int)

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

#for i in range(N-1) :
print(' '.join(map(str, SUM)))

Submission status: Wrong Answer

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


# 親に付いている重み
r = [0,] * (N+1)
for p, x in W:
    r[p] += x



# 木の隣接関係 (a<bは保証されている)
M = [[] for _ in range(N+1)]
for g in G:
    M[g[0]].append(g[1])

# print(M)

# 木の親子関係
P = [[] for _ in range(N+1)]
# dfs
visited = []

def dfs(start):
    Stack = [start,]
    while Stack:
        now = Stack.pop(0)
        visited[now] = 1
        for child in M[now]:
            if not visited[child]:
                r[child] += r[parent]
                Stack.append(child)

for parent in range(1, N+1):
    visited = [0,] * (N+1)
    dfs(parent)
    P[parent].extend([i for i, s in enumerate(visited) if s])

# print(P)

#res = [0,] * (N+1)
# for p, x in W:
#     for pp in P[p]:
#         res[pp] += x




print(*r[1:])

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
nres = [0] * n
ab={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in ab:
        ab[a].append(b)
        ab[b] = [-1]
    else:
        ab[a] = [b]
        ab[b] = []

def tr(tree, res, p, q):
    if p in tree:
        res[p-1] += q
        for i in tree[p]:
            tr(tree, res, i, q)

for i in range(q):
    p,q=map(int,input().split())
    tr(ab, nres, p, q)

print(' '.join(list(str(x) for x in nres)))

Submission status: Wrong Answer

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)
        # カウンター用
        self.tree = [[] for x in range(n + 1)]

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if (x == y):
            return
            # 違う木に属していた場合rnkを見てくっつける方を決める
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
        # カウンター用
        self.tree[y].append(x)
        self.tree[y] += self.tree[x]

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


n, q = map(int, input().split())
ab_array = [[int(x) for x in input().split()] for y in range(n - 1)]
px_array = [[int(x) for x in input().split()] for y in range(q)]

uf = UnionFind(n)
for a, b in ab_array:
    uf.Unite(a, b)
counter = [0 for x in range(n + 1)]
for p, x in px_array:
    counter[p] += x

for i in range(1, n + 1):
    ans = counter[i]
    ans += sum(counter[x] for x in uf.tree[i])
    print(ans, end=" ")
print("")

Submission status: Wrong Answer

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

def make_child(parent):
    child_list = []
    search_deque = [parent]
    if parent in graph:
        search_deque += graph[parent]
    while search_deque:
        p = search_deque.pop(0)
        if not p in child_list:
            child_list.append(p)
            if p in graph:
                search_deque += graph[p]
    return child_list

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

for i in range(q):
    p, x = map(int, input().split())
    if p in graph:
        children = make_child(p)
        for c in children:
            if c in counter:
                counter[c] += x
            else:
                counter[c] = x
    else:
        if p in counter:
            counter[p] += x
        else:
            counter[p] = x
sorted_counter = sorted(counter.items(), key=lambda x:x[0])
for s in sorted_counter:
    print(s[1], end=" ")

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(lambda:'0')
que = [(1,0)]
while len(que)>0:
    tmp = []
    for v,x in que:
        x += c[v]
        ans[v] = str(x)
        for w in d[v]:
            if ans[w]=='0':
                tmp.append((w,x))
    que = tmp

for i in range(1,N+1):
    if i<N:
        print(str(ans[i])+' ',end="")
    else:
        print(str(ans[i]))

Submission status: Wrong Answer

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

lst = [[]]*(n+1) #lst[0]は空位
i = 1
while i <= n-1:
  ai, bi = map(int, input().split())
  lst[ai].insert(0, bi)
  for l in lst:
    if str(ai) in [str(n) for n in l]:
      l.insert(0, bi)
  i += 1

vals = [0]*(n+1)
j = 1
while j <= q:
  pj, xj = map(int, input().split())
  vals[pj] += xj
  for child in lst[pj]:
    vals[child] += xj
  j += 1

vals.pop(0)
s = str(vals.pop(0))
while vals:
  s = s + " " + str(vals.pop(0))

print(vals)

Submission status: Wrong Answer

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

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

#print(edges)

task = [[] for _ in range(N+1)]
for i in range(Q):
    p, x = map(int, input().split())
    task[p].append(x)

#rint(task)

task_sum = [[] for _ in range(N+1)]
for i in range(N+1):
    task_sum[i].append(sum(task[i]))

#print('task_sum:', task_sum)

cnt = [[] for i in range(N+1)]

#print(cnt)

#最初はdfs(1, -1, task_sum[1])

def dfs(v, p, cost):
        
    for nv in edges[v]:
        if nv == p:
            continue
        
        dfs(nv, v, cost+task_sum[nv])

    cnt[v].append(cost)

dfs(1, -1, task_sum[1])

#print(cnt)
for i in range(1, N):
    print(int(sum(cnt[i][0])), end=' ')

Submission status: Wrong Answer

Solution code:

NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])
candidate_list = []
tree_dict = {}
#Make tree dict
for i in range(N-1):
    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])
    tree_dict[i+1] = {
                'count': 0,
                'has_trees': []
            }
    candidate_list.append((a,b))
tree_dict[N] = {
    'count': 0,
    'has_trees': []
    }
candidate_list.reverse()
 
for candidate in candidate_list:
    a = candidate[0]
    b = candidate[1]
    tree_dict[a]['has_trees'] += tree_dict[b]['has_trees'] + [b]
        
out_put_list = [0] * N
for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    out_put_list[p-1] += x
    for idx in tree_dict[p]['has_trees']:
        out_put_list[idx-1] += x
    
print(' '.join(map(str,out_put_list)))

Submission status: Wrong Answer

Solution code:

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

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

a =sorted(a, key=lambda x: x[0])
p =sorted(p, key=lambda x: x[0])

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

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

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

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from collections import defaultdict
import sys
sys.setrecursionlimit(200000)


N, Q = list(map(int,input().rstrip().split(' ')))
sum = [0]*N
connected = list()

for _ in range(N-1):
    connected.append(list(map(int,input().rstrip().split(' '))))

direct_sub_node = defaultdict(list)
for node in range(2, N + 1):
    for c in connected:
        if c[0] == node:
            direct_sub_node[node].append(c[1])

@lru_cache(maxsize=200000)
def subtree(node):
    if node == 1:
        return list(range(1, N + 1))
    else:
        sub_tree_list = direct_sub_node[node]
        if sub_tree_list == []:
            return [node]
        else:
            return [node] + [subtree(sub) for sub in sub_tree_list][0]

for _ in range(Q):
    p, x = list(map(int,input().rstrip().split(' ')))
    sub = subtree(p)
    for y in sub:
        sum[y-1] += x

for r in sum:
    print(r, end=' ')

Submission status: Wrong Answer

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

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



# 2*10**5
# nodes = [Node(i) for i in range(1, n + 1)]

# 2*10**5
edges = defaultdict(list)
for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)


def memoize(f):
    memo = {}

    def memoized(*args):
        if args not in memo.keys():
            memo[args] = f(*args)
        return memo[args]
    return memoized


@memoize
def selectNode(p):
    selected = [p]
    ls = edges[p]
    selected += ls

    while True:
        if ls == []:
            break
        for x in ls:
            ls = edges[x]
            selected += ls
    return selected


dd = defaultdict(int)

# 2*10**5
for _ in range(q):
    p, x = map(int, input().split())
    for idx in selectNode(p):
        dd[idx] += x

print(*(dd[i+1] for i in range(n)))

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**6)
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


point_root = [0] * N
query = [None]
for i in range(Q):
    p,x = map(int, input().split())
    point_root[p-1] += x 
point_root = tuple(point_root)
ans = [0] * N
visited = [False] * N
global vis
vis = 0

def solve(node, point):
    
    ans[node] += point
    visited[node] = True


    if es.get(node, None) != None:
        for i in es[node]:
            if visited[i] == False:
                solve(i, point+point_root[i])
solve(0, point_root[0])

Submission status: Wrong Answer

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

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

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

a =sorted(a, key=lambda x: x[0])
p =sorted(p, key=lambda x: x[0])

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

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

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

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
N,Q = map(int,input().split())
route = [[] for _ in range(N)]
ans = [0] * N
for i in range(N - 1):
    a,b = map(int,input().split())
    route[a - 1].append(b)
    route[b - 1].append(a)
for i in range(Q):
    p,x = map(int,input().split())
    ans[p - 1] = x
W = [(0,1)]
A = [1] * N
while W:
    de,nod = heappop(W)
    A[nod - 1] = 0
    for i in route[nod - 1]:
        if A[i - 1] == 1:
            heappush(W,(de + 1,i))
            ans[i - 1] += ans[nod - 1]
for j in ans:
    print(j)

Submission status: Wrong Answer

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

n,q = map(int, input().split())
child = defaultdict(list)
parent = defaultdict(int)
query = defaultdict(int)
for _ in range(n - 1):
	a, b = map(int, input().split())
	child[a].append(b)
	parent[b] = a
for _ in range(q):
	a, b = map(int, input().split())
	query[a] += b
ans = []
for i in range(1, n + 1):
	ans.append(query[i])
	if child[i] != []:
 		for x in child[i]:
 			query[x] += query[i]
print(ans)

Submission status: Wrong Answer

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

l=[]
x=0

for _ in range(n-1):
  l1=list(map(int,input().split()))
  l.append(l1)

l2=[0]*n  
for _ in range(q):
  a,b=map(int,input().split())
  l2[a-1]+=b

for i in l:
  a,b=i
  l2[b-1]+=l2[a-1]

for i in l2:
  print(i,end=' ')

Submission status: Wrong Answer

Solution code:

# Setup
import sys
import collections
sys.setrecursionlimit(4100000)

n,q = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(n-1)]
p = [[int(i) for i in input().split()] for _ in range(q)]

childs = collections.defaultdict(list)

for A,B in a:
    childs[A].append(B)

counter = collections.defaultdict(int)
affections = collections.defaultdict(list)

for A,B in p:
    counter[A] += B
    if affections.get(A):
        continue
    current = A
    aff = []
    tosee = [current]
    while len(tosee) != 0:
        temp = tosee.pop()
        aff.append(temp)
        for z in childs[temp]:
            if affections.get(z):
                aff += affections[z]
            else:
                tosee.append(z)
    affections[A] = aff

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self):
        self.parent = None
        self.children = []

def update(ans, idx, edges, point):
    ans[idx-1] += point
    queue = []
    queue.extend(edges[idx].children)
    while queue:
        child = queue.pop()
        ans[child-1] += point
        queue.extend(edges[child].children)


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

edges = {}
points = []
ans = [0] * n

for _ in range(n-1):
    a, b = tuple(map(int, input().split()))
    edges.setdefault(a, Node()).children.append(b)
    edges.setdefault(b, Node()).children.append(a)

for _ in range(q-1):
    points.append(tuple(map(int, input().split())))

parent = 1
queue = [(parent, child) for child in edges[1].children]

# update parent
while queue:
    parent, child = queue.pop()
    edges[child].parent = parent
    edges[child].children.remove(parent)
    queue.extend([(child, grand_child) for grand_child in edges[child].children])


for p, x in points:
    update(ans, p, edges, x)

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

Submission status: Wrong Answer

Solution code:
n = list(map(int, input().split(' ')))
N = n[0]
Q = n[1]
a=[]
b=[]
for i in range(N-1):
    ab = list(map(int, input().split(' ')))
    a.append(ab[0])
    b.append(ab[1])
p = []
x = []
for i in range(Q):
    px = list(map(int, input().split(' ')))
    p.append(px[0])
    x.append(px[1])

counter = [0] * N #葉に加算される値を格納
weed = [[0 for i in range(N)] for j in range(N)] # 葉の値を格納表
weedS = [[0 for i in range(N)] for j in range(N)] # 葉の値を格納
for i in range(0,N):
    weed[i][i]=i+1
# 葉同士のひも付きを先に計算する
#print(weed)
for i in range(N-1):
    #print(a[i])
    #print(b[i])
    weed[a[i]-1][b[i]-1] = b[i]
print(weed)
for i in range(N-1):
    for j in range(N-1):
        if weed[i][j] != 0:
            weed[i] = [x+y for (x,y) in zip(weed[i],weed[j])]
print(weedS)
# カウンターを計算する
for q in range(Q):
    for i in range(N):
        # print("p[q]"+str(p[q]))
        if weed[p[q]-1][i] > 0:
            counter[i] += x[q]
for c in counter:
    print(str(c), end=" ")
print()

Submission status: Wrong Answer

Solution code:
line = input().split()
N = int(line[0])
Q = int(line[1])
g = {}
for i in range(N-1):
    r = input().split()
    a = int(r[0])
    b = int(r[1])
    if not a in g:
        g[a] = []
    g[a].append(b)
    g[b] = []

suma = [0 for i in range(N)]

for i in range(Q):
    row = input().split()
    p = int(row[0])
    x = int(row[1])
    suma[p-1] += x

idx = 0
def add(parent):
    global suma
    if parent in g:
        chi = g[parent]
        for c in chi:
            suma[c-1] += suma[parent-1] 
            add(c)
add(1)
for i in range(0,N-1):
    print(suma[i], end=' ')
print(suma[N-1])

Submission status: Wrong Answer

Solution code:
N, Q = list(map(int, input().split()))
a = [0] * (N-1)
b = [0] * (N-1)
p = [0] * (Q)
x = [0] * (Q)

for i in range(N-1):
    a[i], b[i] = list(map(int, input().split()))
for i in range(Q):
    p[i], x[i] = list(map(int, input().split()))
    
trees = {i: [] for i in range(1, N + 1)}
counter = {i: 0 for i in range(1, N + 1)}

for i in range(N-1):
    trees[a[i]].append(b[i])
        
for i in range(Q):
    counter[p[i]] += x[i]
    for num in trees[p[i]]:
        counter[num] += x[i]
        for val in trees[num]:
            counter[val] += x[i]

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

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
lis1 = []
for i in range(n-1):
    tup1 = tuple(map(int, input().split()))
    lis1.append(tup1)
lis2 = []
for i in range(q):
    tup2 = tuple(map(int, input().split()))
    lis2.append(tup2)

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

for i in range(q):
    numPlus = lis2[i][0]
    plusValue = lis2[i][1]
    lisPlus = [numPlus-1]
    for j in range(numPlus+1, n+1):
        if (numPlus, j) in lis1:
            lisPlus.append(j-1)
        for l in range(j+1,n+1):
            if (j, l) in lis1:
                lisPlus.append(l-1)
            for m in range(l+1,n+1):
                if (l, m) in lis1:
                    lisPlus.append(m-1)
                for y in range(m+1,n+1):
                    if (m, y) in lis1:
                        lisPlus.append(y-1)
    for k in lisPlus:
        lis[k] += plusValue

print(lis)

Submission status: Wrong Answer

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

N, Q = map(int, input().split())
link = [[] for _ in range(N)]
a = [0] * (N-1)
b = [0] * (N-1)
for i in range(N-1):
    a[i], b[i] = map(int, input().split())

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

for i in range(N-1):
    link[a[i]-1].append([b[i]-1, cost[i]])

print(cost[0], end=' ')
def dfs(v, c):
    for nv in link[v]:
        #nums[nv[0]] += c + cost[nv[0]]
        print(c + cost[nv[0]], end=' ')
        dfs(nv[0], c + cost[nv[0]])

    return

dfs(0, cost[0])
print()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

tree = defaultdict(list)
parent = [None] * N
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a] += [b]

subs =[[] for _ in range(N + 1)]
for i in reversed(range(1, N + 1)):
    subs[i] += [i]
    for j in tree[i]:
        subs[i] += [j]
        subs[i] += tree[j]

values = [0] * (N + 1)
for i in range(Q):
    p, q = map(int, input().split())
    for j in subs[p]:
        values[j] += q

values = map(str, values[1:])
print(" ".join(values))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

plus_dic = defaultdict(int)
AB_lst = [list(map(int, input().split())) for _ in range(N - 1)]
PX_lst = [list(map(int, input().split())) for _ in range(Q)]

for p, x in PX_lst:
    plus_dic[p] += x


out_lst = [0] * (N + 1)
out_lst[1] = plus_dic[1]

for a, b in AB_lst:
    out_lst[b] = plus_dic[b] + out_lst[a]

print(*out_lst[1:])

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
tree = list()
ope = list()
cnt = [0] * N
for i in range(N-1):
    tree.append(list(map(int, input().split())))
for i in range(Q):
    ope.append(list(map(int, input().split())))

#print(tree, ope)

for i in range(Q):
    vertex = ope[i][0]
    add = ope[i][1]
    parent = list()
    parent.append(vertex)
    for j in range(N-1):
        #print(j, tree[j][0], parent)
        if tree[j][0] in parent:
            parent.append(tree[j][1])
        if tree[j][1] in parent:
            cnt[j+1] += add
    if vertex == 1:
        cnt[0] += add
#print(tree)
print(cnt)

Submission status: Wrong Answer

Solution code:
while True:
    try:
        N, Q = map(int, input().split())
        verts = [None] * N
        results = [0] * N
        for i in range(N - 1):
            a, b = map(int, input().split())
            if a == 1:
                continue
            a -= 1
            if verts[a] is None:
                verts[a] = list()
            verts[a].append(b)
        for i in range(Q):
            q, x = map(int, input().split())
            q-= 1
            results[q] += x
            if q == 0:
                for i in range(1, N):
                    results[i] += x
            elif verts[q] is not None:
                for i in verts[q]:
                    results[i-1] += x
        print(" ".join(map(str, results)))
    except EOFError:
        break

Submission status: Wrong Answer

Solution code:
N, Q = list(map(int, input().split()))
a = [0] * (N-1)
b = [0] * (N-1)
p = [0] * (Q)
x = [0] * (Q)

for i in range(N-1):
    a[i], b[i] = list(map(int, input().split()))
for i in range(Q):
    p[i], x[i] = list(map(int, input().split()))
    
trees = {i: [] for i in range(1, N + 1)}
counter = {i: 0 for i in range(1, N + 1)}

for i in range(N-1):
    trees[a[i]].append(b[i])
        
for i in range(Q):
    counter[p[i]] += x[i]
    if p[i] in trees.keys():
        for num in trees[p[i]]:
            counter[num] += x[i]
            if num in trees.keys():
                for val in trees[num]:
                    counter[val] += x[i]

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

import sys
sys.setrecursionlimit(100000)

# N <= 2*10^5
# Q <= 2*10^5
N, Q = [int(x) for x in stdin.readline().rstrip().split()]
ab = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]
px = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]

ans = [0] * (N+1)
child = [[] for _ in range(N+1)]

for a, b in reversed(ab):
    child[a].append(b)
    if child[b]:
        child[a] += child[b]

for p, x in px:
    ans[p] += x
    for i in child[p]:
        ans[i] += x

print(*ans[1:], sep=" ")

Submission status: Wrong Answer

Solution code:
import queue

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

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

ans = [0]*N
q = queue.LifoQueue()
q.put(1)
while q.empty() != True:
    d = q.get()
    tmp_b = []
    for a,b in zip(A,B):
        if d == a:
            tmp_b.append(b)
            q.put(b)

    for p,x in zip(P,X):
        if d == p:
            # print("{},{}".format(d,x))
            ans[p-1] += x
    for b in tmp_b:    
        ans[b-1] += ans[p-1]
text = ""

for t in ans:
    text += "{} ".format(t)

print(text[:-1])

Submission status: Wrong Answer

Solution code:
line = input().split()
N = int(line[0])
Q = int(line[1])
g = {}
for i in range(N-1):
    r = input().split()
    a = int(r[0])
    b = int(r[1])
    if not a in g:
        g[a] = []
    g[a].append(b)
    g[b] = []

suma = [0 for i in range(N)]

for i in range(Q):
    row = input().split()
    p = int(row[0])
    x = int(row[1])
    suma[p-1] += x

idx = 0
def add(parent):
    if parent in g:
        chi = g[parent]
        for c in chi:
            suma[c-1] += suma[parent-1] 
            add(c)
add(1)
for i in range(0,N-1):
    print(suma[i], end=' ')
print(suma[N-1])

Submission status: Wrong Answer

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

from collections import defaultdict, Counter
from queue import deque

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

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

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

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

increment_count = Counter()

for i in range(Q):
    c, d = map(int, input().split())
    increment_count[c] += d

for key, val in increment_count.items():
    increment(key, count, adj_list, val, set([]))

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

Submission status: Wrong Answer

Solution code:
print('100 110 111 110')