Codeforces Wunder Fund Round 2016 D. Hamiltonian Spanning Tree

方針はすぐに思いついたけど上手く書けなかった。

codeforces.com

解法

x ≧ y のとき
できるだけ全域木以外の辺を使うのが最適。

スターグラフでなければ全域木以外の辺を用いてハミルトンパスを作れるが、スターグラフのときは全域木の辺を 1 本使わなければならない。

x < y のとき
できるだけ全域木の辺を使うのが最適。

これは木の最小パス被覆問題と考える事ができる。 最小パス被覆問題は貪欲法で解けるらしいが、この解説では木 DP の方を説明する。

使う DP テーブルは次の 2 つ。

  • dp0[ 頂点 v ] := v の部分木内で使う辺の本数の最大値。ただし v に接続している辺の総数がたかだか 1
  • dp1[ 頂点 v ] := v の部分木内で使う辺の本数の最大値。ただし v に接続している辺の総数がたかだか 2

dp0 の更新

v に接続している辺がたかだか 1 であるような状態は次の 2 つ。

f:id:pekempey:20160131182814p:plain:w200 f:id:pekempey:20160131182819p:plain:w200

右側のケースで v と繋ぐべき最大の子は、dp0 - dp1 が最も大きい頂点。ゆえに dp0 の更新式は次のようになる。

$$ dp 0[ v ] = \max(S, S + d_1 + 1) $$

ただし $S = \sum_{u \in \mathrm{ch}(v)} dp 1[u] $、d1 は dp0[u] - dp1[u] の最大値とする。

dp1 の更新

v に接続している辺がたかだか 2 であるような状態は、上の 2 つに加えて次の状態もある。

f:id:pekempey:20160131182824p:plain:w250

v と繋ぐべき最大の子は、dp0 - dp1 が1番目に大きい頂点と 2 番目に大きい頂点。ゆえに dp1 の更新式は次のようになる。

$$ dp 1[ v ] = \max(S, S+d_1 + 1, S + d_1 + d_2 + 2) $$

ただし $S = \sum_{u \in \mathrm{ch}(v)} dp 1[u] $、d1 と d2 は dp0[u] - dp1[u] の最大値と 2 番目の最大値とする。


Codeforces Wunder Fund Round 2016 D. Hamiltonian S ...

本番中はパスの個数の最小値で DP してバグらせていたのだが、使う辺の本数の最大値で DP したらすんなり書けた。