Problem p02936 (python)

Fixed submission:
n, q = map(int, input().split())

# 各ノードのリンクを記録
link_set = [set() for _ in range(n-1)]
for i in range(n-1):
  a, b = map(int, input().split())
  link_set[a - 1].add(b)

# カウンターの計算を実施 (O(QN)の計算を避けることがポイント)

## O(Q)の計算
counters = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  counters[p - 1] += x
  
## O(N)の計算
for i in range(n - 1):
  for node in link_set[i]:
    counters[node - 1] += counters[i]

str_counters = [str(c) for c in counters]
print(' '.join(str_counters))

Buggy submission (verdict: Runtime Error):
n, q = map(int, input().split())

# 各ノードのリンクを記録
link_dict = dict()
keys = []
for i in range(n-1):
  a,b = map(int, input().split())
  if a in keys:
    link_dict[str(a-1)].add(b)
  else:
    keys.append(a)
    link_dict[str(a-1)] = {b}
  
# 各ノードの部分木の全てのノードをリストアップ
link_set = [set() for i in range(n-1)]
for i in sorted(keys, reverse=True):
  link_set[int(i) - 1] = set(link_dict[str(i-1)])
  if int(i) < n - 1:
    for j in link_dict[str(int(i) - 1)]:
      if j < n - 1:
        link_set[i - 1] = link_set[i - 1] | link_set[j - 1]

# カウンターの計算を実施
counters = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  counters[p - 1] += x
  for node in link_set[p - 1]:
    counters[node - 1] += x
str_counters = [str(c) for c in counters]
print(' '.join(str_counters))

Buggy submission (verdict: Runtime Error):
n, q = map(int, input().split())

# 各ノードのリンクを記録
link_dict = dict()
for i in rage(n-1):
  a,b = map(int, input().split())
  if a in list(link_dict.keys()):
    link_dict(str(a-1)).add(b)
  else:
    link_dict(str(a-1)) = set(b)
  
# 各ノードの部分木の全てのノードをリストアップ
link_set = [set() for i in range(n-1)]
for i in list(link_dict.keys()).sort():
  link_set[int(i) - 1] = set(link_dict[i - 1])
  if int(i) < n - 1:
    for j in link_dict[str(int(i) - 1)]:
      if j < n - 1:
        link_set[i - 1] = link_set[i - 1] | link_set[j - 1]

# カウンターの計算を実施
counters = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  counters[p - 1] += x
  for node in link_set[p - 1]:
    counters[node - 1] += x
str_counters = [str(c) for c in counters]
print(' '.join(str_counters))

Buggy submission (verdict: Runtime Error):
n, q = map(int, input().split())

# 各ノードのリンクを記録
link_list = [[] for i in range(n-1)]
for i in range(n-1):
  a, b = map(int, input().split())
  link_list[a - 1].append(b)
  
# 各ノードの部分木の全てのノードをリストアップ
link_set = [set() for i in range(n-1)]
for i in range(n-1, 0, -1):
  link_set[i - 1] = set(link_list[i - 1])
  if i < n-1:
    for j in link_list[i - 1]:
      if j < n - 1:
        link_set[i - 1] = link_set[i - 1] | link_set[j - 1]

# カウンターの計算を実施
counters = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  counters[p - 1] += x
  for node in link_set[p - 1]:
    counters[node - 1] += x
str_counters = [str(c) for c in counters]
print(' '.join(str_counters))

Buggy submission (verdict: Runtime Error):
n, q = map(int, input().split())

# 各ノードのリンクを記録
link_list = [[] for i in range(n-1)]
for i in range(n-1):
  a, b = map(int, input().split())
  link_list[a - 1].append(b)
  
# 各ノードの部分木の全てのノードをリストアップ
link_list2 = [[] for i in range(n-1)]
for i in range(n-1, 0, -1):
  link_list2[i - 1] += link_list[i - 1]
  if i < n-1:
    for j in link_list[i - 1]:
      if j < n - 1:
        link_list2[i - 1] += link_list2[j - 1]
link_set = [set(link) for link in link_list2]

# カウンターの計算を実施
counters = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  counters[p - 1] += x
  for node in link_set[p - 1]:
    counters[node - 1] += x
str_counters = [str(c) for c in counters]
print(' '.join(str_counters))