ABC 385 E — Snowflake Tree

考察

中心uと第一層の頂点数xを固定すると、全第一層へ同じ数yの葉を付ける必要があり、yは選んだ隣接頂点の最小(deg(v)-1)で決まる。

同じxならこの最小値を最大化するには、uの隣接頂点を次数の大きい順に上位x個選べばよい。

採用する候補: 各中心の隣接次数を降順sortし、prefix個数xを全探索する

棄却する候補: 削除する頂点集合をsubset全探索する

N=3×10^5で組合せは指数的であり、snowflake構造が次数だけで決まる性質を使えていない。

全頂点uについて隣接頂点のdegを降順に並べる。x=1..deg(u)を走査し、y=sortedDeg[x-1]-1として1+x+xyの最大を更新し、Nから引く。

典型の発動条件

bottleneck最大化のsort prefix

発動条件: x個選んだ価値が選択集合の最小keyで決まるとき。

key上位x個を選び、xごとの最小を末尾要素として評価する。

木の次数による局所構造評価

発動条件: 部分木の形が中心と隣接頂点の次数だけで決まるとき。

中心候補ごとに二層snowflakeの最大サイズを数える。

問題固有の要素

どの葉を残すかは個別に選ばなくても、木なので第一層vには中心以外のdeg(v)-1隣接点を自由に葉として残せる。

別の問題へ持ち帰る視点: 木から固定深さ・一様分岐構造を残す問題では、cycle干渉がないため局所次数のorder statisticsへ帰着できる。

正当性

第一層v自身が中心との辺を一本使うため、葉数候補はdeg(v)-1である。 最大残存頂点数を求めれば、必要削除数はNから引くだけである。 x番目の次数dがbottleneckとなり、残せる頂点数1+x+x(d-1)を各候補で直接評価でき、全隣接sortの合計O(N log N)で済む。

実装上の注意

  • deg(v)-1=0も評価可能で、公式の同値変形により別途除外不要。式1+x+x*yと答えの引き算は整数型で行う。

復習の核

  • path、star、全隣接次数が同じ木を手計算し、x=1とx=deg(u)、y=0相当の扱いを確認する。

計算量と制約

時間

O(N log N)、各頂点の隣接degree sortの合計≤O(N log N)。

空間

O(N)。

制約との対応

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

出典

分類・前提・執筆情報

掲載状態: 収録済み

Snowflake Tree の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

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

      主タグ: 貪欲法と交換論

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

      学習の位置

      体系上の位置: 交換論から選択順を導く

      • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

      この解説で扱わないこと:

      • 対称操作による状態の正規化。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題