考察過程

13:14 から

(本番はあまり考えずかつ分からず、一筆書きというヒントは見た)

  • 適当に辺を足して準オイラー路を作ればよい。使うべき辺の全体は木なので連結性は明らか
  • 準オイラーグラフにするため辺の数は自明でない。star graph であって、追加できる辺の集合が元のグラフに一致しているものなどが例
  • 奇数次の頂点を潰していきたい。二部マッチングあるいはフローぽい
  • 奇数次の頂点から奇数次の頂点へ長さ $1$ 以上のできるだけ短いフローを流す感じのやつ。最小費用流ぽいけど、自明な流れ方を防ぐのが面倒そう
  • 頂点を $2$ 重にして流量も $2$ 倍にするといける気がするが、本当か？
  • 最小費用流を primal dual でやると $O(V^2 E F)$ とかで全然間に合わなさそうですが

(分からないので追加ヒント: 木DP)

  • マッチングが見えてもうフローしか考えてなかったな。木DPなるほど
  • 元々の木の側でやると状態が爆発しそう。追加する側の木の上でやりたい
  • 追加する側の辺の集合が木であることを使ってないなと思ってたんだよな
  • 根を適当に固定し、$\mathrm{f}(x, k)$ を、頂点 $x$ による部分木であってその中に奇数次の頂点 $k \in 3$ 個使わずに残すような場合のコストの最小値とする
  • いくつ経路が開いているか $l \in 2$ は、部分木中の奇数次の頂点の個数の偶奇から一意に定まるので状態に持つ必要はない
  • 計算量は $O(N)$ ぽい

メモ

  • 「一筆書き」「木DP」って言われたら自明なのに両方まったく出せなかった
  • きれいな問題設定、それはそうなのに何故か解けない難易度、実装も軽い、好き

リンク