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

def dfs(graph, start):
    stack = [start]
    visited = []
    while stack:
        label = stack.pop(0)
        if label not in visited:
            visited.append(label)
            stack = graph.get(label, []) + stack
    return visited
  
tree = defaultdict(list)
N,Q = map(int, input().split())

lst1 = [list(map(int, input().split())) for i in range(N-1)]
lst2 = [list(map(int, input().split())) for i in range(Q)]
for i in range(N):
  dict(tree)[i+1] = []
for i in lst1:
  tree[i[0]].append(i[1])
ans = [0] * N
for i in lst2:
  start = i[0]
  for j in list(dfs(dict(tree), i[0])):
    if (start <= j):
      ans[j-1] += i[1]
print(" ".join(list(map(str,ans))))

Submission status: Time Limit Exceeded

Solution code:
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)



def main():
    N, Q = map(int, input().split())
    a_b = [list(map(int, input().split())) for _ in range(N - 1)]
    p_x = [list(map(int, input().split())) for _ in range(Q)]
    score = [0 for _ in range(N)]
    
    tree_dict = {}
    
    for i in a_b:        
        tree_dict.setdefault(i[0], []).append(i[1])
        
        for key, values in tree_dict.items():
            for i in values:
                if i in tree_dict:
                    tree_dict[key].extend(tree_dict[i])



    logging.info(tree_dict)

    for task in p_x:
        try:
            child = tree_dict[task[0]]
            for i in set(child):
                score[i - 1] += task[1]
            score[task[0] - 1] += task[1]
            
        except:
            score[task[0] - 1] += task[1]
                    
    
        

        
    answer = ""
    for i in score:
        answer += str(i)
        answer += " "

    print(answer)
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
from collections import OrderedDict

input = sys.stdin.readline
children = OrderedDict()

def rec(n, sum, result):
    global children
    v = children[n]

    sum += v['w']
    result.append([n, str(sum)])
    if not v['children']:
        return
    for c in v['children']:
        rec(c, sum, result)
    return

def main():
    N, Q = map(int, input().split())

    global children
    for _ in range(N-1):
        a, b = map(int, input().split())
        if a not in children:
            children[a] = {'children': [b], 'w': 0}
        else:
            children[a]['children'].append(b)
        if b not in children:
            children[b] = {'children': [], 'w': 0}

    for _ in range(Q):
        p, x = map(int, input().split())
        children[p]['w'] += x

    result = []
    rec(1, 0, result)

    result.sort(key=lambda x: x[0])
    print(' '.join(list(map(lambda x: x[1], result))))

main()

Submission status: Time Limit Exceeded

Solution code:
def DOWN(part_tree, p, N):
    flag = 0
    for i in range(1, N + 1):
        if part_tree[p][i] == 1:
            flag = 1
            break
    if flag == 0:
        return part_tree[p]
    else:
        for i in range(1, N + 1):
            if part_tree[p][i] == 1:
                A = DOWN(part_tree, i, N)
                for j in range(1, N + 1):
                    part_tree[p][j] += A[j]
        return part_tree[p]

def down(p, x, N, Point, part_tree):
    #print(Point)
    Point[p] += x
    for i in range(1, N + 1):
        if part_tree[p][i] == 1:
            down(i, x, N, Point, part_tree)

def main():
    N, Q = list(map(int, input().split(' ')))

    Point = [0 for i in range(N + 1)]
    part_tree = [[0 for i in range(N + 1)] for j in range(N + 1)]
    for i in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        part_tree[a][b] = 1
    DOWN(part_tree, 1, N)
    #print(part_tree)
    #print(Point)

    for i in range(Q):
        p, x = list(map(int, input().split(' ')))
        Point[p] += x
        for j in range(1, N + 1):
            if part_tree[p][j] == 1:
                Point[j] += x
    Point.pop(0)
    print(*Point)

if __name__ != 'main':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

edge = []
for _ in range(N-1):
    edge.append(list(map(int, input().split())))
edge = sorted(edge)
wgt = []
for _ in range(Q):
  wgt.append(list(map(int,input().split())))
#print(edge)

al = {} # adjacency list (dic)
n2w = {} # node to weight
#edge_1d = np.ravel(np.array(edge))
#for i in edge_1d:
for i in range(1,N+1):
  al[i] = []
  n2w[i] = 0 # initialize each node weight
[al[e[0]].append(e[1]) for e in edge]
#print(al)

n2acn = {}# node to all children node

def get_all_children_node(i, ret):
  if len(al[i]) == 0:
    return ret
  elif i in n2acn:
    return (ret + n2acn[i])
  else:
    for ci in al[i]:
      ret.append(ci)
      ret = get_all_children_node(ci, ret=ret)
    return ret

#for i in list(al.keys())[::-1]: # leaf nodeに近いところから計算することで，取得済みのacnを使い回し高速化
for p,_ in wgt[::-1]:
	n2acn[p] = get_all_children_node(p, [])

for p,x in wgt:
  n2w[p] += x
  for i in n2acn[p]:
    n2w[i] += x

ret = ''
for s in n2w.values():
  ret += str(s) + ' '
  
print(ret.strip())

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(x) for x in input().split()]
ab_list = [[int(x) for x in input().split()] for _ in range(N-1)]
tmp = [[int(x) for x in input().split()] for _ in range(Q)]
x_list = [0] * (N+1)
for p, x in tmp:
    x_list[p] += x
to = [[] for _ in range(N+1)]
for a, b in ab_list:
    to[b].append(a)
subtree = [[i] for i in range(N+1)]
for j in range(N, 0, -1):
    for u in to[j]:
        subtree[u].extend(subtree[j])
ans = [0] * N
for i, x in enumerate(x_list):
    for u in subtree[i]:
        ans[u-1] += x
print(' '.join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

N, Q = map(int, input().split())
children = [[i] for i in range(N)]  # 各頂点の持つ部分木の頂点の集合
edges = [tuple(map(int, input().split())) for _ in range(N-1)]
counts = np.zeros(N, dtype=np.int32)

for i in range(N-2, -1, -1):
    children[edges[i][0]-1] += children[edges[i][1]-1]

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

for count in counts:
    print(count, end=' ')

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N-1)]
px = [list(map(int, input().split())) for i in range(Q)]

count = [0] * N

def find_tree(n, x):
    for i in range(N-1):
        if ab[i][0] == n:
            count[ab[i][1]-1] += x
            find_tree(ab[i][1], x)

for i in range(Q):
    count[px[i][0]-1] += px[i][1]
    find_tree(px[i][0], px[i][1])

for c in count:
  print(c, end =' ')

Submission status: Time Limit Exceeded

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

def main():
    n, q = map(int, input().split())
    tree = []
    for i in range(n):
        tree.append([i + 1])

    for i in range(n - 1):
        m, c = map(int, input().split())
        for a in tree:
            if m == a[0]:
                a.append(c)
                break

    for i in range(len(tree)):
        buf = tree[-1 - i]
        if len(buf) == 1:
            pass
        else:
            for a in tree:
                if buf[0] in a[1:]:
                    a += buf[1:]
                    break

    counter = [0] * n

    for i in range(q):
        p, x = map(int, input().split())
        for a in tree:
            if p == a[0]:
                for j in a:
                    counter[j - 1] += x
                break

    print(*counter)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = [0]*N

a = []
b = []

ab = []

p = []
x = []

px = []

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

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

for i in range(Q):
    flag = [p[i]]
    ans[p[i]-1] += x[i]
    for j in range(N-1):
        if a[j] in flag:
            ans[b[j]-1] += x[i]
            flag.append(b[j])

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

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])
ab.sort()
px.sort()
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:
def roooot(arr, i):
    tmp = i
    while len(arr[i]) != 1:
        i = list(arr[i])[0]-1
        arr[tmp].add(i+1)

def pt(st):
    ret = 0
    for i in list(st):
        ret += cnt[i-1]
    print(ret, end=" ")

n, q = map(int, input().split())
cnt = [0]*n
root = [set([i+1]) for i in range(n)]

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

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

for i in root: pt(list(i))
print("")

Submission status: Time Limit Exceeded

Solution code:

def main():
    
    
    in1 = [int(e) for e in input().split()]
    n = in1[0]
    q = in1[1]

    a = []
    b = []
    for i in range(n-1):
        in1 = [int(e) for e in input().split()]
        a.append(in1[0])
        b.append(in1[1])

    p = []
    x = []
    for i in range(q):
        in1 = [int(e) for e in input().split()]
        p.append(in1[0])
        x.append(in1[1])

    l = [0] * n

    def addval(p,x):
        l[p-1] += x

        for j in range(p-1,n-1):
            #print('j',j)
            if(a[j] == p):
                addval(b[j],x)

    for i in range(q):
        addval(p[i],x[i])

    
    for i in range(n):
        print(l[i], end="")
        print(" ", end="")
        




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
dic = {}

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

v_list = [0 for _ in range(n)]

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


def add_v(num,value):
    v_list[num] = v_list[num] + value
    if num+1 in dic:
        for root in dic[num+1]:
            add_v(root-1, v_list[num])


add_v(0,0)


print(*v_list)

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]:
        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:
#!/usr/bin/env python
# coding: utf-8

# In[17]:


#from sys import stdin
#input = stdin.readline

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


# In[18]:


class Node:
    def __init__(self, nb, data): #コンストラクタ
        self.nb = nb
        self.data = data #ノードがもつ数値
        self.parent = -1 # nodeがrootのとき-1、それ以外番号
        self.childs = [] # childになるnode classが入る
        
    def connect_childs(self, child_class_):
        self.childs.append(child_class_)


# In[19]:


nodes = [Node(_+1, 0) for _ in range(N)]


# In[12]:


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


# In[13]:


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


# In[14]:


def sum_data_to_childs(nodes):
    datas = [0]*N
    
    datas[0] = nodes[0].data
    
    for i in range(1, N):
        nodes[i].data += nodes[nodes[i].parent].data
        #print(nodes[i].data)
        datas[i] = nodes[i].data
        
    return datas


# In[15]:


datas = sum_data_to_childs(nodes)


# In[16]:


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


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def resolve():
    n, q = map(int, input().split())
    ab = sorted(list(list(map(int, input().split())) for _ in range(n - 1)))
    pq = list(list(map(int, input().split())) for _ in range(q))
    d = defaultdict(list)
    counters = [0] * n
    child_nodes = [[0]] * n
    for a, b in ab:
        d[a].append(b)
    for p, q in pq:
        child = d[p]
        nodes = [p] + child
        while any([c in d for c in child]):
            new_nodes = []
            for c in child:
                if not child_nodes[c - 1]:
                    new_nodes += child_nodes[c - 1]
                elif c in d:
                    new_nodes += d[c]
            child = new_nodes
            nodes += new_nodes
        for n in nodes:
            counters[n - 1] += q
    print(" ".join([str(c) for c in counters]))


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

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:
def main():
    n, q = map(int, input().split())
    C = [list(map(int, input().split())) for i in range(n-1)]
    D = [list(map(int, input().split())) for i in range(q)]
    J, K, L = {}, {}, {}

    for c in C:
        if c[0] not in J:
            J[c[0]] = [c[1]]
        else:
            J[c[0]].append(c[1])

    for k, v in J.items():
        L[k] = [i for i in v]
        for i in L[k]:
            if i in list(J.keys()):
                L[k] += J[i]

    for d in D:
        if d[0] not in K:
            K[d[0]] = d[1]
        else:
            K[d[0]] += d[1]

    ans = [0 for i in range(n)]
    for k, v in K.items():
        ans[k-1] += v
        if k in L:
            for i in L[k]:
                ans[i-1] += v

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


if __name__ == "__main__":
    main()

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):
    if p[i] not in trees.keys():
        counter[p[i]] += x[i]
    else:
        counter[p[i]] += x[i]
        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:
from collections import defaultdict
N,Q = map(int,input().split())
d = defaultdict(list)

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

c = defaultdict(int)

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

ans = defaultdict(int)
que = [(1,0,-1)]
while len(que)>0:
    tmp = []
    for v,x,par in que:
        x += c[v]
        ans[v] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w,x,v))
    que = tmp

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

Submission status: Time Limit Exceeded

Solution code:

import sys

sys.setrecursionlimit(200000)

n,q = (int(num) for num in input().split())
neighbor = [[] for _ in range(n)]
visited = [0] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    ab.append((a,b))

    
for item in ab:
    a = item[0]
    b = item[1]
    neighbor[a].append(b)
    neighbor[b].append(a)
    
        
#print(par)
#print(neighbor)
#print(rank)

for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x
    
def calc(idx,neighbor,val,bias):
    val[idx] += bias
    for i in neighbor[idx]:
        if visited[i] == 0:
            visited[i] = 1
            calc(i,neighbor,val,val[idx])

visited[0] = 1
calc(0,neighbor,val,0)    
ans = ""    
for num in val:
    ans += str(num) + " "
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]

pp=[[] for i in range(n+1)]
for i in range(1,n+1):
    pp[p[i]].append(i)

from collections import deque
qu=deque([1])

i=0
while qu:
    qq=qu.popleft()
    l[qq]+=l[p[qq]]
    for j in pp[qq]:
        qu.append(j)


print(*l[1:])

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
def main():
    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)]
    score = [0]*n

    for _ in range(q):
        px_ = list(map(int, input().split()))
        start = int(px_[0])
        child = []
        child.append(start)

        for ab_ in ab:
            if ab_[0] == start :
                child.append(int(ab_[1]))
            elif ab_[0] in child and not(ab_[1] in child):
                child.append(int(ab_[1]))
        for i in child:
            score[int(i)-1] += px_[1]

    print(' '.join([str(j) for j in score]))

if __name__ == '__main__' :
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n-1)]
l.sort()
# print(l)

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

ch = [[] for _ in range(n)]
ad = [[] for _ in range(n)]

for i in range(n-1):
    a, b = l[i][0]-1, l[i][1]-1
    ch[a].append(b)
    ad[b].append(a)
    for x in ad[a]:
        ch[x].append(b)
        ad[b].append(x)

# print(ch)
# print(ad)

ans = [0 for _ in range(n)]
for i in range(q):
    p, x = lq[i][0]-1, lq[i][1]
    ans[p] += x
    for j in ch[p]:
        ans[j] += x

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)
def Nodify(n):
    for i in graph[n]:
        if Tree[i]==-1:
            Tree[i]=n
            Nodify(i)
def solve(n):
    for i in graph[n]:
        if i==Tree[n]:
            pass
        else:
            ans[i]=ans[n]+counter[i]
            solve(i)
n,q=map(int,input().split())
graph=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
Tree=[-1]*n
Nodify(0)
Tree[0]=-1
counter=[0 for _ in range(n)]
for _ in range(q):
    p,x=map(int,input().split())
    counter[p-1]+=x
ans=[-1]*n
ans[0]=counter[0]
solve(0)
for i in ans:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from collections import defaultdict

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

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


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

def solve(node, point):
    
    ans[node] += point
    visited[node] = True
    #print("aa", *ans, visited)
    if all(visited) == True:
        print(*ans)
        exit()

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(1000000)


def main():

    def read_tree(n):
        tree = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            a, b = [int(x) for x in stdin.readline().split()]
            tree[a].append(b)
        return tree

    def walk(p, i, tree, sibs):
        sibs[p].add(i)
        for sib in tree[i]:
            walk(p, sib, tree, sibs)

    def make_sibs(n, tree):
        sibs = [set() for _ in range(n + 1)]
        for p in range(1, n + 1):
            walk(p, p, tree, sibs)
        return sibs

    n, q = [int(x) for x in stdin.readline().split()]

    tree = read_tree(n)
    sibs = make_sibs(n, tree)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = [int(x) for x in stdin.readline().split()]
        for sib in sibs[p]:
            cnt[sib] += x

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


main()

Submission status: Time Limit Exceeded

Solution code:
N ,Q = map(int,input().split())
tree = []
counters = []
nodes = [0 for i in range(N)]
tree_list = [[] for i in range(N+1)]
for i in range(N-1):
  a,b = map(int,input().split())
  tree_list[a].append(b)
tree = sorted(tree)
for i in range(Q):
  counters.append(list(map(int,input().split())))

for i in range(len(tree_list)-1,0,-1):
  for j in tree_list[i]:
    tree_list[i].extend(tree_list[j])
  
for p,x in counters:
  nodes[p-1] += x
  for i in tree_list[p]:
    nodes[i-1] += x

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

Submission status: Time Limit Exceeded

Solution code:

N,Q=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PQ = [list(map(int,input().split())) for _ in range(Q)]
AB.sort()
PQ.sort()
l=[[] for _ in range(N)]
ans=[0]*N
for a,b in reversed(AB):
	l[a-1].append(b)
	l[a-1].extend(l[b-1])
for p,q in PQ:
	ans[p-1]+=q
	for i in l[p-1]:
		ans[i-1]+=q
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, q = map(int, input().split())
a_b = [list(map(int, input().split())) for i in range(n-1)]
p_x = [list(map(int, input().split())) for i in range(q)]
xs = [0 for i in range(n)]
rin = np.array([[0 for i in range(n)] for j in range(n)])
for node in a_b:
    rin[node[0]-1][node[1]-1] = 1
def dfs(p, x):
    for c, d in enumerate(rin[p]):
        if d !=0:
            xs[c] +=x
            dfs(c, x)
    return xs
for ele in p_x:
    xs[ele[0]-1] +=ele[1]
    xs = dfs(ele[0]-1, ele[1])
xs = map(str, xs)
print(' '.join(xs))

Submission status: Time Limit Exceeded

Solution code:
import queue

n,q = list(map(int,input().split()))
a = [0]*(n-1)
b = [0]*(n-1)
for i in range(n-1):
    a[i],b[i] = list(map(int,input().split()))
    a[i]-=1
    b[i]-=1
p = [0]*q
x = [0]*q
for i in range(q):
    p[i],x[i] = list(map(int,input().split()))
    p[i]-=1
    
d = {}
for i in range(n-1):
    d.setdefault(a[i],[]).append(b[i])
cnt = [0]*n
for i in range(q):
    que = queue.Queue()
    que.put(p[i])
    while not que.empty():
        new = que.get()
        cnt[new]+=x[i]
        if new in d:
            for j in range(len(d[new])):
                que.put(d[new][j])
for i in range(n):        
    print(cnt[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
# ab_list=[]
# for i in range(N-1):
#     a,b=map(int,input().split())
#     ab_list.append((a,b))

dic={}
inv_dic={}
for i in range(N-1):
    a,b=map(int,input().split())
    inv_dic[b]=a
for i in range(N):
    dic[i+1]=[i+1]
    
px_list=[]
for i in range(Q):
    p,x=map(int,input().split())
    px_list.append((p,x))


for key,item in inv_dic.items():
    next_key=key
    while True:
        dic[item].append(key)
        if item in inv_dic.keys():
            item=inv_dic[item]
        else:
            break
counts=[0]*N
for p,x in px_list:
    l=dic[p]
    for i in l:
        counts[i-1]+=x
print(" ".join([str(x) for x in counts]))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
point_array = [list(map(int,input().split())) for i in range(n-1)]
point_array.sort()
action_array = [list(map(int,input().split())) for i in range(q)]
solution = [0]*n

for i in range(q):
    solution[action_array[i][0]-1] += action_array[i][1]

for i in range(n-1):
    solution[point_array[i][1]-1] += solution[point_array[i][0]-1]
    
print(*solution)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
 
N,Q = (int(i) for i in input().split())
hen = {}
value = [0] * N
for _ in range(0,N-1):
    a,b = (int(i) for i in input().split())
    if a in hen:
        hen[a].append(b)
    else:
        hen[a] = [b]

def add(p,x):
    if p in hen:
        for i in hen[p]:
            value[i-1] = value[i-1] + x
            add(i,value[i-1])

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


add(1,value[0])
print(' '.join(map(str,value)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Aug 18 21:19:43 2019
ABC138D
@author: maezawa
"""

n, q = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    graph[ai].append(bi)
    graph[bi].append(ai)
    
parent = [[] for _ in range(n+1)]
child = [[] for _ in range(n+1)]
current = 1
while current <= n:
    for j in graph[current]:
        if current in child[j]:
            continue
        child[current].append(j)
    current += 1
#print(child)
parray = [-1]*(n+1)
parray[1] = 0
for i in range(1,n+1):
    for j in child[i]:
        parray[j] = i
#print(parray)
tpoint = [0]*(n+1)
for i in range(q):
    pi, xi = list(map(int, input().split()))
    tpoint[pi] += xi
tpmem = [-1]*(n+1)
tpmem[1] = tpoint[1]
for i in range(1, n+1):
    pi = 0
    j = i
    while True:
        if tpmem[j] != -1:
            pi += tpmem[j]
            break
        pi += tpoint[j]
        if parray[j] == -1:
            break
        j = parray[j]
    print(pi)
    tpmem[i] = pi