二乗の木 DP を応用したもの。このセットの運営チームだった。 問題へのリンク editorial 北大アーカイブ 問題概要 頂点からなる木が与えられる。 この木の 個の空でない部分グラフの組であって、各部分グラフがいずれも連結で、どの二つの相異なる部分グラ…

めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…

二乗の木 DP のいい練習問題！！！！！ ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…

二乗の木 DP の例題として、すごくいい感じ！！！ 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…

すごく典型的な「二乗の木 DP」！！！！！ そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…

「TDPC うなぎ」の類題。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。ツリー上の「頂点を共有しないようなパスの集合」として考えられるもののうち、パスの重みの総和の最大値を求めよ。 制約 考えたこと ツリー二重 DP をする。 ツリー DP…

二乗の木DPの問題にようやく出会えました！ 問題へのリンク 問題概要 頂点のツリーがあって、各頂点には値 が割り振られている。今ツリーのエッジを何本か取り除いて何個かの連結成分に分けたとき 連結成分内に含まれる全ノードの頂点の重みの和が負の値 連…