AGC001 C - Shorten Diameter - gratan’s diary

新環境になってWordにためてた精進記録が取れなくなったのでブログで代用

これからは単発も上げるわ（虚空に向けて）

問題：n頂点の木が与えられる。頂点を削除して直径をk以下にせよ。最小頂点数を求めよ

考察：

いろいろ考えると簡単には求まらないことがわかります。

根付き木に帰着して木DPをします。

いつも思うんですけどDPが生えるときって、あんまり論理的に考えていない気がします。経験上DPっぽい、みたいな程度になってますね。

さて、どういうDPをするかです。

dp[i][j]：iの部分木で、ｉの親から葉の距離がｊ以下になるために、削除する頂点の最小数

こんな感じです。

迷うところは、距離ｊ以下か削除する頂点ｘだと思います。マージするとき明らかに前者のほうが便利なのでそうしました。

木ＤＰなのでdfsして根付き木を構築しながらDPをします。

二乗の木DPなので計算量はO(N^2)です

repr(i,child[v],-1){

repr(j,child[u],-1){

マージする

}}

child[v]+=child[u];

大体こんな感じです。childで抑えて最後に更新することに注意

マージとしてはi+j-1>kになる場合、くっつつけられません。なので全て切り離し+child[u]です

そうでない場合は、すべて切り離すか、くっつつけるかの2通りで更新します。

j+1>iのとき最大深さが変わるので添え字が変化します。

最後に解を求めます。

任意の頂点について非連結（削除される）可能性を持っているのですべて調べる必要があります。

dp[i][j]：i=1~n,j=0~k+1で

n-child[i]+dp[i][j]です

部分木以外を削除し、部分木内でk以下になるように削除したものです。

提出コード

この計算量で27msはちょっと信じがたいですね。ケース弱いのかも。