◇◇ref002:Summer Festival Contest 2018 - D : 木からパスへ (Tree--->path)◇◇

https://beta.atcoder.jp/contests/summerfes2018-div1/tasks/summerfes2018_d

$N$頂点からなる連結な無向木が与えられる。これに

• ノードを好きなだけ追加する
• 木の頂点と追加した頂点の間に好きなだけ辺を追加する（もとからある頂点どうしに辺をつくることはできない）
• できたグラフから閉路がなくなるまで好きなだけ辺を削除して、パス（すべてのノードの次数が2以下の木）にする

という操作を行うとき、与えられた木を一本の連結なパスにするために追加しなくてはならない最小のノード数を求めよ。

木を切断して$M$本のパスに分解できたとすると、それらの間にノードを1つ追加して辺で結ぶことで1本の連結なパスを作ることができる。よって$M$の最小値がわかれば、答えは${\rm min}(M)-1$となる。

$M$の最小値は、木DPで求めることができる。DPテーブルは以下のようである。 $$DP[i][j]={\rm ノード}i{\rm を根とする部分木をいくつかのパスに分解するとき、その分割数の最小値}$$ ここで、$DP[i][0]$は$i$がパスの端点として使われているときの分割数の最小値、$DP[i][1]$は$i$がパスの中間点として使われている時の分割数の最小値、$DP[i][2]$は${\rm min}(DP[i][0],DP[i][1])$、つまり$i$の使われ方にかかわらず、分割数の最小値である。よって、ノード0を与えられた木の根とすると、最終的な答えは$DP[0][2]-1$となる。

DPテーブルの遷移は以下のようである。

$DP[i][0]$は、ノード$i$をパスの端点として使う場合の最小の分割数である。これは$i$の子ノードから求めることができて、2つのパターンがある。1つは$i$単体を1つのパスとして扱うパターンであり、これは$sum=\sum DP[child][2]$(子を根とする部分木の最小の分割数の和)とすると、$sum+1$で表せる。もう1つは子のうちの一つに接続する場合であり、当然子ノードがパスの端点として使われている場合にしか接続できないので、これは$sum-DP[child_1][2]+DP[child_1][0]$で表せる。ここで$child_1$は$DP[child][2]-DP[child][0]$が最大になるような子ノードである。$i$が接続されていない子を根とする部分木は普通に$DP[child][2]$で分けて、接続された子は$DP[child_1][0]$で分けたいので、このようになる。よって、遷移は $$DP[i][0]={\rm min}(sum+1,sum-DP[child_1][2]+DP[child_1][0])$$ であるが、$i$が葉である場合には1を入れておく(1つめのパターンの子がないバージョン)。

$DP[i][1]$は、ノード$i$をパスの中間点として使う場合の最小の分割数である。これは1パターンしかなくて、子のうち2つに接続するので、上と同じ考え方で、その遷移は $$DP[i][1]=sum-DP[child_1][2]+DP[child_1][0]-DP[child_2][2]+DP[child_2][0]-1$$ ここで、$child_1,child_2$は$DP[child][2]-DP[child][0]$が大きい子ノード2つである。最後に1を引くことと、子が1つ以下しかないときはどうやっても$i$を中間点に使うことはできないのでINF(0を入れるとバグる)を入れておくことに注意。

これは$DP[i][0]$と$DP[i][1]$のminをとるだけでよい。

これで与えられた木の最小分割数がわかるので、1引いたものを出力すればいい。

特にない。難しかった。

戻る