読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CSAcademy Special MVC

editorial読んで概要はすぐに理解できたけど、cactus上のDPを整理するのに手間取った。この回難しすぎる。

https://csacademy.com/contest/archive/#task/special-mvc/

解法

奇数長のサイクルしかないという条件から、すべての二重頂点連結成分は橋またはサイクルになる。このようなグラフは cactus と呼ばれている。

Cactus graph - Wikipedia

二重頂点連結成分分解したあとのグラフは木のようになっており、さらに各成分は橋かサイクルなのでDPができる。

二重頂点連結成分分解書いたけど、多分いらない。