考察
outdegree 1 の functional graph の各弱連結成分は、唯一の有向cycleと、そこへ流れ込むreverse treesからなる。cycle上の頂点からはcycle長 c 個すべてへ到達し、tree頂点uからはcycle c 個に加えてcycleまでのpath上の depth(u) 個へ到達する。Kahn法でindegree0を順に除いた後に残る頂点はcycle頂点だけで、各cycleを一周して同じ長さを全頂点へ設定できる。cycleからreverse graphを外向きにたどると、子uのreachable数は親a_uの値+1となり、共有suffixを一度だけ再利用できる。
採用する候補: indegree削除またはSCCでcycleを特定し、cycle長を基底値としてreverse edge方向へ到達数+1を伝播する。
各頂点・辺を定数回だけ処理し、全uのreachable countを O(N) で得て合計できる。
棄却する候補: 各始点uからa_iを辿り、最初の重複まで訪問数を数える。
長いtailを多数の始点が共有する場合、同じsuffixを繰り返し歩いて O(N²) になる。
全indegreeとreverse adjacencyを作り、queueでindegree0頂点を削除し順序を保存する。残存未訪問頂点ごとにcycleを列挙して長さ c をansCountへ代入する。削除順を逆にたどり count[u]=count[a_u]+1 とし、全 count を64 bitで合計する。
典型の発動条件
functional graph のcycle peeling
発動条件: 各頂点の遷移先が一意で、cycleと流入木を分離したいとき。
indegree0から除去し、残存部分をcycle、除去逆順をtree DP順とする。
共有suffixのDP
発動条件: 各始点の一意な遷移列が途中から合流し、到達数を全点で求めるとき。
次頂点の答え+1を逆topological順に伝える。
問題固有の要素
到達可能数はcomponent全体サイズではなく「自分からcycleまでのdepth+cycle長」で、reverse subtreeの兄弟へは到達しない。
別の問題へ持ち帰る視点: functional graphではundirected componentとdirected reachable setを混同せず、tailとcycleへ分ける。
正当性
cycle点の到達集合はcycle全体。木頂点uは自身と後継の到達集合で、自身は後継から戻れないためcount[u]=count[A_u]+1。削除逆順なら後継が先に計算され、全到達pairを始点ごとの和でちょうど一度数える。
実装上の注意
- self-loopもcycle長1として扱う。答えは最大N²なので64 bitを使い、peel順を逆にしないまま更新しない。
復習の核
- 一成分をcycleと逆向き木に描き、どの頂点へは到達しないかも確認する。peeling後の残存条件と逆順DPをセットで覚える。
計算量と制約
時間
N 頂点に対して O(N)。
空間
出辺、入次数、削除順とcount O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 1 \leq a_i \leq N; All input values are integers.
出典