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:
from collections import defaultdict, deque

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

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

count = defaultdict(int)
for i in range(q):
    pp, xx = map(int, input().split())
    count[pp] += xx


def traverse():
    dq = deque()
    dq.append(1)
    counter = defaultdict(int)
    visited = set()
    while True:
        if len(dq) == 0:
            break
        p = dq.popleft()
        visited.add(p)
        counter[p] += count[p]
        for c in edge[p]:
            if c in visited:
                continue
            counter[c] += counter[p]
            dq.append(c)
    return counter


if __name__ == '__main__':
    counter = traverse()
    for i in range(n):
        if i != n - 1:
            print(counter[i + 1], end= " ")
        else:
            print(counter[i + 1])

Submission status: Time Limit Exceeded

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

def upper(a,b):
  if gu[a] == {}:
    gl[a].add(b)
  else:
    gl[a].add(b)
    for l in gu[a]:
      upper(l, b)

candidate = set()
for i in range(n-1):
  a, b = map(int,input().split())
  a, b = a-1, b-1
  gu[b].add(a)
  candidate.add(b)

for b in candidate:
  for a in gu[b]:
    upper(a,b)

#print(gu)
#print(gl)

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

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

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


#深さ優先探索
def dfs(pt,v):
    n=len(pt)
    d=[-1]*n
    check_visited = [False]*n
    check_visited[v] = True
    S = [v]
    d[v] = 0
    while S:
        v1 = S.pop()
        for i in pt[v1]:
            if check_visited[i] == False:
                check_visited[i] = True
                d[i] = d[v1] + 1
                S.append(i)
    return d


pt = defaultdict(list)
for i in range(N-1):
    pt[a[i]].append(b[i])
    pt[b[i]].append(a[i])
d = dfs(pt,0)

parent = defaultdict(list)
for i in range(N-1):
    if d[a[i]]>d[b[i]]:
        parent[a[i]].append(b[i])
    else:
        parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(N):
    now = i
    ans = 0
    while now != 0:
        ans += val[now]
        now = parent[now][0]
    print(val[0]+ans)

Submission status: Time Limit Exceeded

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

connection_dictionary = {}  # key:id, value:child list
# 読み込んでグラフを作成
# ノード間のつながりができてから，親と子を決定する
node_list = [0 for _ in range(N)]  # nodeごとのadd number

for _ in range(N-1):
    ab = input().split()
    a = int(ab[0]) - 1
    b = int(ab[1]) - 1
    if a in connection_dictionary:
        connection_dictionary[a].append(b)
    else:
        connection_dictionary[a] = [b]

# ノードごとに足される数を保存する
for _ in range(Q):
    px = input().split()
    p = int(px[0])
    x = int(px[1])
    node_list[p-1] += x
# のーど1からノードにあるadd numberを足していく
# node 1 から親子関係を決定する
calc_list = [0]
while calc_list:
    calc_number = calc_list.pop(0)
    add_number = node_list[calc_number]
    if calc_number in connection_dictionary:
        child_list = connection_dictionary[calc_number]
        for child in child_list:
            node_list[child] += add_number
            calc_list.append(child)
# 出力
for node in node_list:
    print(node, end=" ")
print("")

Submission status: Time Limit Exceeded

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

for i in range(n-1):
    ab[i] = tuple(map(int, input().split()))

ab.sort(reverse=True)

for a, b in ab:
    a -= 1
    b -= 1
    tl[a].append(b)
    tl[a].extend(tl[b])

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

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

Submission status: Time Limit Exceeded

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

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)
for i in cnt:
  print(i, end =" ")

Submission status: Time Limit Exceeded

Solution code:
nodelist=[]
operation=[]

n,q=map(int,input().split())
for i in range(n-1):
    nodelist+=list(input().split())
for i in range(q):
    operation+=list(input().split())
counter=[0 for i in range(n)]
add_counter=[0 for i in range(n)]


#1回の操作

#cnt=0
#cnt_temp=0
for j in range(q):
    add_counter=[0 for i in range(n)]
    storage=[]
    while True:
        for i in range(n-1):
            if int(nodelist[i*2])==int(operation[j*2]):
                if add_counter[int(nodelist[i*2])-1]==0:
                    counter[(int(nodelist[i*2])-1)]+=int(operation[j*2+1])
                    add_counter[int(nodelist[i*2])-1]=1
                if add_counter[int(nodelist[i*2+1])-1]==0:
                    counter[(int(nodelist[i*2+1])-1)]+=int(operation[j*2+1])
                    add_counter[int(nodelist[i*2+1])-1]=1
                storage+=nodelist[i*2+1]
            if int(nodelist[i*2+1])==int(operation[j*2]):
                 if add_counter[int(nodelist[i*2+1])-1]==0:
                    counter[(int(nodelist[i*2+1])-1)]+=int(operation[j*2+1])
                    add_counter[int(nodelist[i*2+1])-1]=1
        if len(storage)==0:
            break
        else:
            operation[j*2]=storage[0]
            del storage[0]
            
result=""
for i in range(n):
  result+=str(counter[i])+" "
  
print(result)

Submission status: Time Limit Exceeded

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

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

Solution code:

class Node(object):
  def __init__(self,name):
    self.name=name
    self.value = 0
    self.nodes_names = []
    self.nodes = []
  
  def set_nodes(self,all_Nodes_dic):
    for name,node in all_Nodes_dic.items():
      if name in self.nodes_names:
        self.nodes.append(node)
  
  def update_value(self,val):
    self.value += val
    for node in self.nodes:
      node.update_value(val)



def main():
  N,Q = map(int,input().split())
  all_Nodes = {}
  tasks=[]
  for _ in range(N-1):
    name,pname = map(int,input().split())
    if name not in all_Nodes.keys():
      node = Node(name)
      node.nodes_names.append(pname)
      all_Nodes.update({name:node})
    else:
      node = all_Nodes[name]
      node.nodes_names.append(pname)
    
    if pname not in all_Nodes.keys():
      node = Node(pname)
      all_Nodes.update({pname:node})
  
  for _ in range(Q):
    node_name,point = map(int,input().split())
    tasks.append((node_name,point))

  for node in all_Nodes.values():
    node.set_nodes(all_Nodes)
  
  for name,value in tasks:
    parent = all_Nodes[name]
    parent.update_value(value)
  
  sorted_lst = sorted(list(all_Nodes.values()), key=lambda x:x.name)

  print(" ".join([str(node.value) for node in sorted_lst]))
  return


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000000)

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

tree = [[] for _ in range(n)]
ope = [0]*n
ret=[0]*n

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

def counter(target,num):
    global ret
    global ope
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        tmp=ope[i]
        counter(i,num+tmp)

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

counter(0,ope[0])

print(*ret)

Submission status: Time Limit Exceeded

Solution code:
def main():

    N, Q = [int(x) for x in input().split()]
    counter = {key:0 for key in range(1, N+1)}
    parent_dict = dict()
    child_data = {x:list() for x in range(1, N+1)}
    child_data[1] = [1]

    # 要は木構造っぽいものを作りたいが、再起関数だと処理時間で死んだ
    # なので、親一覧 + 自分のリストを作成する
    for _ in range(N - 1):
        a, b = [int(x) for x in input().split()]
        parent_dict[b] = a
        child_data[b].append(b)
        temp = b
        while temp in parent_dict:
            temp = parent_dict[temp]
            child_data[temp].append(b)

    # 親一覧 + 自分のリストから答えを出す   
    for _ in range(Q):
        p, x = [int(x) for x in input().split()]
        for key in child_data[p]:
            counter[key] += x

    print(" ".join([str(val) for key, val in sorted(counter.items())]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

tree = {}
counter = [0]*N
result = [0]*N
numbers = []

for o in operations:
    counter[int(o[0])-1] += int(o[1])

result[0] = counter[0]

# print(counter)

for e in edges:
    parent = e[0]
    sun = e[1]
    if sun in numbers:
        sun = e[0]
        parent = e[1]
    else:
        numbers.append(sun)

    if sun in tree:
        tree[sun].append(parent)
    else:
        tree[sun] = [parent]

    if parent in tree:
        tree[sun].extend(tree[parent])


# print(tree)

for k in tree.keys():
    result[int(k)-1] += counter[int(k) - 1]
    for i in tree[k]:
        result[int(k)-1] += counter[int(i)-1]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,Q = list(map(int, input().split(" ")))
v_list = np.zeros(N+1, dtype=np.int) # n-1でやること注意
dic_tree = {}
for i in range(N):
    dic_tree[i+1] = [] 

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

# make tree
for k in reversed(range(N)):
    if len(dic_tree) == 0:
        continue
    
    for node in dic_tree[k+1]:
        if len(dic_tree[node]) != 0:
            dic_tree[k+1].extend(dic_tree[node])
        
for i in range(Q):
    p, x = list(map(int, input().split(" ")))
    
    v_list[dic_tree[p]] += x
    v_list[p] += x

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
cost = collections.deque([])
tree = collections.deque([])
level = collections.deque([])
parent = collections.deque([])

for i in range(210000):
    tree.append(collections.deque([]))
level = collections.deque([-1] * 200100)
parent = collections.deque([-1] * 200100)
cost = collections.deque([0] * 200100)

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

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

def make_level(index, lev, pp):
    level[index] = lev
    parent[index] = pp
    for next in tree[index]:
        if level[next] != -1:
            continue
        cost[next] += cost[index]
        make_level(next, lev + 1, index)

make_level(1, 0, -1)

print(" ".join(list(map(str, cost))[1:n+1]))

Submission status: Time Limit Exceeded

Solution code:
#import pysnooper
import os,re,sys,operator,math,heapq,string
from collections import Counter,deque
from operator import itemgetter
from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
from copy import deepcopy

setrecursionlimit(10**6)

def rec(pp,xx):
    for i in range(n):
        if gragh[pp][i]:
            cnt[i]+=xx
            hen[i]-=1
            if tree[i]:
                continue
            if hen[i]<0:
                rec(i,xx)
                break
            rec(i,xx)
    return
n,q=map(int,stdin.readline().rstrip().split())
gragh=[[0]*n for _ in range(n)]
cnt=[0]*n
tree=[0]*n
hen=[0]*n
for i in range(n-1):
    a,b=map(int,stdin.readline().rstrip().split())
    tree[a-1],tree[b-1]=0,1
    hen[a-1]+=1
    gragh[a-1][b-1]=1
for i in range(q):
    p,x=map(int,stdin.readline().rstrip().split())
    cnt[p-1]+=x
    rec(p-1,x)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
abL = [[int(x) for x in input().split()] for _ in range(N-1)]
tree = [[0]*(N+1) for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for a,b in abL:
    graph[a].append(b)
 
for a in range(N, 0, -1):
    incL = graph[a]
    for b in incL:
        for i in range(a):
            if a in graph[i]:
                graph[i].append(b)
    graph[a].append(a)
 
pxL = [[int(x) for x in input().split()] for _ in range(Q)]
 
for p,x in pxL:
    tmpL = graph[p]
    for b in tmpL:
        tree[p][b] += x
 
for i in range(1, N+1):
    sum_ = 0
    for j in range(1, N+1):
        sum_ += tree[j][i]
    print(sum_, end=" ")

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


def bfs(pt,v):
    n=len(pt)
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
    return d


pt = defaultdict(list)
for i in range(N-1):
    pt[a[i]].append(b[i])
    pt[b[i]].append(a[i])
d = bfs(pt,0)

parent = defaultdict(list)
for i in range(N-1):
    if d[a[i]]>d[b[i]]:
        parent[a[i]].append(b[i])
    else:
        parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(N):
    now = i
    ans = 0
    while now != 0:
        ans += val[now]
        now = parent[now][0]
    print(val[0]+ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
n,q= map(int,input().split())
nodes = [[]for _ in range(n+1)]
value = [0 for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().split())
    nodes[a].append(b)
    nodes[b].append(a)
query = []
for i in range(q):
    a, b = map(int, sys.stdin.readline().split())
    value[a]+=b
def dfs(node,p,score):
    for v in nodes[node]:
        if v !=p:
            value[v]+=score
            dfs(v,node,value[v])

dfs(1,-1,value[1])
for i in range(1,n+1):
    sys.stdout.write('{} '.format(int(value[i])))

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
n, q = map(int, input().split())
#g = np.zeros((n+1,n+1))
g = [[0 for i in range(n+1)] for j in range(n+1)]
ans = [0] * n #np.zeros(n) #Do not Foget -1
for i in range(n-1):
    a, b = map(int, input().split())
    g[a][b] = 1

#c = np.zeros((n+1,n+1))

c = []
for i in range(n+1):
    c.append([i])

for j in reversed(range(n+1)):
    for i in range(n+1):
        if g[i][j] == 1:
            c[i]+=c[j]

#print(c)

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

#print(ans)

ans_str = str(ans)
ans_str = ans_str.replace('[','').replace(']','').replace(',','')
print(ans_str)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

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)
P = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    P[p-1] += x
result = [0] * n
def r(current, point):
    result[current] += point
    for ee in E[current]:
        r(ee, point+P[ee]) 
 
r(0, P[0])

print(*result)

Submission status: Time Limit Exceeded

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

# print(x_sorted)

cost = dict() # コストテーブル
for i, j in ab:
    cost[i - 1] = cost.get(i - 1, []) + [(j - 1, x_sorted[i - 1])]

d = [0 for i in range(n)]
qq = [(d[0], 0)]
while qq:
    (du, u) = qq.pop()
    for v, weight in cost.get(u, []):
        alt = du + weight
        d[v] = alt
        qq.append((alt, v))

ans_list = []
for i in range(n):
    ans_list.append(str(d[i] + x_sorted[i]))

print(' '.join(ans_list))

Submission status: Time Limit Exceeded

Solution code:
class TreeObj:
    def __init__(self):
        self.value = 0
        self.childs = []

    def getValue(self):
        return self.value

    def setValue(self, v):
        self.value = v

    def getChilds(self):
        return self.childs

    def addChild(self, node):
        self.childs.append(node)


def appender(tree, v):
    tree.setValue(tree.getValue()+v)
    for child in tree.getChilds():
        appender(child, v)


def main():
    N, Q = list(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)]

    root = TreeObj()  # 1
    trees = {1: root}   # 1
    for a, b in AB:
        if (a not in trees):
            trees[a] = TreeObj()

        tree = trees[a]
        if (b not in tree.getChilds()):
            child = TreeObj()
            trees[b] = child
            tree.getChilds().append(child)

        tree = None

    for p, x in PX:
        tree = trees[p]
        appender(tree, x)

    tmp = [str(trees[key].getValue()) for key in sorted(trees.keys())]
    print(' '.join(tmp))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math;

def swap(a,b):
    return (b,a)

def gcd(a,b):
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def search(p,x):
    ans[p-1] += x
    if p not in d.keys():
        return
    for i in d[p]:
        search(i,x)

def main():
    global n,q,ab,px,d,ans
    n,q = map(int,input().split())
    ab = [[]]
    for i in range(n-1):
        ab.append([])
        a,b = map(int,input().split())
        ab[i].append(a)
        ab[i].append(b)
    ab.sort()
    if [] in ab:
        ab.remove([])
    px = [[]]
    for i in range(q):
        px.append([])
        p,x = map(int,input().split())
        px[i].append(p)
        px[i].append(x)
    d = {}
    c = ab[0][0]
    l = []
    for i in range(n-1):
        if c!=ab[i][0]:
            d[c] = l.copy()
            c = ab[i][0]
            l.clear()
            l.append(ab[i][1])
        else:
            l.append(ab[i][1])
    d[c] = l.copy()
    px.sort()
    if [] in px:
        px.remove([])
    ans = [0 for x in range(n)]
    for i in range(q):
        search(px[i][0],px[i][1])
    for i in ans:
        print(i)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
x = list(map(int, input().split()))
n = x[0]
q = x[1]
#n = 4
#q = 3

ans = [0]*n
ki = {}
for i in range(1,n+1):
    ki[i] = []

#z = ["1 2", "2 3", "2 4"]

for i in range(n-1):
    e = list(map(int, input().split()))
    #e = list(map(int, z[i].split()))
    ki[e[0]].append(e[1])

#print(ki)

def df(graph, start, point):
    stack = [start]
    visited = []
    while stack:
        v = stack.pop(0)
        ans[v - 1] += point
        if v not in visited:
            visited.append(v)
            stack = graph.get(v, []) + stack

#y = ["2 10", "1 100", "3 1"]
for i in range(q):
    p = list(map(int, input().split()))
    #p = list(map(int, y[i].split()))
    df(ki, p[0], p[1])

for n in ans:
    print(n, end=" ")

Submission status: Time Limit Exceeded

Solution code:
# -*- condig:utf-8 -*-

import sys
sys.setrecursionlimit(10000000)

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

g = {}
o = []
counter = []
for i in range(n+1):
  counter.append(0)
  o.append(0)

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

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


queue = [1]
parents = []
while queue:
  p = queue.pop(0)
  parents.append(p)
  count = o[p]
  flag = False
  for i in g[p]:
    if not i in parents:
      queue.append(i)
    else:
      count += counter[i]
  counter[p] += count
 
for i in range(1, n+1):
  print(counter[i], end=' ')

Submission status: Time Limit Exceeded

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)
    count[a] = 0

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

Solution code:
from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = {}
for i in range(N):
    edge_map[i] = deque([])

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


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

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

def dfs_res(idx, parent, diff):
    global res_list
    global counters
    if calculated[i]:
        return res_list[idx]
    res = counters[idx] + diff
    res_list[idx] = res
    calculated[idx] = True
    for child in edge_map[idx]:
        if child == parent:
            continue
        dfs_res(child, idx, res)
    return

dfs_res(0, None, 0)

ans = " ".join([str(i) for i in res_list])
print(ans)

Submission status: Time Limit Exceeded

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

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


a_s = sorted(a)
b_s = sorted(b)
ans= [ 0 for _ in range(N)]


for i in range(Q):
    ans[b_s[i][0]-1] += b_s[i][1]

for i in range(N-1):
    ans[a_s[i][1]-1] += ans[a_s[i][0]-1]

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
dic = {}
amari = {}
for i in range(N-1):
  k, v = map(int, input().split())
  try:
    dic[k].append(v)
  except KeyError:
    dic[k] = [v]
  try:
    amari.pop(k)
  except KeyError:
    pass
  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: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
a = [0] * N
b = [0] * N
p = [0] * Q
x = [0] * Q
isTree = [False] * N
output = [0] * N

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

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

for i in range(Q):
    isTree = [False] * N
    for j in range(N):
        isTree[p[i] - 1] = True
        if p[i] == a[j] or isTree[a[j] - 1]:
            isTree[b[j] - 1] = True
    for j in range(N):
        if isTree[j]:
            output[j] += x[i]

print(*output)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


def bfs(pt,v):
    n=len(pt)
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
    return d


pt = [[] for _ in range(N)]
for i in range(N-1):
    pt[a[i]].append(b[i])
    pt[b[i]].append(a[i])
d = bfs(pt,0)

parent = defaultdict(list)
for i in range(N-1):
    if d[a[i]]>d[b[i]]:
        parent[a[i]].append(b[i])
    else:
        parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(N):
    now = i
    ans = 0
    while now != 0:
        ans += val[now]
        now = parent[now][0]
    print(val[0]+ans)