https://codeforces.com/contest/2165/problem/E
$N$ 頂点の木が与えられる。
$k=1,2,\dots,N-1$ について、以下の問題に答えよ。
- 木の各辺を色 $1,2,\dots,k$ で塗り分けることを考える。ただし、全ての色を少なくとも $1$ 度は使わなければならない。
- $f(u,v) = $ $u$ から $v$ へのパス上に塗られた色の種類数と定義する。
- 塗り分けの 不便さ を $\displaystyle \max_{1 \le u,v \le N} f(u,v)$ と定義する。
- 達成可能な不便さの 最小値 を求めよ。
$3 \le N \le 3 \times 10^5$
公式解説ベースで、自分が分からないところを補間しながらまとめます。
取り扱いやすいように、本問題の key と value を入れ替える。即ち、不便さが $l$ 以内となるような塗り分けで最大何色使えるかを考える。
まず、次の主張を確認します。
最適な塗り分けにおいて、各色の辺だけ見た時、色ごとに $1$ つの連結成分を成す。
色 $c$ に非連結な複数の成分があったとします。このとき、最も「外側」(厳密には、色 $c$ で補助木を考えた時の葉にあたる成分) の連結成分 $X$ に対して次が成り立ちます。
- 連結成分 $X$ から他の色 $c$ の連結成分 $Y$ に向かう時に最初に通る辺の色を $d$ とする。このとき、 $X$ 全体を色 $d$ で塗っても不便さは大きくならない。
以下の図だと、丸を付けた色 $1$ の連結成分全体を色 $4$ で塗ることに相当します。
丸を付けられた方の色 $1$ の連結成分が $X$ 、そうでない色 $1$ の連結成分が $Y$ です。
- 元から $X$ も $Y$ も通らないパス
- 何も起こらない。
- 元から $Y$ のみを通るパス
- 何も起こらない。
- 元から $X$ のみを通るパス
- $Y$ を根と考える。
- $X$ の子から $X$ に入り、 $X$ の子に向かって出ていく場合
- この場合、パス中で $X$ が唯一の色 $1$ の連結成分である。
- この場合、色 $1$ の役割が色 $4$ に変わるだけなので、この塗り替えで不便さは大きくならない。
- $X$ の親から $X$ に入り、 $X$ の子に向かって出ていく場合
- この場合、 $X$ に入る時に色 $4$ の辺を通ることになるので、この塗り替えで不便さは大きくならない。
- 元から $X$ も $Y$ も通るパス
- $X,Y$ 間の移動において色 $4$ の辺を通ることになるので、この塗り替えで不便さは大きくならない。
この塗り替えを繰り返していくことで、各色が $1$ つの連結成分を成すまで変形していけるので、題意が示されました。
ところで、この問題では、木の直径のようなものを訊いています。なので、木の中心のような量を考えることが筋良です。参考 類題
不便さの最大値を $d$ と置く。このとき、実際に $d$ を達成するパスに着目することで、以下が発見できます。これ以降、これらを 核 と呼びます。
- $d$ が奇数であるとき、核は辺である。
- 核から全ての葉に向かう際に通る色の種類数が $(d-1)/2$ 以下である。
- $d$ が偶数であるとき、核は頂点である。
- 核から全ての葉に向かう際に通る色の種類数が $d/2$ 以下である。
引用: 公式解説の図
この核を使って、次の事項を証明します。
- 核からの色数の条件を満たす塗り分けを考える。
- ある葉から核に向かうパスについて、色が $a-b-c-c-d-e-\dots$ のようになっている(葉から辿って行って、色の境界が葉から始めて連続で発生していない)部分がある。この時、このパスの色を $a-b-c-d-d-e-\dots$ のように変更して使える色数が減ることはない。
- より端的には、色の境界を核から葉の方向に押しても損しない。
この図を見てもらうとわかりやすいが、部分木中の数字はその部分木で残り使える色の種類数を表す。確かに、境界を葉に向かって押した場合が押さなかった場合の上位互換となっていることが分かる。
あとは、部分木中で新たに適切に新色を導入すれば得できる。
これを、このような操作ができる限り繰り返せば良いことになる。
ここまでの議論をまとめると、
- 核は存在せざるを得ない。
- 核があるとき、色の境界を核から葉に向かって押せるだけ押すのが最適である。
ここから、許されている不便さの最大値 $d$ の偶奇別に、以下の最適な構築ができる。
- $d$ が奇数であるとき
- 核は辺である。
- 核が存在せざるを得ないので、核から葉に向かって最大 $(d-1)/2$ 色しか使うことが出来ない。
- このもとで、可能な限り葉に向かって色の境界を押すことを考える。
- すると、以下の手順で塗り分けることが最適となる。
- 以下を $(d-1)/2$ 回繰り返す。
- 現在の木の葉に繋がる辺を異なる色で塗り分ける。その後、それらの葉と辺を取り除く。
- 残り使えるのはパス当たり $1$ 色なので、残った辺が全て核である。
- 以下を $(d-1)/2$ 回繰り返す。
- $d$ が偶数であるとき
- 核は頂点である。
- 核が存在せざるを得ないので、核から葉に向かって最大 $d/2$ 色しか使うことが出来ない。
- このもとで、可能な限り葉に向かって色の境界を押すことを考える。
- すると、以下の手順で塗り分けることが最適となる。
- 以下を $(d/2)-1$ 回繰り返す。
- 現在の木の葉に繋がる辺を異なる色で塗り分ける。その後、それらの葉と辺を取り除く。
- 残り使えるのはパス当たり $2$ 色である。
- なので、残った頂点のうち現時点での次数が最大のものを核とし、その頂点周りの辺およびそこから伸びる連結成分を全て異なる色で塗れば最適である。
- 以下を $(d/2)-1$ 回繰り返す。
引用: 公式解説の図 再掲
https://codeforces.com/contest/2165/submission/349759306
公式解説だけでは解法の正当性が腑に落ちなかったのでメモ。
自力でも葉のレイヤを求めるみたいなことには辿り着けてサンプルは通ってたんだけど、通し切るまでもう一段かかるなぁという印象。
2 h 6 問の 5 問目だから落として許されてるところあるけど、 3 h だったら通したい問題ですね...
