Official

Ex - Optimal Path Decomposition Editorial by cn449


答えについて二分探索をします。以下、元の問題の答えが \(K\) 以下になるか?という判定問題を考えます。

適当に根を取り木を根付き木とし、木 dp を行います。\(dp_v\)\(v\) を根とする部分木内のどのパスにおいてもパス内に塗られている色の種類数が \(K\) 以下にすることができるならばそのような制約を課した上で、 \(v\)\(v\) の子孫を結ぶ単純パスのうち、そのパス内の頂点に塗られている色の種類数の最大値を最小化した値で定義します。また、\(f_v\) を前述の値を最小化したときに \(v\) の子であって \(v\) と同じ色で塗られた頂点が \(2\) つ存在する(すなわち、\(v\) の親を \(v\) と同じ色で塗ることができない)ときに \(f_v = 1\)、そうでないときに \(f_v = 0\) で定義します。

\(v\)\(v\) の子孫を結ぶ単純パス内の頂点に塗られている色の種類数の最大値を増加させ、 \(v\) の親を \(v\) と同じ色に塗れるようにすることで単純パス上の色の種類数の最大値を減少させることはありません。

よって考慮するべき状態は \(v\)\(v\) の子孫を結ぶ単純パス内の頂点に塗られている色の種類数の最大値が \(dp_v\) であって、\(f_v = 0\) ならば \(v\) の親を \(v\) と同じ色に塗ることができ、\(f_v = 1\) ならばできないようなものに限ります。

以下、dp の遷移を考えます。
\(v\) の子であって \(f_w = 0\) をみたす \(w\) について \(dp_w\) を降順に並べた数列を \(X\)\(v\) の子であって \(f_w = 1\) をみたす \(w\) について \(dp_w\) を降順に並べた数列を \(Y\) と定義します。また、数列 \(X\) の長さを \(x\)\(Y\) の長さを \(y\) とします。 頂点 \(v\) を取ったときに、\(v\) の子であって \(v\) と同じ色に塗られる頂点は高々 \(2\) 個であるため、以下の \(3\) 通りに場合分けします。

  • 選択肢 \(1\) : \(v\) の子であって \(v\) と同じ色に塗られる頂点が存在しない
  • 選択肢 \(2\) : \(v\) の子であって \(v\) と同じ色に塗られる頂点が \(1\) つ存在する
  • 選択肢 \(3\) : \(v\) の子であって \(v\) と同じ色に塗られる頂点が \(2\) つ存在する

答えが \(K\) 以下という条件のもとで許容される選択肢内での最適解を考えます。

まず、\(x = 0\) のときは明らかに選択肢 \(1\) しか選ぶことができません。一方、\(x \neq 0\) のときは選択肢 \(1\) を選ぶかわりに選択肢 \(2\) を選ぶとしても状況が悪化することはないので選択肢 \(2\) と選択肢 \(3\) の比較に帰着されました。

\(v\) と同じ色に塗る \(v\) の子 \(w\)\(dp_w\) が大きいものから選んでいくのが最適であるため、選択肢 \(2\) を選ぶと \(dp_v = \max (X_1,X_2+1,Y_1+1)\)、選択肢 \(3\) を選ぶと \(dp_v = \max(X_1,X_3+1,Y_1+1)\) です。(\(X\)\(Y\) の長さが足りない場合がありますが、その場合 \(\max\) を取る対象から外します)

選択肢 \(3\) を選ぶべき状況について整理します。
まず、明らかに \(x \geq 2\) は必要なので以下 \(x \geq 2\) とします。
数列 \(C\)\((X_1 - 1, X_2, \ldots, X_x, Y_1, \ldots, Y_y)\) を降順に並べ替えたもの、数列 \(D\)\((X_1 - 1, X_2- 1, \ldots, X_x, Y_1, \ldots, Y_y)\) を降順に並べ替えたものとします。
選択肢 \(2\) を選ぶと答えが \(C_1 + C_2 + 1\) 以上となることが確定し、選択肢 \(3\) を選ぶと答えが \(D_1 + D_2 + 1\) 以上となることが確定します。
ここで \(C_1 + C_2 + 1\geq D_1 + D_2 + 1\) であるため、\(\max (X_1,X_2+1,Y_1+1) > \max(X_1,X_3+1,Y_1+1)\) をみたすとき、あるいは \(C_1 + C_2 + 1 > K\) をみたすときに限り選択肢 \(3\) を選ぶとしてよいです。

以上より判定問題を解くことができました。

上の議論では説明の簡略化のために数列を sort しましたが、数列は実際には sort する必要がなく大きいものから定数個取ればよいので判定問題は \(O(N)\) で解くことができ、HL 分解を考えることで答えは \(O(\log N)\) で抑えられるので時間計算量 \(O(N \log \log N)\) でこの問題を解くことができました。

posted:
last update: