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:
tmp1 = input().split()
n = int(tmp1[0])
q = int(tmp1[1])
a = [0]*(n-1)
b = [0]*(n-1)
p = [0]*q
x = [0]*q
ans = [0]*n
flag = [0]*n
box = []
for i in range(n-1):
  tmp2 = list(map(int, input().split()))
  box.append(tmp2)
  
#print(box)
box.sort()
#print(box)
for i in range(n-1):
  a[i] = int(box[i][0])
  b[i] = int(box[i][1])
  
for i in range(q):
  tmp3 = input().split()
  p[i] = int(tmp3[0])
  x[i] = int(tmp3[1])
#print(a, b, p, x)

for i in range(n):
  for j in range(n):
    flag[j] = 0
  #親頂点を探す
  oya = i
  flag[i] = 1
  for j in range(n-2, -1, -1):
    if b[j]-1 == oya:
      #print(a[j], b[j])
      flag[a[j]-1] = 1
      oya = a[j]-1
  #print(flag)
  #点数を数える
  for j in range(q):
    if flag[p[j]-1] == 1:
      ans[i] = ans[i] + x[j]

for i in range(n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,q=map(int,input().split())
  a=[[i] for i in range(n+1)]
  b=[0 for i in range(n+1)]
  
  for i in range(n-1):
    x,y=map(int,input().split())
    for j in range(n-1):
      if x in a[j]:
        a[j].append(y)
#        print(a)
 
#  print("aaa",a)
  for i in range(q):
    x,y=map(int,input().split())
#    print("c,y",x,y)
#    print("ax",a[x])
#    print("B",b)
    for j in a[x]:
#      print("j",j)
      b[j-1]+=y
#      print(b)

       
  print(*b[:n])

if __name__ == "__main__":
    main()

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-1):
    print(ans[i],end=" ")
print(ans[N-1])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
a=[]
b=[]
s=[0]


for i in range(0,n-1):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
    s.append(0)
for i in range(0,q):
    P,X=map(int,input().split())
    s[P-1]=s[P-1]+X


for j in range(0,n-1):
    for i in range(0,n-1):
        if i+1==a[j]:
            s[b[j]-1]=s[b[j]-1]+s[a[j]-1]

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

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

n , q = map(int, input().split())
lab = []
points = [0]*n
for i in range(n-1):
    lab.append(list(map(int, input().split())))
lpx = []
for i in range(q):
    lpx.append(list(map(int, input().split())))

lll = []
for i in range(n):
    childs = Queue()
    inc = []
    parent = i+1
    childs.put(parent)
    while childs.qsize() > 0:
        a = childs.get()
        inc.append(a)
        for k in lab:
            if k[0] == a:
                childs.put(k[1])
    lll.append(list(set(inc)))

for i in lpx:
    for j in lll[i[0]-1]:
        points[j-1] += i[1]
print(' '.join(map(str, points)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, q = map(int, input().split())
counter = [0 for _ in range(n)]
tree = [[] for _ in range(n)]

roots = [0]
stack = []
for _ in range(n - 1):
  a, b = map(lambda x: int(x) - 1, input().split())
  if a in roots:
    tree[a].append(b)
    roots.append(b)
  elif b in roots:
    tree[b].append(a)
    roots.append(a)
  else:
    stack.append((a, b))
    
  next_stack = []
  for edge in stack:
    a, b = edge
    if a in roots:
      tree[a].append(b)
      roots.append(b)
    elif b in roots:
      tree[b].append(a)
      roots.append(a)
    else:
      next_stack.append((a, b))
  stack = next_stack

def count(p: int, x: int) -> None:
  counter[p] += x
  children = tree[p]
  if children:
    for child in children:
      count(child, x)

for _ in range(q):
  p, x = map(int, input().split())
  count(p-1, x)
  
print(' '.join(map(str, counter)))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().split())
top_list = [list(map(int,input().split())) for i in range(n - 1)]
ope_list = [list(map(int,input().split())) for i in range(q)]

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

for i in ope_list:
#自分にスコアを加算
    ans[i[0] - 1] += i[1]
#自分にぶら下がる頂点にスコアを加算
    for j in top_list:
        if i[0] == j[0]:
            ans[j[1] -1] += i[1]
#自分の孫以下の頂点にスコアを加算
            for k in top_list:
                if j[1] == k[0]:
                    ans[k[1] -1] += i[1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from copy import deepcopy

sys.setrecursionlimit(10 ** 5 + 5)

n, q = list(map(int, input().split()))
edge = defaultdict(set)
for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge[a].add(b)
    edge[b].add(a)

tree = defaultdict(lambda: {"count": 0, "children": set()})
ROOT = 0


def rec(parent, ancestors):
    # print(parent)
    for ancestor in ancestors:
        for child in edge[parent]:
            if child in ancestors:
                continue
            tree[ancestor]["children"].add(child)
            new_ancestors = deepcopy(ancestors)
            new_ancestors.add(child)
            rec(child, new_ancestors)


rec(ROOT, set([ROOT]))

# print(tree)

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

score = [0] * n
for p, x in opr:
    score[p] += x
    for child in tree[p]["children"]:
        score[child] += x

answer = " ".join(map(str, score))
print(answer)

Submission status: Time Limit Exceeded

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

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

c = [0]*N
res = [0]*N
for p,x in PX:
    c[p-1] += x

def BFS(start,edges,N,c):
    roots=[[] for _ in range(N)]
    for a,b in edges:
        roots[a-1]+=[(b-1,c[b-1])]
    queue=[]
    visited=[start]
    queue.append(start)
    res[start] = c[start]
    while queue:
        label = queue.pop()
        for i,c in roots[label]:
            if i not in visited:
                res[i]= res[label]+c
                queue += [i]
                visited.append(i)
    return res
print(*BFS(0,edges,N,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,b = Line(N-1)
p,x = Line(Q)

for i in range(N-1):
    a[i] -= 1
    b[i] -= 1

for i in range(Q):
    p[i] -= 1


#深さ優先探索
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 = [[] for _ in range(N)]
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:
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.append(-1)
    parent.append(-1)
    cost.append(0)

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)

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

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

l_2 = [0 for i in range(n+1)]
for p, x in px:
    l_2[p] += x

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, l_2):
    ans[start] += x
    if len(graph[start]) == 0:
        return
    else:
        for i in graph[start]:
            dfs_2(graph, i, ans, x+l_2[i], l_2)
 
ans = [0 for i in range(n+1)]
dfs_2(l, 1, ans, l_2[1], l_2)
        
for i in range(1, n+1):
    print(ans[i], end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

N, Q = map(int, input().split())
nodes = np.array([0]*(N+1))
subtree_flag = [False]*(N+1)
subtree = np.array([[0]*(N+1) for i in range(N+1)])
tree = [set() for _ in range(N+1)]

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

def add(p, x):
  dq = deque()
  dq.append(p)
  subtree[p][p] = 1
  while len(dq) > 0:
    tp = dq.popleft()
    nodes[tp] += x
    subtree[p][tp] = 1
    for np in tree[tp]:
      dq.append(np)

for i in range(Q):
  p, x = map(int, input().split())
  if subtree_flag[p]:
     nodes += subtree[p] * x
  else:
    add(p, x)
    subtree_flag[p]=True
print(" ".join([str(i) for i in nodes[1:]]))

Submission status: Time Limit Exceeded

Solution code:
def bubunki(akan):
    for l in range(n-1) :
        if(a[l] == akan) :
            z[b[l]] += x1
            bubunki(b[l]) 
    return 



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

a = []
b = []
p = [] 
x = []
z = [0] * (n+1)

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

for j in range(q) :
    p1,x1 = map(int,input().split())
    # p.append(p1)
    # x.append(x1)
    z[p1] += x1
    bubunki(p1)        


# for k in range(q) :

    # z[p[k]] += x[k]

    # bubunki(p[k])        

s = ""
for l in range(1,n+1) :
    s +=  str(z[l]) + " "
    
print(s)

Submission status: Time Limit Exceeded

Solution code:
def get_subgraph(node):
  subgraph = [node]
  for i, j in edges:
    if node == i:
      subgraph.extend(get_subgraph(j))
  return subgraph

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

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

counter = list(map(int, list('0'*n)))

for p, x in tasks:
  subgraph = get_subgraph(p)
  for i in subgraph:
    counter[i-1] += x

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(G,v):
    seen[v]=True
    for next_v in G[v]:
        if G[next_v]==True:
            continue
        else:
            counter[next_v]+=counter[v]
            dfs(G,next_v)

seen=[False for _ in range(N+1)]
dfs(graph,1)
ans=''
for i in range(N):
    ans+=str(counter[i+1])+' '
print(ans)

Submission status: Time Limit Exceeded

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

a=[0]*N
b=[0]*N
p=[0]*(Q+1)
x=[0]*(Q+1)
Point=[0]*(N+1)

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

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


for j in range(1,Q+1):
  f=[]
  f.append(p[j])
  Point[p[j]]+=x[j]
  for i in range(1,N):
    boolian=True
    if(all(elem!=a[i] for elem in f)):
      boolian=False

    if(boolian):
      f.append(b[i])
      Point[b[i]]+=x[j]


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


print()

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()
    print(' '.join([str(counter[i]) for i in sorted(counter.keys())]))

Submission status: Time Limit Exceeded

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

    sub_tree_list = direct_sub_node[node]
    if sub_tree_list == []:
        return [node]
    else:
        tmp = []
        for sub in sub_tree_list:
            tmp += subtree(sub)
        return [node] + tmp

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: 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):
    temp = []
    for v in nodes[node]:
        if v !=p:
            value[v]+=score
            dfs(v,node,value[v])
dfs(1,-1,value[1])
print(*value[1:])

Submission status: Time Limit Exceeded

Solution code:
class Node:
  def __init__(self):
    self.counter = 0
    self.childs = []
    self.parents = set()
  def add_child(self, node):
    self.childs.append(node)
  def add_parents(self, node):
    self.parents.add(node)

N, Q = [int(i) for i in input().split()]
ndic = {}
for i in range(1, N+1):
  ndic[i] = Node()
  ndic[i].add_child(ndic[i])
for i in range(N-1):
  a, b = [int(i) for i in input().split()]
  ndic[a].add_child(ndic[b])
  ndic[b].add_parents(ndic[a])
  for n in ndic[a].parents:
    n.add_child(ndic[b])  
    ndic[b].add_parents(n)

from collections import defaultdict
adddict = defaultdict(int)
for i in range(Q):
  p, x = [int(i) for i in input().split()]
  adddict[p] += x
for k, v in adddict.items():
  if v > 0:
    for j in ndic[k].childs:
      j.counter += v
ans = ""
for k, v in ndic.items():
  ans += str(v.counter) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
tree = [list(map(int, input().split())) for i in range(N-1)]
process =  [list(map(int, input().split())) for i in range(Q)]
 
def next_node(node_num):
  next_nodes = []
  for edge in tree:
    if edge[0] == node_num:
      next_nodes.append(edge[1])
  return next_nodes
 
def all_nodes(num):
  x = [] 
  add_nodes = next_node(num)
  while add_nodes != []:
    for i in add_nodes:
      add_nodes += next_node(i) 
      x += add_nodes
      add_nodes = []
  return x
 
 
def add(score, procedure):
  "procedure = [p, x]"
  score[procedure[0]-1] += procedure[1]
  for n in all_nodes(procedure[0]):
    score[n-1] += procedure[1]
  return score
 
 
score = [0]*N
for procedure in process:
  add(score, procedure)

for s in score:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
n,q = list(map(int,input().split()))
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

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

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

ret = [0] * (n+1)
def add_tree(node,value):
    retn = value
    if dd_px[node]:
        retn += dd_px.pop(node)
    ret[node] += retn
    if dd_ab[node]:
        for n in dd_ab.pop(node):
            add_tree(n,retn)
add_tree(1,0)
for i in ret[1::]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from copy import deepcopy

sys.setrecursionlimit(10 ** 5 + 5)

n, q = list(map(int, input().split()))
edge = defaultdict(set)
for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge[a].add(b)
    edge[b].add(a)

tree = defaultdict(lambda: {"count": 0, "children": set()})
ROOT = 0


def rec(parent, ancestors):
    # print(parent)
    for child in edge[parent]:
        if child in ancestors:
            continue

        for ancestor in ancestors:
            tree[ancestor]["children"].add(child)
        new_ancestors = deepcopy(ancestors)
        new_ancestors.add(child)
        rec(child, new_ancestors)


rec(ROOT, set([ROOT]))

# print(tree)

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

score = [0] * n
for p, x in opr:
    score[p] += x
    for child in tree[p]["children"]:
        score[child] += x

answer = " ".join(map(str, score))
print(answer)

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)

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

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 = ''
for i in range(n):
    ans += str(d[i] + x_sorted[i]) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
#入力n,q,の受け取り
n,q = map(int, input().split())

#ab[i]には頂点iにつながる頂点たちが列挙されている
#ただし、最後の数字は各頂点以下に加えるxの値
ab = [0]*n
for i in range(n):
    ab[i] = []
for i in range(n-1):
    inp = list(map(int, input().split()))
    inp.sort()
    ab[inp[0]-1].append(inp[1])
for i in range(n):
    ab[i].append(0)

#入力p,xの受け取り
for i in range(q):
    px = list(map(int, input().split()))
    ab[px[0]-1][-1] += px[1]

#あとは答えを出して行って終わり
for i in range(n):
    len_ = len(ab[i])-1
    for j in range(len_):
        ab[ ab[i][j]-1 ][-1] += ab[i][-1]
for i in range(n):
    print(ab[i][-1],end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
#+++++
		
def main():
	n,q = map(int, input().split())
	tree=[[] for _ in range(n+1)]
	hh=[ 0 for _ in range(n+1)]
	ret=[0 for _ in range(n+1)]
	
	for i in range(n-1):
		pa,ch = map(int, input().split())
		tree[pa].append(ch)
		
	for v in range(q):
		nd, hv = map(int, input().split())
		hh[nd] += hv
		
	ol = queue.Queue(n+1)
	ret[1]=hh[1]
	vv=hh[1]
	for cc in tree[1]:
		ol.put((vv,cc))
		
	while not ol.empty():
		ph,nd=ol.get()
		ret[nd]=hh[nd]+ph
		vv=ret[nd]
		for cc in tree[nd]:
			ol.put((vv,cc))

	print(' '.join([str(v) for v in ret[1:]]))
	
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

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


def ps(z):
	if z!=1:
		parent[z-1]=[z]+ps(a[b.index(z)])
		return(parent[z-1])
	else:
		parent[z-1]=[z]
		return([z])

parent=[]
for i in range(N):
	parent.append([])
for i in range(N):
	ps(i+1)

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


ans=[0]*N
for i in range(N):
	for j in range(len(parent[i])):
		ans[i]+=qs[parent[i][j]-1]

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

Submission status: Time Limit Exceeded

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 = {}
counter = {i: 0 for i in range(1, N + 1)}

for i in range(N-1):
    if a[i] in trees.keys():
        trees[a[i]].append(b[i])
    else:
        trees[a[i]] = [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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N,Q = list(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)]
counter = []
ab.append([0,1])

px_shin =[0 for i in range(N)]
temp=0
def dfs(p,x):
    for i in range(N):
        if ab[i][0] == p:
            for j in range(Q):##
                if px[j][0] == ab[i][1]:
                    px_shin[ab[i][1]-1] += px[j][1]
            px_shin[ab[i][1]-1]+=x
            dfs(ab[i][1], px_shin[ab[i][1]-1])
        
dfs(0,0)
print(' '.join(map(str, px_shin)))

Submission status: Time Limit Exceeded

Solution code:

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

ans=[0]*N
ab=[[] for i in range(N)]

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

px=[]
for _ in range(Q):
    px.append(list(map(int,input().split())))
    
    
for j,item in enumerate(ab[::-1]):
    for i in item:
        ab[N-j-1].extend(ab[i])

#for i in range(N):
#    ab[i]=list(set(ab[i]))
    
for ppxx in px:
    p,x=ppxx
    for i in ab[p-1]:
        ans[i]=ans[i]+x
    ans[p-1]=ans[p-1]+x
#    print(ans) 

print(str(''.join(str(j)+' ' for j in ans)[:-1]))

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
a = []
p = []
edges = {}
ans = [0]*(N+1)
for _ in range(N-1):
    a.append(list(map(int, input().split())))
for _ in range(Q):
    p.append(list(map(int, input().split())))
for edge in a:
    if edge[0] in edges.keys():
        edges[edge[0]].append(edge[1])
    else:
        edges[edge[0]] = [edge[1]]

q = {}
for value in p:
    if value[0] in q:
        q[value[0]] += value[1]
    else:       
        q[value[0]] = value[1]

for key, value in q.items():
    que = [key]
    while que != []:
        target = que.pop()
        ans[target] += value
        if target in edges.keys():
            for edge in edges[target]:
                que.append(edge)

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
a = []
b = []
for i in range (n-1):
  t_a, t_b = map(int, input().split())
  a.append(t_a-1)
  b.append(t_b-1)
p = []
x = []
for i in range (q):
  t_p, t_x = map(int, input().split())
  p.append(t_p-1)
  x.append(t_x)
c = [0 for i in range(n)]
tree = [[None, [], False] for i in range(n)]
tree[0][2] = True

while(1):
  for hen in range(n-1):
    if tree[a[hen]][2] == True:
      tree[a[hen]][1].append(b[hen])
      tree[b[hen]][0] = a[hen]
      tree[b[hen]][2] = True
    elif tree[b[hen]][2] == True:
      tree[a[hen]][1].append(a[hen])
      tree[a[hen]][0] = b[hen]
      tree[a[hen]][2] = True
  finish = True
  for peak in tree:
    if peak[2] == False:
      finish = False
      break
  if finish == True:
    break

def calc(p, x, ret):
  if len(tree[p][1]) == 0:
    ret[p] += x
  else:
    for child in tree[p][1]:
      ret = calc(child, x, ret)
    ret[p] += x
  return ret

ans = [0 for i in range(n)]
for i in range(q):
  t_c = calc(p[i], x[i], [0 for i in range(n)])
  ans = list(map(lambda x,y: x+y, ans, t_c))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

class Node:
    def __init__(self, key):
        self.key = key
        self.child = []
        self.point = 0

n, q = map(int, input().split())
a, b, p, x = [], [], [], []
nodes = []
nodes.append(None)
ans = []

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

for i in range(q):
    temp1, temp2 = map(int, input().split())
    p.append(temp1)
    x.append(temp2)

# Make node list
for i in range(1, n+1):
    node = Node(i)
    nodes.append(node)


for i in range(n-1):
    nodeParent = nodes[a[i]]
    nodeChild = nodes[b[i]]
    nodeParent.child.append(nodeChild)

# def printNode(node):
#     ans.append(node.point)
#     for child in node.child:
#         printNode(child)

def printNode(node):
    for i in range(1, n+1):
        ans.append(nodes[i].point)

def addCount(node, point):
    node.point += point
    # for child in node.child:
    #     addCount(child, point)

def traverse(node, point):
#    print(node.point)
    node.point += point
    for child in node.child:
        traverse(child, node.point)

for i in range(q):
    node = nodes[p[i]]
    addCount(node, x[i])

traverse(nodes[1], 0)
printNode(nodes[1])

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

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,b = Line(N-1)
p,x = Line(Q)

for i in range(N-1):
    a[i] -= 1
    b[i] -= 1

for i in range(Q):
    p[i] -= 1


#深さ優先探索
def dfs(pt,v):
    '''
    input
        pt: 各点との結合場所を格納した2次元配列　pt=[[1, 2, 3], [0], [5, 0], [6, 0], [6], [2], [3, 4]]
        v: 初期点 v=0

    output
        d: 初期点からの距離を格納した配列 d=[0, 1, 1, 1, 3, 2, 2]
    '''
    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 = [[] for _ in range(N)]
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:
import sys
import collections
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
cost = collections.deque([])
res = collections.deque([])
tree = collections.deque([])
level = collections.deque([])
parent = collections.deque([])
cache = collections.deque([])
for i in range(210000):
    res.append(0)
    tree.append(collections.deque([]))
    level.append(-1)
    parent.append(-1)
    cost.append(0)
    cache.append(-1)

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
        parent[next] = index
        cost[next] += cost[index]
        make_level(next, lev + 1, index)

make_level(1, 0, -1)

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