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:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())

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

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

def dfs(v, p):
    for u in edge[v]:
        if u != p:
            imos[u] += imos[v]
            dfs(u, v)

dfs(0, -1)
print(' '.join([str(x) for x in imos]))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
cnt = [0]*n
root = [[] for i in range(n)]

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

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

    tmpi = p-1
    tmparr = [tmpi]
    while tmparr:
        tmpi = tmparr.pop(0)
        cnt[tmpi] += x
        tmparr += root[tmpi]
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)

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

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

seen = [False] * (N + 1)
ans = [0] * (N + 1)


def dfs(e, v, x):
    seen[v] = True
    ans[v] += x
    for next_v in e[v]:
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v, x + q[next_v])


dfs(e, 1, q[1])
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:

# Setup
import sys
import collections
sys.setrecursionlimit(4100000)

n,q = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(n-1)]
p = [[int(i) for i in input().split()] for _ in range(q)]

childs = collections.defaultdict(list)

for A,B in a:
    childs[A].append(B)

counter = collections.defaultdict(int)
affections = collections.defaultdict(list)

for A,B in p:
    counter[A] += B
    if affections.get(A):
        continue
    current = A
    aff = []
    tosee = [current]
    while len(tosee) != 0:
        temp = tosee.pop()
        aff.append(temp)
        for z in childs[temp]:
            if affections.get(z):
                aff += affections[z]
            else:
                tosee.append(z)
    affections[A] = aff
counts = collections.defaultdict(int)
for i in range(1,n+1):
    for z in affections[i]:
        counts[z] += counter[i]

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

Submission status: Time Limit Exceeded

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

class Node:
    def __init__(self, root):
        self.root = root
        self.children = []
        self.val = 0

    def add_child(self, child_node):
        self.children.append(child_node)
        if self.root is not None:
            self.root.add_child(child_node)

    def calc(self):
        if self.root is not None:
            self.val += self.root.val
        return self.val

nodes = [Node(None)] * n

for i in range(1, n):
    a, b = map(int, input().split())
    a_node = nodes[a - 1]
    nodes[b - 1] = Node(a_node)
    a_node.add_child(nodes[b - 1])

for j in range(q):
    p, x = map(int, input().split())
    node = nodes[p - 1]
    node.val += x

res = []
for node in nodes:
    res.append(str(node.calc()))
print(" ".join(res))

Submission status: Time Limit Exceeded

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

sahen = [0]*n
result = [0]*n

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

j = [[]]*q

for num in range(q):
  a1,b1 = map(int,input().split())
  if (a1 in sahen):
    for num2 in range(a1-1,n):
      result[num2] += b1
  else:
    result[a1-1] += b1

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
a = []
b = []
hens = []
for i in range (n-1):
  t_a, t_b = map(int, input().split())
  a.append(t_a-1)
  b.append(t_b-1)
  hens.append([t_a-1, 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(len(hens) >= 1):
  for hen in hens[:]:
    if tree[hen[0]][2] == True:
      tree[hen[0]][1].append(hen[1])
      tree[hen[1]][0] = hen[0]
      tree[hen[1]][2] = True
    elif tree[hen[1]][2] == True:
      tree[hen[1]][1].append(hen[0])
      tree[hen[0]][0] = hen[1]
      tree[hen[0]][2] = True
    hens.remove(hen)

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 = [x+y for x,y in zip(ans, t_c)]
print(*ans)

Submission status: Time Limit Exceeded

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

tyouten = [list(map(int,input().split())) for _ in range(n-1)]
tree = [list(map(int,input().split())) for _ in range(q)]
ans = [0] * n
temp = [[] for i in range(1,n+1)]
temp2 = [[0] for _ in range(n)]

tyouten.sort()

for i in range(n-1):
    temp[tyouten[i][0]-1].append(tyouten[i][1])

for i in range(q):
    temp2[tree[i][0]-1][0] += tree[i][1]
    
for i in range(n):
    ans[i] += temp2[i][0]
    for j in temp[i]:
        ans[j-1] += ans[i]
    
print(*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 = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

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

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


parent = defaultdict(list)
for i in range(N-1):
    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:
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[list(map(int,input().split())) for i in range(b)]
e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[]for i in range(a)]
n=0
f=[0 for _ in range(a)]
ans=[0 for _ in range(a)]
for i in d:
  ans[i[0]-1]=ans[i[0]-1]+i[1]
i=0
h=[]
while n<a:
  n+=1
  m=float("inf")
  for j,k in enumerate(e[i]):
    if f[i]==k:
      m=j
    else:
      f[k]=i
  if m!=float("inf"):
    e[i].pop(m)
  h=h+e[i]
  for j in e[i]:
    ans[j]+=ans[i]
  if len(h)!=0:
    i=h.pop()



  

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())

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

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

def dfs(v, p):
    for u in edge[v]:
        if u != p:
            imos[u] += imos[v]
            dfs(u, v)

dfs(0, -1)
print(' '.join([str(x) for x in imos]))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split(" "))
A = []
A.append(-1)

B = [0 for j in range(N)]
for i in range(N-1):
    tmp = list(map(int,input().split(" ")))
    A.append(tmp[0])

for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]

for i in range(N):
    ans = 0
    p = i
    while(1):
        ans += B[p]
        p = A[p]-1
        if p <= -1:
            break;
    print(ans,end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200004)
N, Q = map(int, input().split(" "))
cnt = [0] * N
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

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


def dfs(n, prev, cnt):
    for e in edge[n]:
        if e == prev:
            continue
        cnt[e] += cnt[n]
        dfs(e, n, cnt)


dfs(0, -1, cnt)
print(*cnt)

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 nex in edge[cur]:
        if nex != root:
            dfs(nex, c + cost[nex], cur)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200004)
N, Q = map(int, input().split(" "))
cnt = [0] * N
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

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


def dfs(n, prev):
    for e in edge[n]:
        if e == prev:
            continue
        cnt[e] += cnt[n]
        dfs(e, n)


dfs(0, -1)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


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

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

parent = [0] * n
res = [0] * n
visited = [False] * n
def dfs(x, n):
    res[x] += n
    visited[x] = True
    for ne in adj[x]:
        if not visited[ne]:
            dfs(ne, n + p[ne])

dfs(0, p[0])
print(' '.join([str(x) for x in res]))

Submission status: Time Limit Exceeded

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

sahen = [0]*n
result = [0]*n

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

j = [[]]*q

for num in range(q):
  a1,b1 = map(int,input().split())
  if (a1 in sahen):
    for num in range(a1-1,n):
      result[num] += b1
  else:
    result[a1-1] += b1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())

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

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

def dfs(v, p):
    for u in edge[v]:
        if u != p:
            imos[u] += imos[v]
            dfs(u, v)

dfs(0, -1)
print(' '.join([str(x) for x in imos]))

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
memo = {}
for i in lst2:
  start = i[0]
  visited = []
  if (start == 1):
      ans = list(map(lambda x: x + i[1], ans))
  else:
    if start not in memo.keys():
      memo[start] = dfs(dict(tree), start)
    for j in memo[start]:
      if (start <= j):
        ans[j-1] += i[1]
print(" ".join(list(map(str,ans))))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

comp = defaultdict(list)
for i in range(n):
    c = data[i]
    pos = 0
    while pos < len(c):
        c += data[c[pos]]
        pos += 1
    comp[i] = c

score = defaultdict(int)
for i in range(q):
    p, x = list(map(int,input().split()))
    score[p] += x
    for c in comp[p]:
        score[c] += x

scorelist = []
for i in range(n):
    s = str(score[i+1])
    scorelist.append(s)
print(' '.join(scorelist))

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 = sorted([list(map(int, input().split())) for _ in range(N - 1)])
    p_x = sorted([list(map(int, input().split())) for _ in range(Q)])
    score = [0 for _ in range(N)]

    for task in p_x:
        score[task[0] - 1] += task[1]

    
    for leef in a_b:
        score[leef[1] - 1] += score[leef[0] - 1]   

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
for i in range(q):
    p, x = map(int, input().split())
    children = deque([p - 1])
    while children:
        c = children.pop()
        counter[c] += x
        for j in tree[c]:
            children.append(j)
print(*counter)

Submission status: Time Limit Exceeded

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

class Node:
    def __init__(self, root):
        self.root = root
        self.children = []
        self.val = 0

    def add_child(self, child_node):
        self.children.append(child_node)
        if self.root is not None:
            self.root.add_child(child_node)

    def calc(self):
        res = self.val
        curr = self
        while True:
            root = curr.root
            if root is None:
                break
            res += root.val
            curr = root
        return res

nodes = [Node(None)] * n

for i in range(1, n):
    a, b = map(int, input().split())
    a_node = nodes[a - 1]
    nodes[b - 1] = Node(a_node)
    a_node.add_child(nodes[b - 1])

for j in range(q):
    p, x = map(int, input().split())
    node = nodes[p - 1]
    node.val += x
    # children = node.children
    # for child in children:
    #     child.val += x

res = []
for node in nodes:
    res.append(str(node.calc()))
print(" ".join(res))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict

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

q = deque()
ans = [0] * (N+1)

T = defaultdict(list)
for ab in AB:
    a, b = ab
    T[a].append(b)

P = defaultdict(int)
for px in PX:
    p, x = px
    P[p] += x
ans[1] = P[1]

for t in T[1]:
    q.append([1, t])
while q:
    a, b = q.popleft()
    ans[b] += ans[a] + P[b]
    for t in T[b]:
        q.append([b, t])

print(*ans[1:])

Submission status: Time Limit Exceeded

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

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

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

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

for num in range(q):
  inpt =input().split()
  if (int(inpt[0]) in sahen):
    for num in range(int(inpt[0])-1,n):
      result[num] += int(inpt[1])
  else:
    result[int(inpt[0])-1] += int(inpt[1])

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

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
t={i:[] for i in range(1,n+1)}
c=[0 for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    t[a].append(b)

ts={i:[] for i in range(1,n+1)}
for i in range(n,0,-1):
    ts[i].append(i)
    if t[i]!=[]:
        for s in t[i]:
            ts[i].extend(ts[s])

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

print(*c[1:])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}
for i in range(N) :
    dic[i+1] = []

for i in range(N-1) :
    a, b = (int(x) for x in input().split())
    dic[a].append(b)
    for n in dic.keys() :
        if a in dic[n] :
            dic[n].append(b)

SUM = np.zeros(N, dtype=np.int)

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

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

Submission status: Time Limit Exceeded

Solution code:
nodelist=[]
operation=[]

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



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

result=""
for i in range(n):
  result+=str(counter[i])+" "

print(result)

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(x) for x in input().split()]
lines = []
while True:
  try:
    lines.append([int(x) for x in input().split()])
  except:
    break
G = lines[:-Q]
O = lines[-Q:]

Gd = {}
for l in G:
  if l[0] not in Gd:
    Gd[l[0]] = []
  Gd[l[0]].append(l[1])

Od = {}
for l in O:
  if l[0] not in Od:
    Od[l[0]] = []
  Od[l[0]].append(l[1])

counter = {i+1:0 for i in range(N)}
subtrees = {j+1:[] for j in range(N)}
#subtrees[1] = list(range(2, N+1))

def helper(d, i, lst):
  if i not in d:
    return i
  for j in d[i]:
      lst.append(j)
      helper(d, j, lst)
lst = []

for k in range(1, N+1):
  helper(Gd, k, subtrees[k])

for k, v in Od.items():
  counter[k] += sum(v)
  for m in subtrees[k]:
    counter[m] += sum(v)
print(' '.join([str(x) for x in list(counter.values())]))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
graph = {i:[] for i in range(N)}
G = {i:[] for i in range(N)}
ans = [0 for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  graph[a-1] += [b-1]
  graph[b-1] += [a-1]
stuck = [0]
log = [0 for i in range(N)]
log[0]=1
ls = [0]
while stuck:
  x = stuck.pop()
  A = graph[x]
  flag = True
  ki = []
  for a in A:
    if log[a]==0:
      stuck += [a]
      ki+=[a]
      log[a]=1
      flag = False
  for l in ls:
    G[l] += ki
  ls += ki
  if flag:
    ls.remove(x)
for i in range(Q):
  p, x = map(int,input().split())
  p = p-1
  for l in G[p]:
    ans[l] += x
  ans[p] += x
A = map(str, ans)
print(' '.join(A))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
ab=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*(n-1)]
pq=[list(map(int,input().split())) for _ in [0]*q]
for i in range(q):
    pq[i][0]-=1

graph=[[] for _ in [0]*n]
[graph[a].append(b) for a,b in ab if a<b]
[graph[b].append(a) for a,b in ab if a>b]

plus=[0 for _ in [0]*n]
for i,j in pq:
    plus[i]+=j

pos=[]
ans=[0 for _ in [0]*n]
temp=0
q=[0]
memo=[False for _ in [0]*n]

while q:
    i=q.pop(-1)
    if memo[i]==False:
        pos.append(i)
        temp+=plus[i]
        ans[i]=temp
    memo[i]=True

    while graph[i]:
        j=graph[i].pop(-1)
        if memo[j]==False:
            q.append(j)
            break
    else:
        temp-=plus[pos[-1]]
        pos.pop(-1)
        if pos!=[]:
            q.append(pos[-1])
print(*ans)

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 = []
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())
    z[p1] += x1
    bubunki(p1)        


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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
tree = [list(map(int, input().split())) for _ in range(n - 1)]
nums = [list(map(int, input().split())) for _ in range(q)]

#ノード用のクラス定義
class Node:
  def __init__(self, myval, child = None):
    self.myval = myval 
    self.count = 0
    self.childs = []
    if child != None:
      self.childs.append(child)

  def plus(self, num):
    self.count += num
    for child in self.childs:
      child.plus(num)

  def add_child(self, newchild):
    self.childs.append(newchild)
  
  def get_count(self):
    return self.count

tops = []
node_tree = {}

def add_node(c_node):
  name0 = str(c_node[0])
  name1 = str(c_node[1])
  if c_node[0] in tops  and c_node[1] in tops:
    node_tree[name0].add_child(node_tree[name1]) 
  elif c_node[0] in tops:
    new_node = Node(c_node[1])
    node_tree[name0].add_child(new_node)
    tops.append(c_node[1])
    node_tree[name1] = new_node
  else:
    new_node1 = Node(c_node[1])
    new_node0 = Node(c_node[0], new_node1)
    tops.append(c_node[0])
    tops.append(c_node[1])
    node_tree[name0] = new_node0
    node_tree[name1] = new_node1


for node in tree:
  add_node(node)

for num in nums:
  node_name = str(num[0])
  node_tree[node_name].plus(num[1])

tops.sort()
out = ''
for i in tops:
  out += (str(node_tree[str(i)].get_count()) + ' ')

print(out[:-1])

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)

for v in repn[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
            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]



## 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())
tree = {}
ans = {}
sum = 0

for _ in range(N-1):
  pare, kid = map(int, input().split())
  tree[kid] = pare

for _ in range(Q):
  p, x = map(int, input().split())
  if p in ans.keys():
    ans[p] += x
  else:
    ans[p] = x
for i in range(1, N + 1):
  temp = i
  while True:
    try:
      sum += ans[temp]
    except KeyError:
        pass
    if temp == 1:
      break
    else:
      temp = tree[temp]

  print(sum)
  sum = 0

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(1000000)

MAX_N = 100010
memo = children = [set() for i in range(MAX_N)]


def all_children(node_no, direct_children_list, memo):
    res = set([])

    if len(memo[node_no]) != 0:
        # print(str(node_no) + " " + str(res) + " | " + " ".join(list(map(str, memo[0:len(direct_children_list):]))))
        return set(memo[node_no])

    direct_children = direct_children_list[node_no]
    if len(direct_children) == 0:
        res = set([node_no])
        memo[node_no] = res
        # print(str(node_no) + " " + str(res) + " | " + " ".join(list(map(str, memo[0:len(direct_children_list):]))))
        return res

    for child in direct_children:
        res = res | set([child]) | all_children(child, direct_children_list, memo)
    res = res | set([node_no])
    memo[node_no] = res
    # print(str(node_no) + " " + str(res) + " | " + " ".join(list(map(str, memo[0:len(direct_children_list):]))))
    # print("")
    return res


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, memo)
    # 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:
#!/usr/bin/env python3

def a(index, point0):
    if len(dict[index][0]) == 0:
        dict[index][1] += point0
        return
    else:
        dict[index][1] += point0
        for j in dict[index][0]:
            a(j, point0)

nq = list(map(int, input().split(" ")))
n = nq[0]
q = nq[1]

branch = []
dict = {1 : [[], 0]}
for i in range(n - 1):
    branch.append(list(map(int, input().split(" "))))
    dict[i + 2] = [[], 0]

point = []
for i in range(q):
    point.append(list(map(int, input().split(" "))))

route = [[]] * (n + 1)

for w in branch:
    route[w[1]] = route[w[0]] + [w[1]]
    dict[w[0]][0].append(w[1])

for c in point:
    a(c[0], c[1])


list = []
for i in range(1, n + 1):
    list.append(str(dict[i][1]))

print(" ".join(list))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import defaultdict
import sys,time

d = defaultdict(list)

n, q = map(int, input().split())
ans = [0]*n

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

for i in range(q):
    p, x = map(int, input().split())
    #print(p, x)
    queue = [p]
    while True:
        #print("queue", queue)
        index = queue.pop(0)
        ans[index-1] += x
        tmp_list = d[index]
        if len(tmp_list) != 0:
            #print("tmp_list", tmp_list)
            #print("ans", ans)
            queue.extend(tmp_list)
                #print(ans)
        if len(queue) == 0:
            break
        #print(ans)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

n,q = map(int, input().split())
child = defaultdict(list)
parent = defaultdict(int)
query = defaultdict(int)
for _ in range(n - 1):
	a, b = map(int, input().split())
	child[a].append(b)
	parent[b] = a
for _ in range(q):
	a, b = map(int, input().split())
	query[a] += b
ans = [-1 for _ in range(n)]
for i in range(1, n + 1):
	if parent[i] == 0:
		break
l = [i]
while l != []:
	i = l[0]
	ans[i - 1] = query[i]
	if child[i] != []:
 		for x in child[i]:
 			query[x] += query[i]
 			l.append(x)
	l.pop(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
for i in range(q):
    children = queue.Queue()
    p, x = map(int, input().split())
    children.put(p - 1)
    while not children.empty():
        c = children.get()
        counter[c] += x
        for j in tree[c]:
            children.put(j)
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
tree = [[int(i) for i in input().split()] for i in range(n-1)] 
px = [[int(i) for i in input().split()] for i in range(q)] 
calc_tree = []

for i in range(n):
  tmp = [i+1]
  for j in range(n-1):
    if tree[j][0] in tmp:
      tmp.append(tree[j][1])
  calc_tree.append(tmp)
#print(calc_tree)
ans = [0] * n
  
for i in range(q):
  order = px[i][0] -1
  for j in calc_tree[order]:
    ans[j-1] += px[i][1]
    
for i in ans:
  print(i,end=' ')