ABC 378 F — Add One Edge 2

考察

木に辺を1本追加すると、その両端点を結ぶ元の木上の道と追加辺で閉路ができる。次数が1増えるのは追加辺の両端点だけで、道の内部頂点の次数は変わらない。したがって、閉路上の全頂点の次数を3にするには、元の木で端点の次数が2、内部頂点の次数が3であればよい。

例えば公式入力例1の木は、辺1–2、2–3、3–4、4–5、3–6からなる。ここへ辺2–4を追加すると、元の道2–3–4と追加辺で閉路ができる。端点2と4の次数は2から3へ増え、内部頂点3の次数は3のままなので、閉路の3頂点は全て次数3になる。

端点から一歩以上の次数3連鎖を通って到達する次数2頂点数を各子方向ごとに持つと、現在頂点を内部に含むpathは異なる二方向の積で数えられる。現在頂点が次数2なら端点候補として上へ1を返し、次数3なら子からの候補を合算し、それ以外の次数では伝播を止める。

採用する候補: 木を根付き化し、次数3の頂点だけを伝播路として、各子方向から到達できる次数2端点数をbottom-upに集計して異なる方向の組を数える。

数える対象を次数列が制限された単純pathへ言い換えると、頂点ごとの子方向の集約だけで各pathを一度だけ数え、O(N)の木DPにできる。

棄却する候補: 追加する頂点対を全て試し、できた cycle 上の次数を確認する。

頂点対が Θ(N^2) あり、path 確認を加えるとさらに重くなる。

任意根でDFSし、a_vを「vが次数2ならその1頂点、次数3なら子方向から次数3だけを内部にして到達できる次数2端点数」とする。deg(v)=2では、最初の内部頂点を必ず1個含めるためdeg(child)=3のchildについてだけΣa_childを答えへ加え、a_v=1とする。deg(v)=3ではΣ_{i<j}a_i a_jを加えてa_v=Σa_iとし、それ以外はa_v=0とする。

典型の発動条件

次数条件で伝播を切り替える木DP

発動条件: 端点と内部で異なる頂点条件を満たす木上pathを数えるとき。

次数3だけを通る端点候補数を子から集約し、現在頂点の次数に応じて組の加算と親への返値を切り替える。

問題固有の要素

追加後の cycle 条件を元の木上の path の次数列へ翻訳すると、辺追加を試す必要がなくなる。

別の問題へ持ち帰る視点: 内部条件を満たす連鎖だけを DP 値として親へ渡し、壊れた時点で0にする。

正当性

閉路は元の木の端点間の道と追加辺からなる。端点の次数だけ1増え、内部頂点の次数は変わらないので、端点は元次数2、内部は元次数3が必要十分。道を最高点で分類すると異子方向の結合と上端自身の場合に一意分解される。次数2端点同士の隣接を除くことで3頂点以上の閉路だけを数える。

実装上の注意

  • pathは3頂点以上なので端点同士が隣接するケースを除く。各pathは根付き木上の最高点または上側端点で一度だけ数え、親方向とのpairを同じ頂点で重ねて数えない。

復習の核

  • 木への辺追加でできる閉路を、元の木で両端点を結ぶ道と追加辺に分けて考える。次数が増えるのは追加辺の両端点だけなので、端点は元次数2から3へ、内部頂点は元次数3のまま、という条件を自力で導く。
  • 端点同士が隣接していると既存の辺を重ねてしまう。単純グラフの条件から、数える道は内部頂点を1個以上含むものに限る。

計算量と制約

時間

N 頂点。子候補の和と積和を一回ずつ更新して O(N)。

空間

木と各頂点の端点候補数で O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 2 \times 10^5; 1 \leq u_i, v_i \leq N; The given graph is a tree.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Add One Edge 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 根付き木DP・部分木集約

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 根付き木DP・部分木集約

      執筆: abc-explanation-author1.1.1 / revision 3

      学習の位置

      体系上の位置: 根付き木DP・部分木集約

      • 根付き木で子側の状態を合成し、部分木または木全体の値を求められる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題