BOJ 14267会社文化1

https://www.acmicpc.net/problem/14267
2秒、512 MBメモリ
input :

n m (2 ≤ n, m ≤ 100,000)

nトップ上司の電話番号(トップ上司の電話番号は自分の電話番号より小さく、1番は社長)

i w (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)

output :

1号からn号までの従業員の表彰程度は

である.
条件:

上司はトップの上司を褒めて、彼の部下のすべての部下は褒められます.

Ye Jaeが「2 2」と入力すると、2,3,4はいずれも2の称賛を得る.
「5 6」の場合は5万6の称賛を受ける.
最も問題になっている部分は、称賛をどのように計算するかです.

入力を受け取るたびに計算
そうすると、そのノードからleafノードまで計算する必要がありますが、m行を入力する前にこの検索を続けると、時間が足りません.

きろく
これは問題を解決する人が推薦する方法です.まず各ノードの称賛を記録し,最後にBFS,DFS,巡回などを用いて追加する.

問題の条件の下で、上司の番号は自分より小さいので、上司たちは親のノードになりました.最終的には、ツリー構造の例が表示されます.
したがって、図のようなリストを作成して、ノードに関連付けられたノードを格納します.
rootはもちろんボス(1番ノード)です.
ノードに遭遇した場合、ansリストを更新する必要があります.しかし、qにコストを格納するのではなく、for文でans[next node]=ans[node]+value[next node]と同じ方法を使用することができます.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
parent = [0] + list(map(int, sys.stdin.readline().split()))
ans, graph, value = [0] * (n + 1), [[] for _ in range(n + 1)], dict()

for i in range(2, n + 1):
    graph[parent[i]].append(i)

for _ in range(m):
    i, w = map(int, sys.stdin.readline().split())

    if i not in value:
        value[i] = w
    else:
        value[i] += w

q = deque([(0, 1)])
while q:
    cost, node = q.popleft()
    ans[node] = cost

    for next_node in graph[node]:
        temp = 0

        if next_node in value:
            temp += value[next_node]
        q.append((cost + temp, next_node))

print(*ans[1:])