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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import queue

def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    # initialize count
    count = [0] * N
    for j in range(Q):
        count[p[j]-1] += x[j]
    # initialize tree vertice adjacency list
    adj_list = [ [] for i in range(N) ]
    for i in range(N-1):
        u, v = a[i] - 1, b[i] - 1
        adj_list[u] += [v]
        adj_list[v] += [u]
    # BFS from root, which is 0-th node
    explored = [False] * N
    myqueue = queue.Queue()
    explored[0] = True
    myqueue.put(0)
    while(not myqueue.empty()):
        u = myqueue.get()
        for v in adj_list[u]:
            if explored[v] == False:
                myqueue.put(v)
                explored[v] = True
                count[v] += count[u]
    print(' '.join([str(i) for i in count]))
    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: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10000000)

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

tree = [[] for _ in range(N+1)]
for a, b in ab:
  tree[a] += [b]
  #tree[b] += [a]

def isList(item):
  if not item:
    return False
  return isinstance(item, list)

from collections import deque

d = deque()
def f(arr, n):
  global d
  if not arr:
    return
  for pp in arr if type(arr) == list else arr.popleft():
    if isList(tree[pp]):
      d.append(tree[pp])
      counter[pp] += n
    else:
      counter[pp] += n
  if d:
    return f(d, n)

counter = [0] * (N+1)
for p, x in px:
  f(tree[p], x)
  counter[p] += x
print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
box=[list(map(int,input().split())) for i in range(n-1)]
point=[list(map(int,input().split())) for i in range(q)]
tree={i+1:[] for i in range(n)}
answer=[0]*n
for x,y in box:
    tree[x] +=[y]
for x,y in point:
    answer[x-1] +=y
for x,y in tree.items():
    for i in y:
        answer[i-1]=answer[x-1]+answer[i-1]

print(*answer)

Submission status: Time Limit Exceeded

Solution code:
x,y = map(int,input().split())
set_list=[list(map(int,input().split())) for i in range(x-1)]
point_li=[list(map(int,input().split())) for i in range(y)]
ans_li=[0 for i in range(x)]

def setPoint(n, point):
    rlist=[]
    for tt in range(x-1):
        if set_list[tt][0]==n:
            ans_li[set_list[tt][1]-1]+=point
            rlist.append(set_list[tt][1])
    return rlist
for i in range(y):
    point=point_li[i][1]
    start=point_li[i][0]
    r=setPoint(start,point)
    if len(r)>0:
        for kk in range(len(r)):
            setPoint(r[kk],point)
    ans_li[start-1]+=point
[print(ans_li[i] , end =" ") for i in range(x)]

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
import copy
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 

ans = [0] * N
for i in range(N):
    ans[i] += point_root[i]
    if es.get(i, None) != None:
        next_nodes = copy.deepcopy(es[i]) # これからポイントを足し行くやつら
    else:
        continue
    
    visited = [False] * N
    visited[i] = True
    idx_n = 0
    while idx_n <= len(next_nodes)-1:
        #idx_n = 0
        if idx_n <= len(next_nodes)-1:
            if visited[next_nodes[idx_n]] == False:
                ans[next_nodes[idx_n]] += point_root[i]
                visited[next_nodes[idx_n]] = True
            #print("--",es,next_nodes)
                #print(es[next_nodes[0]])
                #print("ne",next_nodes)
                idx = next_nodes[idx_n]
                #print("aaa",idx, es)
                tmp = es.get(idx, None)
                if tmp != None:
                    next_nodes.extend(tmp)
                    idx_n += 1
                #next_nodes = next_nodes[1:]
            else:
                idx_n += 1
        else:
            break

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = {}
for i in range(n-1):
    ai, bi = map(int,input().split())
    if ai-1 in d:
        d[ai-1] += [bi-1]
    else:
        d[ai-1] = [bi-1]
    if bi-1 in d:
        d[bi-1] += [ai-1]
    else:
        d[bi-1] = [ai-1]
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] +=xi
sp = [0 for i in range(n)]

def f(v,vp,p):
    su = p + px[v]
    sp[v] = su
    if v in d:
        for di in d[v]:
            if not di == vp:
                f(di,v,su)
f(0,0,0)
for i in range(n):
    print(sp[i])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200000000)

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

l = [[] for i in range(n+1)]
for pi in ab:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])

def dfs(graph, start, oya):
    if start != 1:
        graph[start].remove(oya)
    if len(graph[start]) == 0:
        return
    else:
        for i in graph[start]:
            dfs(graph, i, start)

dfs(l, 1, 1)

def dfs_2(graph, start, ans, x):
    ans[start] += x
    if len(graph[start]) == 0:
        return
    else:
        for i in graph[start]:
            dfs_2(graph, i, ans, x)

ans = [0 for i in range(n+1)]
for p, x in px:
    dfs_2(l, p, ans, x)
        
for i in range(1, n+1):
    print(ans[i], end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]
#print(ab)
#print(px)
ans= [[0 for i in range(n)] for i in range(n)]
ans2= [0 for i in range(n)]
for i in range(n):
    ans[i][i] = 1
for i in range(len(ab)):
    ans[ab[i][0]-1][ab[i][1]-1]+=1
for i in range(n):
    for j in range(i+1,n):
        if(ans[i][j]>0):
            for k in range(j,n):
                ans[i][k]+=ans[j][k]
for i in range(q):
    for j in range(n):
        ans2[j]+=px[i][1]* 1 if ans[px[i][0]-1][j] else 0
print(" ".join(list(map(str,ans2))))

Submission status: Time Limit Exceeded

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

def r(e, chain):
    while True:
        try:
            ee = e.pop()
            E[ee].remove(chain[-1])
        except IndexError:
            break
        for c in chain:
            E2[c].append(ee)
        r(E[ee], chain+[ee]) 

r(E[0], [0])

for i, x in enumerate(P):
    for e2 in E2[i]:
        result[e2] += x

print(*result)

Submission status: Time Limit Exceeded

Solution code:

first = [int(i) for i in input().split()]
N = first[0]
Q = first[1]


graph = {}

for i in range(1, N):
    n = [int(j) for j in input().split()]
    if n[0] in graph:
        graph[n[0]]['next'].append(n[1])
        if n[1] not in graph:
            graph[n[1]] = {
                'next':  [],
                'val': 0,
            }

    else:
        graph[n[0]] = {
            'next':  [n[1]],
            'val': 0,
        }
        graph[n[1]] = {
            'next':  [],
            'val': 0,
        }


def add(graph, key, val):
    graph[key]['val'] += val
    for i in graph[key]['next']:
        graph = add(graph, i, val)
    return graph


for i in range(1, Q+1):
    n = [int(j) for j in input().split()]
    graph = add(graph, n[0], n[1])

for v in graph.values():
    print(v['val'], end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
a = []
b = []
for i in range(N-1):
    a.append(list(map(int, input().split())))
for i in range(Q):
    b.append(list(map(int, input().split())))
class Tree():
    def __init__(self):
        self.leaf = []
        self.num = 0

def plus(treenum, num):
    tree[treenum].num += num
    #print(treenum, num)
    for i in range(len(tree[treenum].leaf)):
        plus(tree[treenum].leaf[i] ,num)


tree = []
for i in range(N):
    tree.append(Tree())

for i in range(N - 1):
    tree[a[i][0] - 1].leaf.append(a[i][1] - 1)

for i in range(Q):
    plus(b[i][0] -1, b[i][1])
for i in range(N):
    print(tree[i].num, end = " ")

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
edges = sorted([list(map(int,input().split())) for _ in range(N-1)])
cnts = [list(map(int,input().split())) for _ in range(Q)]
values = [0]*N
trees = [[i+1] for i in range(N)]

for a,b in edges:
  for tree in trees:
    if a in tree:
      tree.append(b)

for j,cnt in cnts:
  for node in trees[j-1]:
    values[node-1] += cnt

for value in values:
  print(value, end =" ")

Submission status: Time Limit Exceeded

Solution code:
def bfs(graph, start, weight, ):
	queue = [start]
	while queue:
		label = queue.pop(0)
		cnt[label-1] += weight
		queue += graph.get(label,[])

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

cnt = [0 for i in range(n)]
dic = {}
for i in range(n-1):
	if a[i][0] not in set(dic.keys()):
		dic[a[i][0]] = [a[i][1]]
	else:
		dic[a[i][0]].append(a[i][1])

for i in range(q):
	bfs(dic, b[i][0], b[i][1])
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

G = Graph()

N, Q = getlist()
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a, b)
	G.add_edge(b, a)

plus = [0 for i in range(N + 1)]
for i in range(Q):
	p, x = getlist()
	plus[p] += x


q = deque([]) 
ans = [0 for i in range(N)]
visit = [-1 for i in range(N + 1)]
visit[1] = 1
q.append(1)
while q:
	m = q.pop()
	visit[m] = 1
	ans[m - 1] += plus[m]
	x = ans[m - 1]
	for i in G.graph[m]:
		if visit[i] == -1:
			q.append(i)
			ans[i - 1] += x

print(" ".join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N,Q=map(int,input().split())
l=[ tuple( map(int,input().split()) ) for i in range(N-1) ]
p=[ tuple( map(int,input().split()) ) for i in range(Q) ]
d=defaultdict(list)
for vert,childs in l:
    d[vert].append(childs)

for i in range(N,0,-1):
    for j in d[i]:
        if j in d.keys():
            for x in d[j]:
                d[i].append(x)

d_2=defaultdict(int)
for i in range(1,N+1):
    d_2[i]=0

for p,x in p:
    d_2[p]+=x
    for o in d[p]:
        d_2[o]+=x

ans=d_2.values()
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
par=[-1 for i in range(n+1)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す
p=[-1 for i in range(n+1)]
p[1]=0
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    x,y=a,b
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
        x,y=y,x
    par[a]+=par[b]
    par[b]=a
    p[b]=x
    
    return True
ll=[]
for i in range(n-1):
    a=[int(j) for j in input().split()]
    ll.append(a)
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

l=[0 for i in range(n+1)]
for i in range(q):
    r=[int(j) for j in input().split()]
    l[r[0]]+=r[1]
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

inputs=[]
for i in range(n+1):
    inputs.append((p[i],i,l[i]))
g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

d = Dijkstra(g, 0)
ans=[]
for i in range(1,n+1):
    ans.append(d.shortest_distance(i))

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
np = input().split()
N = int(np[0])
Q = int(np[1])


class Node:

    def __init__(self, number_id):
        self.number_id = number_id  # int
        self.connection_list = []  # つながりのあるidのリスト
        self.parent_id = None
        self.children_list = []
        self.add_number = 0

    def add_add_number(self, add_n):
        self.add_number += add_n

    def add_connection(self, connect_id):
        self.connection_list.append(connect_id)

    def set_tree(self, parent_id, add_n):
        self.parent_id = parent_id
        self.add_number += add_n
        for child_d in self.connection_list:
            if child_d != parent_id:
                self.children_list.append(child_d)
        return self.children_list


# 読み込んでグラフを作成
# ノード間のつながりができてから，親と子を決定する
node_list = [Node(i+1) for i in range(N)]
for _ in range(N-1):
    ab = input().split()
    a = int(ab[0])
    b = int(ab[1])
    a_node = node_list[a-1]
    b_node = node_list[b-1]
    a_node.add_connection(b)
    b_node.add_connection(a)

# ノードごとに足される数を保存する
for _ in range(Q):
    px = input().split()
    p = int(px[0])
    x = int(px[1])
    p_node = node_list[p-1]
    p_node.add_add_number(x)
# のーど1からノードにあるadd numberを足していく
# node 1 から親子関係を決定する
node_one = node_list[0]
children_dictionary = {}  # key:parent id, value: children list
key_list = [1]
child_l = node_one.set_tree(0, 0)
children_dictionary[1] = child_l
while len(children_dictionary) != 0:
    # key = sorted(children_dictionary.keys())[0]
    key = key_list.pop(0)
    parent_add_n = node_list[key-1].add_number
    children_l = children_dictionary.pop(key)
    for child in children_l:
        new_children = node_list[child-1].set_tree(key, parent_add_n)
        children_dictionary[child] = new_children
        key_list.append(child)

# 出力
for node in node_list:
    print(node.add_number, end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue


class Graph:

  def __init__(self, N):
    self.V = {}
    self.E = {}

    for i in range(N):
      self.V[i + 1] = 0
      self.E[i + 1] = {}

  def add_edge(self, u, v, w):
    self.E[u][v] = w


def calc(N, G):
  result = [0] * N
  Q = Queue()

  Q.put((1, 0))

  while not Q.empty():
    u, value = Q.get()
    value += G.V[u]
    result[u - 1] = value
    for v in G.E[u]: Q.put((v, value))

  return result


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

G = Graph(N)

for _ in range(N - 1):
  a, b = map(int, input().strip().split())
  G.add_edge(a, b, 0)

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

result = calc(N, G)

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

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(_) for _ in input().split())  
arr = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
output = [0 for i in range(n)]

for i in range(n-1):
  a, b = (int(_) for _ in input().split()) 
  arr[a-1][b-1] = 1
  for x in range(a-1):
    if arr[x][a-1] == 1:
      arr[x][b-1] = 1

for i in range(q):
  p, q = (int(_) for _ in input().split()) 
  for i, x in enumerate(arr[p-1]):
    if x == 1:
      output[i] += q
    
print(' '.join([str(x) for x in output]))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [0 for i in range(n)]  # 親
        self.children = [set([i]) for i in range(n)]  # 子の一覧

    # xの属する木の根を求める
    def find(self, x):
        if 0 == x:
            return

        pa = self.par[x]
        self.children[pa] = self.children[pa] | self.children[x]
        self.find(pa)
        return


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

tree = UnionFind(N+1)

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

# print(tree.par)

for i in range(N+1):
    tree.find(i)

# print(tree.children)

anslist = [0]*(N+1)
for i in range(Q):
    p, x = map(int, input().split())
    addset = tree.children[p]
    for index in addset:
        anslist[index] += x

ans = ""
for i in anslist[1:]:
    ans += str(i)+" "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
import copy
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 

ans = [0] * N
for i in range(N):
    ans[i] += point_root[i]
    if es.get(i, None) != None:
        next_nodes = es[i] # これからポイントを足し行くやつら
    else:
        continue
    
    visited = [False] * N
    visited[i] = True
    idx_n = 0
    while idx_n <= len(next_nodes)-1:
        #idx_n = 0
        if idx_n <= len(next_nodes)-1:
            if visited[next_nodes[idx_n]] == False:
                ans[next_nodes[idx_n]] += point_root[i]
                visited[next_nodes[idx_n]] = True
            #print("--",es,next_nodes)
                #print(es[next_nodes[0]])
                #print("ne",next_nodes)
                idx = next_nodes[idx_n]
                #print("aaa",idx, es)
                tmp = es.get(idx, None)
                if tmp != None:
                    next_nodes.extend(tmp)
                    idx_n += 1
                #next_nodes = next_nodes[1:]
            else:
                idx_n += 1
        else:
            break

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,q= map(int,input().split())

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

ans = np.zeros(n)
dp = {i:np.zeros(n) for i in range(1,n+1)}
for i in range(1,n+1):
  dp[i][i-1] = 1
for i in range(n,0,-1):
  for j in edges[i]:
    dp[i] += dp[j]

queries = [0]*(n+1)
for _ in range(q):
  p,x = map(int,input().split())
  queries[p] += x
for i in range(1,n+1):
  ans += queries[i]*dp[i]
    
st = ""
for i in range(n):
  if i != 0:
    st+=" "
  st+= str(int(ans[i]))
print(st)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
N,Q = map(int,input().split())

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

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

def dig(i,tmp):
    tmp += adds[i]
    ans[i] = tmp
    for v in tree[i]: dig(v,tmp)

tmp = 0
dig(1,tmp)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
N, Q = map(int, input().split())
A = [[] for i in range(N)]
P = []
X = []
c = [0]*N
def add(p, x):
    for a in A[p]:
        c[a] += x
        add(a, x)

for i in range(N-1):
    a, b = map(int, input().split())
    A[a-1].append(b-1)
for i in range(Q):
    p, x = map(int, input().split())
    P.append(p-1)
    X.append(x)
for i in range(Q):
    p = P[i]
    x = X[i]
    c[p] += x
    add(p, x)
print(' '.join(map(str,c)))

Submission status: Time Limit Exceeded

Solution code:
def bfs(graph, start, weight, ):
	queue = [start]
	while queue:
		label = queue.pop(0)
		cnt[label-1] += weight
		queue += graph.get(label,[])

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

cnt = [0 for i in range(n)]
dic = {}
for i in range(n-1):
	if a[i][0] not in dic:
		dic[a[i][0]] = [a[i][1]]
	else:
		dic[a[i][0]].append(a[i][1])

for i in range(q):
	bfs(dic, b[i][0], b[i][1])
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
tree_list = []
count_list = [0]*N

def make_tree(a,b):
  if len(tree_list) == 0:
    tree_list.append([a,b])
    tree_list.append([b])
  else:
    for i in range(len(tree_list)):
      if a in tree_list[i]:
        tree_list[i].append(b)
      if i == len(tree_list)-1:
        tree_list.append([b])
def count(p,x):
  for i in range(len(tree_list)):
    if tree_list[i][0] == p:
      for i in tree_list[i]:
        count_list[i-1] += x 
for i in range(N-1):
  a,b = map(int,input().split())
  make_tree(a,b)
for i in range(Q):
  p,x = map(int,input().split())
  count(p,x)
count_list = [str(i) for i in count_list]
print(" ".join(count_list))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ed = [[] for i in range(n)]
cd = [[] for i in range(n)]
r = [i+1 for i in range(n)]
cnt = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    ed[a-1].append(b)
    ed[b-1].append(a)

st = [1]
while len(st) != 0:
    v = st.pop()
    cd[v-1] = list(set(ed[v-1]) & set(r))
    for item in list(set([i+1 for i in range(n)]) - set(r)):
        cd[item-1] += cd[v-1]
    r.remove(v)
    st += cd[v-1]

for i in range(q):
    p, x = map(int, input().split())       
    cnt[p-1] += x
    for item in cd[p-1]:
        cnt[item-1] += x
ans = ""
for c in cnt:
    ans += (str(c) + " ")

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

G = Graph()

N, Q = getlist()
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a, b)
	G.add_edge(b, a)

plus = [0 for i in range(N + 1)]
for i in range(Q):
	p, x = getlist()
	plus[p] += x


q = deque() 
ans = [0 for i in range(N)]
visit = [-1 for i in range(N + 1)]
visit[1] = 1
q.append(1)
while q:
	m = q.pop()
	visit[m] = 1
	ans[m - 1] += plus[m]
	x = ans[m - 1]
	for i in G.graph[m]:
		if visit[i] == -1:
			q.append(i)
			ans[i - 1] += x

print(" ".join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

mi = lambda: map(int, input().split())

N, Q = mi()
A = [[0] for _ in range(1, N+1)]

parent = [0] * N
child = [[] for _ in range(N)]
for i in range(N-1):
  a, b = mi()
  parent[b-1] = a-1

child[0] = A
for i in range(1, N):
  child[i].append(A[i])
  
for i in range(N):
  p = parent[i]
  while p != 0:
    child[p].append(A[i])
    p = parent[p]

for i in range(Q):
  p, x = mi()
  for c in child[p-1]:
      c[0] += x

print(' '.join([str(a[0]) for a in A]))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
chi = [set([i]) for i in range(N)]


for n in range(N-1):
    a,b = map(int, input().split())
    chi[a-1].add(b-1)
    for i in range(N):
        if a-1 in chi[i]:
            chi[i] = chi[i] | chi[a-1]  
            
cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   for i in chi[p-1]:
       cnt[i] += x

for n in range(N):
    print(cnt[n], end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(300000)
N, Q = map(int,input().split())
edge_from = defaultdict(list)
cnt = [0]*N
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge_from[a].append(b)
tmp = [0]*N
for i in range(Q):
    p, x = map(int,input().split())
    tmp[p-1] += x
def rec(v, x):
    x += tmp[v]
    cnt[v] = x
    for nx in edge_from[v]:
        rec(nx, x)
rec(0, 0)
for i in range(N):
    print(cnt[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:

a,b=map(int,input().split())
y=[]
for i in range(a-1):
    v=list(map(int,input().split()))
    y.append(v)
y.sort(key=lambda net:net[0])
ans=[0]*a
for j in range(b):
    c,d=map(int,input().split())
    ans[c-1]=ans[c-1]+d
for k in range(a-1):
    yy=y[k][0]-1
    zz=y[k][1]-1
    ans[zz]=ans[zz]+ans[yy]
print(*ans,sep=" ")

Submission status: Time Limit Exceeded

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

ct = [0] * (n + 1)
e = [[] for _ in range(n + 1)]
c = {}

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

for _ in range(q):
    p, q = map(int, input().split())
    target = c.get(p)
    if target is None:
        tmp = [p]
        target = []
        while len(tmp):
            t = tmp.pop()
            target.append(t)
            for nt in e[t]:
                tmp.append(nt)
        c[p] = target
    for t in target:
        ct[t] += q

print(*ct[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(300000)
input = sys.stdin.readline

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

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

Co = [0] * (N + 1)


def chase(now, nodes, su):
    Co[now] = Ps[now] + su
    nodes.append(now)
    for c in children[now]:
        chase(c, nodes, Co[now])


chase(1, [], 0)

Co.pop(0)
print(" ".join(map(str, Co)))

Submission status: Time Limit Exceeded

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


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    e = [list(map(int, input().split())) for _ in range(n-1)]
    p = [list(map(int, input().split())) for _ in range(q)]

    e2 = [{} for _ in range(n)]
    for ee in e:
        a, b = ee
        e2[a-1][b-1] = 1
        e2[b-1][a-1] = 1

    counters = [0 for _ in range(n)]
    for pp in p:
        counters[pp[0]-1] += pp[1]

    def dfs(x, p_sum):
        counters[x] += p_sum
        for y in e2[x]:
            del e2[y][x]
            dfs(y, counters[x])

    dfs(0, 0)
    print(*counters)


main()

Submission status: Time Limit Exceeded

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
    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
counts = collections.defaultdict(int)
for i in range(1,n+1):
    for z in affections[i]:
        counts[z] += counter[i]

ans = ""
for i in range(1,n+1):
    ans += str(counts[i]) + " "
print(ans)