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

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

edges = [[] for i in range(n)]

d = [0] * n

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

for i in range(q):
    pa,xa = map(int,input().split())
    d[pa-1] += xa

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




def dfs(v):
    q=[v]
    visited = [0] * n
    while q:
        v=q.pop()
        hoga = d[v]
        visited[v] = 1
        for i in edges[v]:
            if not visited[i]:
                d[i] += hoga
                q.append(i)
        
    return d

print(*dfs(0))

Solution (Python):
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce


def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

sys.setrecursionlimit(10000)

mod = 1000000007

"""

a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654


char_list = list("abcd") 



    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())


    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""


class Tree:
    def __init__(self):
        self.child = []
        self.count = 0

if __name__ == "__main__":
    N, Q = map(int, sys.stdin.readline().split())
    node_list = [Tree() for _ in range(N + 1)]

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

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

    ans = []
    for n in node_list[1::]:
        ans.append(n.count)
        for nc in n.child:
            node_list[nc].count += n.count
    print(*ans)

Solution (Python):
N, Q = map(int, input().split())
tree_dic = {}
count = [0] * (N+1) 
for n in range(N):
    tree_dic[n+1] = []
for n in range(N-1):
    a, b = map(int, input().split())
    tree_dic[a].append(b)

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


for key in tree_dic:
    l = tree_dic[key]
    for i in l:
        count[i] += count[key]

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

Solution (Python):
import sys

n, q = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
for line in lines[:n - 1]:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
adds = [0] * n
for line in lines[n - 1:]:
    p, x = map(int, line.split())
    p -= 1
    adds[p] += x
ans = [-1] * n
q = [(0, 0)]
while q:
    v, a = q.pop()
    a += adds[v]
    ans[v] = a
    for u in links[v]:
        if ans[u] == -1:
            q.append((u, a))

print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)

import sys
input = sys.stdin.readline

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

query = [0] * N
ans = [0] * N

for p,x in px:
    query[p-1] = query[p-1] + x
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(b-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    val += query[v]
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
    return 
        
dfs(0,0)
print(*ans)

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

F = [0 for i in range(N)]
T = [[]for i in range(N)]

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

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

ans = [X[i] for i in range(N)]
for i in range(N):
    F[i] = 1
    for j in range(len(T[i])):
        if F[T[i][j]] == 1:
            continue
        ans[T[i][j]] += ans[i]

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

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

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

for i,bs in enumerate(base_score):
    score[i] = bs
    for j in edge[i]:
        base_score[j] += bs

print(*score)

Solution (Python):
N, Q = map(int, input().split())
a = [0] * (N - 1)
b = [0] * (N - 1)
ab = [0] * (N - 1)
for i in range(N-1):
    ab[i] = list(map(int, input().split()))
ab.sort()

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(N-1):
    score[ab[i][1]] += score[ab[i][0]]


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

score.pop(0)

ans = ' '.join(score)

print(ans)

Solution (Python):
import sys


def input():
    return sys.stdin.readline()[:-1]


def main():
    N, Q = map(int, input().split())
    hen = [[int(i)-1 for i in input().split()] for _ in range(N-1)]
    sousa = [[int(i) for i in input().split()] for _ in range(Q)]
    ans = [0]*N
    hen.sort(key=lambda x: x[1])
    hen.sort(key=lambda x: x[0])

    for s in sousa:
        ans[s[0]-1] += s[1]
    for h in hen:
        ans[h[1]] += ans[h[0]]

    
    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import collections

def first_search(graph, root, actions, ans):
    seen, queue = set([root]), collections.deque([[root, 0],])
    while queue:
        vertex, value = queue.pop()  
        ans[vertex] = value + actions[vertex]
        for node in graph[vertex]:
            if node not in seen:
                seen.add(node)
                queue.append([node, ans[vertex]])


def main(): 
    N, Q = LI()
    from collections import defaultdict
    edges = defaultdict(list)
    for _ in range(N-1):
        a, b = LI()
        edges[a].append(b)
        edges[b].append(a)
    actions = defaultdict(int)
    for _ in range(Q):
        p, x = LI()
        actions[p] += x

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

    first_search(edges, 1, actions, ans)

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




main()

Solution (Python):
from collections import defaultdict as de
n,q=map(int,input().split())
s=[[]for i in range(n+1)]
a=de(int)
for i in range(n-1):
    o,b=map(int,input().split())
    s[o].append(b)
    s[b].append(o)
for i in range(q):
    p,x=map(int,input().split())
    a[p]=a[p]+x
t=[0]*(n+1)
g=[[1,0,0]]
while g:
    w=[]
    for i in g:
        t[i[0]]=i[1]+a[i[0]]
        for j in s[i[0]]:
            if j!=i[2]:
                w.append([j,t[i[0]],i[0]])
    else:
        g=w
print(*t[1:])

Solution (Python):
n,q=map(int,input().split())
link=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    link[a-1].append(b-1)

under=[[] for i in range(n)]
for i in range(n-1, -1, -1):
    l=link[i]
    for j in l:
        under[i].append(j)








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

for i in range(n):
    for j in under[i]:
        ans[j]+=ans[i]
for i in ans:
    print("{} ".format(i), end="")
print()

Solution (Python):
from collections import deque

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

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

ans = [0] * (N + 1)
queue = deque()
queue.append(1)
visited = [0] * (N + 1)
visited[1] = 1
ans[1] = point[1]
while queue:
    v = queue.pop()
    for u in adj[v]:
        if visited[u] == 0:
            queue.appendleft(u)
            visited[u] = 1
            ans[u] = ans[v] + point[u]

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

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

edges = [set() for i in range(n)]
for _ in range(n-1):
    a, b= map(int,input().split())
    edges[a-1].add(b-1)
cnt = [0] * n

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

l = [0]
l2 = [cnt[0]]
while len(l) != 0:
    a = l.pop()
    b = l2.pop()
    if a != 0:
        cnt[a] += b
    for i in edges[a]:
        l.append(i)
        l2.append(cnt[a])
print(*cnt)

Solution (Python):
N,Q = map(int,input().split())
Edge = [[] for _ in range(N+1)]

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

PX = [list(map(int,input().split())) for _ in range(Q)]

visited = [True for _ in range(N+1)]
visited[1] = False
stack = [1]
Ans = [0]*(N+1)

for p,x in PX:
    Ans[p] += x

while len(stack) > 0:
    nextnode = stack.pop()
    for e in Edge[nextnode]:
        if visited[e]:
            visited[e] = False
            stack.append(e)
            Ans[e] += Ans[nextnode]
print(*Ans[1:],sep = " ")

Solution (Python):

memo = [-1] * (10**6)
def find(p, tree, query):
    global memo
    if p == 0:
        return 0
    if memo[p] < 0:
        memo[p] = find(tree[p], tree, query) + query[p]
    return memo[p]

def main():
    n, q = map(int, input().split())
    tree = [0]*(n+1)
    tree[1] = 0
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree[b] = a
    query = [0] * (n+1)
    for _ in range(q):
        p, x = map(int, input().split())
        query[p] += x
    print(' '.join([str(find(i+1, tree, query)) for i in range(n)]))

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)


def solve():
    nodedict = {}

    preorder_list = []

    class Node:
        def __init__(self, id):
            self.id = id
            self.childlist = []
            self.p = 0
            self.walked = False

        def __repr__(self):
            return str(self.__dict__)

        def preorder(self, p):
            if self.walked:
                return 0

            self.p = self.p + p

            self.walked = True
            preorder_list.append(self.id)

            for child in self.childlist:
                child.preorder(self.p)

            return 0


    N, Q = LI()

    for i in range(1, N+1):
        nodedict[i] = Node(i)

    for i in range(N-1):
        a, b = LI()
        nodedict[a].childlist.append(nodedict[b])

    for i in range(Q):
        p, x = LI()
        nodedict[p].p += x

    
    nodedict[1].preorder(0)

    dprint(preorder_list)
    print(' '.join([str(nodedict[i].p) for i in range(1, N+1)]))

solve()

Solution (Python):
from collections import deque
n, q = [int(i) for i in input().split()]
g = [[] for i in range(n)]

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

q = deque([[1, c[0]]])
while len(q) != 0:
    p = q.popleft()
    for i in g[p[0]-1]:
        c[i-1] += p[1]
        q.append([i, c[i-1]])

print(*c)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
table = [[] for i in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  table[a].append(b)
task = [0]*N
count = [0]*N
for i in range(Q):
  p,x = map(int,input().split())
  p -= 1
  task[p] += x
H = deque()
H.append(0)
while H:
  y = H.popleft()
  count[y] += task[y]
  for ny in table[y]:
    H.append(ny)
    count[ny] = count[y]
print(" ".join(map(str,count)))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(900000)


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

def dfs(p, s, checked, score):
    
    ns = s + score[p]
    score[p] += s
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            score = dfs(q, ns, checked, score)
    return score


def main():


    score = [0 for _ in range(N)]
    for p, x in PX:
        score[p-1] += x

    checked = [False for _ in range(N)]
    checked[0] = True
    
    ans = dfs(0, 0, checked, score)
    print(' '.join([str(a) for a in ans]))


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, Q = [int(s) for s in input().split()]
    adj = [[] for _ in range(N)]
    counters = [0] * N
    increments = [0] * N

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

    for _ in range(Q):
        p, x = [int(s) for s in input().split()]
        increments[p - 1] += x

    stack = [(0, 0, -1)]

    while stack:
        u, inc, parent = stack.pop()
        inc += increments[u]
        counters[u] += inc

        for v in adj[u]:
            if v != parent:
                stack.append((v, inc, u))

    print(' '.join(str(c) for c in counters))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
	n,q = map(int,input().split())
	rt = [[] for _ in range(n)]
	point = [0 for _ in range(n)]
	used = [False for _ in range(n)]
	ans = [0 for _ in range(n)]
	for _ in range(n-1):
		temp, temp2 = map(int, input().split())
		temp -= 1
		temp2 -= 1
		rt[temp2] = rt[temp2] + [temp]
	for _ in range(q):
		temp, temp2 = map(int,input().split())
		temp -= 1
		point[temp] += temp2
	def u(x):
		for i in rt[x]:
			if not(used[i]):
				ref = u(i)
				ans[x] += ref
			else:
				ans[x] += ans[i]
		ans[x] += point[x]
		used[x] = True
		return ans[x]
	for i in range(n):
		ref = u(i)
		print(str(ans[i]) + ("\n" if i == n-1 else " "), end= "")

main()

Solution (Python):
n, q = map(int,input().split())
nodes = [[[], 0] for _ in range(n)]

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

search_node = [0]

while len(search_node) > 0:
    n = search_node.pop()
    for i in nodes[n][0]:
        nodes[i][1] += nodes[n][1]
        search_node.append(i)


op = str(nodes[0][1])
for n in range(1, len(nodes)):
    op += " {}".format(nodes[n][1])
print(op)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
    
pq = [0 for _ in range(N)]
for _ in range(Q) :
    p, q = map(int, input().split())
    pq[p-1] += q
    
visited = [False] * N
visited[0] = True

ret = [0] * N
def bfs(cur, score) :
    ret[cur] = score + pq[cur]
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            bfs(nex, ret[cur])

bfs(0, 0)
    
print(*ret)

Solution (Python):
import sys
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, q = LI()
    g = defaultdict(list)
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
    c = [0 for i in range(n+1)]
    for i in range(q):
        p, x = LI()
        c[p] += x


    d = deque([1])
    while len(d) > 0:
        root = d.pop()
        chs = g[root]
        for ch in chs:
            c[ch] += c[root]
            d.append(ch)

    c = [str(i) for i in c]
    print(' '.join(c[1:]))


if __name__ == '__main__':
    main()

Solution (Python):









import sys


sys.setrecursionlimit(10000000)








from collections import deque, Counter, OrderedDict,defaultdict
from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace




def dfs(curr,parent):
    visited[curr]=True
    value[curr]+=value[parent]
    for i in mydict[curr]:
        if not visited[i]:
            dfs(i,curr)


def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

n,q=get_ints()
mydict=defaultdict(list)
parent=[0]*(n+1)
for i in range(n-1):
    a,b=get_ints()
    mydict[a].append(b)
    parent[b]=a

value=[0]*(n+1)
while q>0:
    index,score=get_ints()
    value[index]+=score
    q-=1

visited=[False]*(n+1)
dfs(1,0)

print(*value[1:])

Solution (Python):
n,q=[int(i) for i in input().split()]
g={}
val=[0]*n
vis=[0]*n
for i in range(n-1):
  a,b=[int(i) for i in input().split()]
  if a-1 in g:g[a-1].append(b-1)
  else:g[a-1]=[b-1,]
for i in range(q):
  a,b=[int(i) for i in input().split()]
  val[a-1]+=b
stack=[]
stack.append(0)
vis[0]=1
while(len(stack)>0):
  p=stack.pop()
  if p in g:
    for i in g[p]:
      if vis[i]==0 :
        val[i]=val[i]+val[p]
        stack.append(i)
        vis[i]=1
for i in val:print(i,end=" ")
print(" ")

Solution (Python):
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=str(res[0])
for i in range(1,n):
	ans+=" "+(str(res[i]))
print(ans)

Solution (Python):
n, q = [ int(v) for v in input().split() ]
value_list = [ 0 for i in range(n) ]
connect_list = [ [] for i in range(n) ]
for i in range(n-1):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append(b)
    connect_list[b].append(a)
for i in range(q):
    c, p = [ int(v)-1 for v in input().split() ]
    value_list[c] += p + 1


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

search_list= connect_list[0]
serached_list[0] = 1
for i in connect_list[0]:
    value_list[i] += value_list[0] 


while search_list != []:
    new_search_list = []
    for i in search_list:
        serached_list[i] = 1
        for j in connect_list[i]:
            if serached_list[j] == 0:
                value_list[j] += value_list[i] 
                new_search_list.append(j)
    search_list = new_search_list
print(*value_list)

Solution (Python):
N, Q = map(int, input().split())
EDGES = [list(map(int, input().split())) for i in range(N-1)]
OPES = [list(map(int, input().split())) for i in range(Q)]
VALUES = [0 for i in range(N)]

for o in OPES:
    VALUES[o[0]-1] += o[1]

EDGES.sort(key=lambda e:e[0])
for e in EDGES:
    VALUES[e[1]-1] += VALUES[e[0]-1]
print(" ".join(map(str, VALUES)))

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

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

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

result = [None]*N
stack = [(0,0)]
while stack:
    v,a = stack.pop()
    a += memo[v]
    result[v] = a
    for u in adj[v]:
        stack.append((u,a))

print(*result)