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 set_child(from_p) -> int:
    global effect_list
    global start_edge_list
    effect_list[from_p].add(from_p)
    if from_p not in start_edge_list:
        return effect_list[from_p]
    for edge in edge_list:
        if from_p == edge[0]:
            effect_list[from_p].add(edge[1])
            children = set_child(edge[1])
            if children:
                for j in children:
                    effect_list[from_p].add(j)
        if from_p < edge[0]:
            return effect_list[from_p]
    return effect_list[from_p]


N, Q = input().split(' ')
N = int(N)
Q = int(Q)
ab = [input().split(' ') for i in range(N - 1)]
px = [input().split(' ') for i in range(Q)]

edge_list = sorted(ab)
start_edge_list = [e[0] for e in edge_list]

effect_list = defaultdict(lambda: set())  # key: pi, value: piから影響を受ける頂点すべて
index = 0
for i in range(N):
    top_n = i + 1
    set_child(str(top_n))

result = [0 for i in range(N)]
for impact in px:
    top_n = impact[0]
    val = int(impact[1])

    if top_n in effect_list:
        for target in effect_list[top_n]:
            result[int(target) - 1] += val

result_str = [str(i) for i in result]
print(' '.join(result_str))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
T = [[0, [], []] for _ in range(N+1)] #counter, parents, children
E = sorted([list(map(int, input().split())) for _ in range(N-1)], key=lambda x:x[0])
for e in E:
  p = e[0] if e[0] in T[1][2] else e[1]
  if 1 in e:
    p = 1
  c = e[0]+e[1]-p
  T[c][1] += T[p][1]
  T[c][1].append(p)
  for q in T[c][1]:
    T[q][2].append(c)
for _ in range(Q):
  p, x = map(int, input().split())
  T[p][0] += x
  for c in T[p][2]:
    T[c][0] += x
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)

Submission status: Time Limit Exceeded

Solution code:
line1 = input().split()
n = int(line1[0])
q = int(line1[1])

sahen = [0 for num in range(n)]
uhen = [0 for num in range(n)]

for num in range(n-1):
  inp =input().split()
  sahen[num] = int(inp[0])
  uhen[num] = int(inp[1])

j = [0 for num in range(q)]
for num in range(q):
  inpt =input().split()
  j[num] = [int(inpt[0]),int(inpt[1])]

result = [0 for num in range(n)]

for num2 in j:
  if (num2[0] in sahen):
    start = sahen.index(num2[0])
    for num in range(start,n):
      result[num] += num2[1]
  else:
    result[num2[0]-1] += num2[1]

print(*result)

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を使い回し高速化
  n2acn[i] = get_all_children_node(i, [])

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 numpy as np

n,q = map(int,input().split())
lst = {i+1:[] for i in range(n)}
for _ in range(n-1):
  l,r = map(int,input().split())
  lst[l].append(r)
counter=[0 for _ in range(n)]

for _ in range(q):
  p,x = map(int,input().split())
  temp = [p]
  while len(temp)!=0:
    search_num = temp.pop()
    counter[search_num-1]+=x
    temp+=lst[search_num]
    
ans = " ".join([str(i) for i in counter])
print(ans)

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)

multi_child = [[] for i in range(N)]
for i in range(N):
    multi_child[i].append(i)
    v = parent[i]
    while v != -1:
        multi_child[v].append(i)
        v = parent[v]


# make a function
def add(lst, p, x):
    if child[p] == []:
        lst[p] += x
    else:
        lst[p] += x
        for v in child[p]:
            add(lst, v, x)

## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    for v in multi_child[p]:
        count[v] += x
    
print(' '.join(map(str, count)))

Submission status: Time Limit Exceeded

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

Part = [[i] for i in range(N+1)]
tmp = {1}
while (tmp):
  tmp2 = set()
  for i in tmp:
    for j in range(len(AB)):
      if i == AB[j][0]:
        for k in range(1,N+1):
          if i in Part[k]:
            Part[k].append(AB[j][1])
        tmp2.add(AB[j][1])
  tmp = tmp2

Counter = [0] * (N+1)
for i in range(len(P)):
  for j in Part[P[i][0]]:
    Counter[j] += P[i][1]
print(*[Counter[i] for i in range(1,N+1)])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

num_node, num_query = map(int, input().split())
node_info = [map(int, input().split()) for i in range(num_node-1)]
query_info = [map(int, input().split()) for i in range(num_query)]

numpy_layer = np.zeros(num_node)
numpy_size = np.zeros(num_node)
numpy_layer[0] = 1

for ai, bi in node_info:
    ai_layer = numpy_layer[int(ai)-1]
    numpy_layer[int(bi)-1] = ai_layer + 1

for node, size in query_info:
    node_size = int(numpy_layer[node-1])
    numpy_size[node-1] += size
    # 根を探す
    numpy_size[np.where(numpy_layer > node_size)] += size

numpy_size = numpy_size.astype("int64")
print(*numpy_size)

Submission status: Time Limit Exceeded

Solution code:

NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])
candidate_list = [0] * (N-1)
tree_dict = {}
#Make tree dict
for i in range(N-1):
    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])
    tree_dict[i+1] = {
                'count': 0,
                'has_trees': []
            }
    candidate_list[N-2-i] = (a,b)
tree_dict[N] = {
    'count': 0,
    'has_trees': []
    }
for candidate in candidate_list:
    a = candidate[0]
    b = candidate[1]
    tree_dict[a]['has_trees'] += tree_dict[b]['has_trees'] + [b]
        

for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    tree_dict[p]['count'] += x
    for num in tree_dict[p]['has_trees']:
        tree_dict[num]['count'] += x

out_put_list = []
for each_dict in tree_dict.values():
    out_put_list.append(str(each_dict['count']))
print(' '.join(out_put_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
edge = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

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

ans = [0] * n
def dfs(cur, c, root):
    # print(cur, c, root)
    ans[cur] = c
    for next in edge[cur]:
        if next != root:
            dfs(next, c + cost[next], cur)

dfs(0, cost[0], -1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:


import sys
sys.setrecursionlimit(200000)

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


def search(n):
    global P,res

    for l in L[n]:
        res[l]=res[n]+P[l]
        search(l)

N,Q=acinput()

L=[[]for i in range(N+1)]

for i in range(N-1):
    tmp=acinput()
    L[tmp[0]].append(tmp[1])

P=[0]*(N+1)
for i in range(Q):
    tmp=acinput()
    P[tmp[0]]+=tmp[1]

res=[0]*(N+1)
res[1]=P[1]
search(1)

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

Submission status: Time Limit Exceeded

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

ab_list = []
is_ab = True
done_list = []

while is_ab:
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))
    done_list.append(a)
    done_list.append(b)
    if set(done_list) == set(range(1, n+1)):
        break

px_total_dict = {node_id: 0 for node_id in range(1, n+1)}
for _ in range(q):
    p, x = list(map(int, input().split()))
    px_total_dict[p] += x

ab_list = sorted(ab_list, key=lambda x: x[0])

count_list = [0] * n
next_child_list = []

parent2children_dict = {i: [] for i in range(1, n+1)}

for i, ab in enumerate(ab_list):
    a, b = ab
    # print('a, b = ({}, {})'.format(a, b))
    next_child_list.append(b)

    if i != len(ab_list) - 1 and ab_list[i+1][0] == a:
        # 次の辺も同じノードが始点だったら
        continue
    else:
        parent2children_dict[a] = next_child_list
        next_child_list = []

# print(parent2children_dict)

for node_id in range(1, n+1):
    # print('node_id: {}'.format(node_id))
    # count = sum([x for p, x in px_list if p == node_id])
    count = px_total_dict[node_id]
    child_list = parent2children_dict[node_id]
    # print(child_list)
    count_list[node_id-1] += count
    for child_node_id in child_list:
        count_list[child_node_id-1] += count_list[node_id-1]

    # print(count_list)

ans = ' '.join([str(x) for x in count_list])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))

sys.setrecursionlimit(10 ** 9)


def main():
    N, Q = MAP()
    AB = [LIST() for _ in range(N-1)]
    PX = [LIST() for _ in range(Q)]
    count = [0] * N

    for q in range(Q):
        queue = deque([PX[q][0]])
        top = set([])

        while 1:
            if len(queue) == 0: break
            flag = False
            last = queue.popleft()
            top.add(last)

            for i in range(N-1):
                if AB[i][0] == last:
                    flag = True
                    queue.append(AB[i][1])

            if not flag and len(queue) == 0: break

        for t in top:
            count[t-1] += PX[q][1]

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import collections
import bisect
import fractions
mod=1000000007
pi=3.1415926535897932
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
# fractions.gcd(x,y)
def lcm(a,b): return a*b//fractions.gcd(a,b)
def eof(t): print(t); exit()

def qul(d,l,p):
    if p in d:
        for j in d[p]:
            if j in d:
                if j not in l:
                    l.append(j)
                qul(d,l,j)
            else:
                l.append(j)
def sol():
    d={}
    n,q=map(int,input().split())
    for i in range(n-1):
        a,b=map(int,input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a]=[b]
    w=[0]*(n+1)
    for i in d:
        d[i].sort(reverse=True)
    for i in range(q):
        p,x=map(int,input().split())
        w[p]+=x
    for i in range(n,0,-1):
        l=[]
        qul(d,l,i)
        for j in l:
            w[j]+=w[i]
        #print(i,l)
    print(*w[1:])

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
def all_children(node_no, direct_children_list):
    res = set([])
    direct_children = direct_children_list[node_no]
    if len(direct_children) == 0:
        return set([node_no])
    for child in direct_children:
        res = res | set([child]) | all_children(child, direct_children_list)
    return res | set([node_no])


if __name__ == '__main__':
    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)]

    ab = sorted(ab, key=lambda x:x[0])

    direct_children = [set() for i in range(n)]
    direct_parent = [set() for i in range(n)]
    levels = [0 for i in range(n)]

    for i in range(n-1):
        a, b = ab[i]
        direct_children[a - 1].add(b - 1)
        direct_parent[b - 1].add(a - 1)

    # 前子ノードの列挙
    children = [set() for i in range(n)]
    for i in range(n):
        children[i] = all_children(i, direct_children)
    # print(children)

    counters = [0 for i in range(n)]
    # operation
    for i in range(q):
        p,x  = px[i]
        add_child = children[p-1]
        # print(add_child)
        for child_index in children[p-1]:
            counters[child_index] += x

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

Submission status: Time Limit Exceeded

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

ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
vs = [list(map(int, input().split(" ")))  for _ in range(Q)]
dic = dict.fromkeys(range(1,N+1), 1)
rlt = dict.fromkeys(range(1,N+1), 0)
for i in range(N-1):
  dic[ns[i][1]] = ns[i][0]
  
for q in vs:
  rlt[q[0]] = rlt[q[0]] + q[1]
  l = [i for i in range(q[0]+1,N+1) if dic[i] == q[0]]
  while len(l) > 0:
    t = l.pop(0)
    rlt[t] = rlt[t] + q[1]
    l1 = [i for i in range(t+1,N+1) if dic[i] == t]
    l.extend(l1)
    
print(" ".join(map(str, list(rlt.values()))))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
n,q= map(int,input().split())
nodes = [[]for _ in range(n+1)]
subnode = [[]for _ in range(n+1)]
value = [0 for _ in range(n+1)]
updated = [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):
    temp = []
    for v in nodes[node]:
        if v !=p:
            temp= temp+ dfs(v,node)
    my = temp+[node]
    subnode[node]=my
    return my
dfs(1,-1)
for i in range(1,n+1):
    for v in subnode[i]:
        updated[v]+=value[i]
print(*updated[1:])

Submission status: Time Limit Exceeded

Solution code:
import heapq
n, m= map(int, input().split())

links = []

sums = [0] * (n + 1)

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

uppers = [[1, x] for x in range(n + 1)]

for l in links:
  # print(l, uppers)
  uppers[l[1]] += uppers[l[0]]
  uppers[l[1]] = list(set(uppers[l[1]]))
  
for _ in range(m):
  p, x = map(int, input().split())
  for i in range(n+1):
    if p in uppers[i]:
      sums[i] += x

print(*sums[1:])

Submission status: Time Limit Exceeded

Solution code:


import sys
sys.setrecursionlimit(200000)

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


def search(n):
    global P,res

    for l in L[n]:
        res[l]=res[n]+P[l]
        search(l)

N,Q=acinput()

L=[[]for i in range(N+1)]

for i in range(N-1):
    tmp=acinput()
    L[tmp[0]].append(tmp[1])

P=[0]*(N+1)
for i in range(Q):
    tmp=acinput()
    P[tmp[0]]+=tmp[1]

res=[0]*(N+1)
res[1]=P[1]
search(1)

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

Submission status: Time Limit Exceeded

Solution code:
def dfs(tree: dict, count: list) -> list:
    res = [0] * (N + 1)

    stack = [1]
    while stack:
        label = stack.pop(0)
        res[label] = count[label]
        if tree[label] != []:
            for next_label in tree[label]:
                count[next_label] += count[label]
            stack = tree[label] + stack

    return res


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

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

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

ans = dfs(tree, count)
print(*ans[1:])

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())
    a[x].append(y)
#    print(a)
  
  for i in range(n):
    for j in range(i+1,n):
      if a[j][0] in a[i]:
        for k in a[j]:
          if k not in a[i]:
            a[i].append(k)
#  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:
def A():
    a = int(input())
    s = str(input())
    if a<3200:
        print('red')
    else:
        print(s)

def B():
    n = int(input())
    a = input().split()
    s = 0
    for i in range(n):
        s += (1/int(a[i]))
    print(1/s)

def C():
    n = int(input())
    v = sorted([int(i) for i in input().split()])

    if n == 2:
        print((v[0]+v[1])/2)
        return

    for i in range(1, n):
        v[i] = (v[i]+v[i-1])/2

    print(v[-1])

class Node:
    def __init__(self, n):
        self.num = n
        self.next = []

def D():
    temp = [int(j) for j in input().split()]
    n = temp[0]
    q = temp[1]

    d = {}
    for i in range(n-1):
        temp = [int(j) for j in input().split()]
        if temp[0] not in d.keys():
            d[temp[0]] = [temp[1]]
        else:
            d[temp[0]].append(temp[1])
    
    ans = [0]*(n+1)
    for i in range(q):
        temp = [int(j) for j in input().split()]
        root = temp[0]
        val = temp[1]

        stack = [root]
        while (stack != []):
            ans[stack[0]] += val
            if stack[0] in d.keys():
                stack += d[stack[0]]

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

D()

Submission status: Time Limit Exceeded

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

    t = [[] for _ in range(n+1)]
    o = [0 for _ in range(n)]

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

    for _ in range(q):
        p, x = map(int, input().split())
        o[p-1] += x
        s = list(t[p])
        while True:
            if len(s) == 0:
                break
            m = s.pop()
            o[m-1] += x
            if len(t[m]) != 0:
                s = s + t[m]

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

if __name__ == "__main__":
    f_d()

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, visited, x):
    if len(visited)==1:
        xs[p] +=x
    for c, d in enumerate(rin[p]):
        if d !=0:
            visited.append(c)
            xs[c] +=x
            dfs(c,visited, x)
    return xs
for ele in p_x:
    xs = dfs(ele[0]-1, [ele[0]-1], ele[1])
xs = map(str, xs)
print(' '.join(xs))

Submission status: Time Limit Exceeded

Solution code:
import sys;sys.setrecursionlimit(10000000)
M=lambda:map(int,input().split())
n,q=M()
s=[set()for _ in range(n)]
for i in range(n-1):
  a,b=M()
  s[a-1].add(b-1)
  s[b-1].add(a-1)
p=[0]*n
for i in range(q):
  a,b=M()
  p[a-1]+=b
x=[0]*n
def bfs(I,U):
  global x,s
  u=U
  u+=p[I]
  x[I]=u
  for i in s[I]:
    s[i].discard(I)
    bfs(i,u)
bfs(0,0)
print(*x)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
glp = [[] for i in range(N+1)]
glp[1] = list(range(N))
counter = [0]*N

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

for i, g in enumerate(glp):
    for gi in g:
        glp[i].extend(glp[gi])

for i in range(Q):
    p, x = map(int, input().split())
    for pi in glp[p]:
        counter[pi-1] += x
    counter[p-1] += x
    
print(" ".join(map(str, counter)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
N, Q = map(int, input().split())

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

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

children = defaultdict(set)
for i in range(1,N+1):
    children[i].add(i)
    d = deque(connection[i])
    checked = set(connection[i])
    while len(d) > 0:
        x = d.popleft()
        children[i].add(x)
        d += connection[x]

c = Counter()
for opr in operations:
    for num in children[opr[0]]:
        c[num-1] += opr[1]

ans = []
for i in range(N):
    ans.append(str(c[i]))
print(' '.join(ans))

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 = []
    for i in range(n):
        l.append(0)

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

        for j in range(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(1000000000)

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

tree = [[] for _ in range(n)]
ope = [0]*n
opef=[False]*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
    global opef
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        tmp=0
        if opef[i]==False:
            tmp=ope[i]
            opef[i]=True
        counter(i,num+tmp)

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

for i in range(n):
    if opef[i]==False:
        opef[i]=True
        counter(i,ope[i])

print(*ret)

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 px_ in px:
        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:
import sys
sys.setrecursionlimit(1000000)
def main():
  def calc_results(results, pvalue, i):
    results[i] = pvalue + values[i]
    if childrens[i] is None:
      return
    for j in childrens[i]:
      calc_results(results, results[i], j)
  n, q = map(int, input().split())
  values = [0] * (n + 1)
  results = [0] * (n + 1)
  childrens = [None] * (n + 1)
  dc = [None for i in range(0, n + 1)]
  for i in range(n - 1):
    a, b = map(int, input().split())
    if childrens[a] is None:
      childrens[a] = []
    childrens[a].append(b)
  for _ in range(q):
    p, x = map(int, input().split())
    values[p] += x
  calc_results(results, 0, 1)
  print(*[results[i] for i in range(1, n + 1)])
main()

Submission status: Time Limit Exceeded

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

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

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

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

ans = [0] * N

def setAnswer(parent, number, value):
    ans[number] = value

    for i in M[number]:
        if i != parent:
            setAnswer(number, i, value + X[i])

setAnswer(0, 0, X[0])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
cost = []
res = []
tree = []
level = []
childs = []
parent = []
cache = []
for i in range(210000):
    res.append(0)
    tree.append([])
    level.append(-1)
    childs.append([])
    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)

def make_level(index, lev, pp):
    l = 0
    level[index] = lev
    parent[index] = pp
    for next in tree[index]:
        #print("index {0} search {1}".format(index, next))
        # 逆走はしない
        if level[next] != -1:
            #print("CANNOT MOVE to {0}".format(next))
            continue
        # 子供に親を設定
        parent[next] = index
        curparent = index
        make_level(next, lev + 1, index)

make_level(1, 0, -1)

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

#print("parent")
#print(parent[0:10])

def calc_cost(index):
    if index == -1:
        return 0
    #print("index = {0}, parent = {1}".format(index, parent[index]))
    if cache[parent[index]] != -1:
        #print(" parent has cache: {0}".format(cache[parent[index]]))
        cache[index] = cost[index] + cache[parent[index]]
        #print(" RET index = {0}, COST = {1}".format(index, cost[index] + cache[parent[index]]))
        return cost[index] + cache[parent[index]]
    else:
        cc = calc_cost(parent[index])
        #print(" parent hasNOT cache: {0}".format(cc))
        cache[index] = cost[index] + cc
        #print(" RET index = {0}, COST = {1}".format(index,cost[index] + cc))
        return cost[index] + cc



for i in range(1, n+1):
    #print("llll:{0}".format(i))
    res[i] = calc_cost(i)

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

Submission status: Time Limit Exceeded

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

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

for i in range(n-1):
  a, b = map(int,input().split())
  a, b = a-1, b-1
  gu[b].append(a)
  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:
n, q = map(int, input().split())

ct = [0] * (n + 1)
target = {i: [i] for i in range(n + 1)}

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

for _ in range(q):
    p, q = map(int, input().split())
    t = target[p]
    for ti in t:
        ct[ti] += q

print(*ct[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

def main():
    N,Q=map(int, input().split())
    T = defaultdict(list)
    C = defaultdict(int)
    PX = deque()
    for i in range(N-1):
        a,b=map(int, input().split())
        T[a].append(b)
        for k in T.keys():
            if a in T[k]:
                T[k].append(b)
    for i in range(Q):
        p,x=map(int, input().split())
        PX.append((p,x))
    
    while len(PX) > 0:
        px = PX.pop()
        C[px[0]] += px[1]
        for i in T[px[0]]:
            C[i] += px[1]

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

if __name__ == '__main__':
    main()