Codeforces AIM Tech Round 3 (Div. 1) C. Centroids
あまり筋の良い方法ではないです。
問題概要
木が与えられる。辺を一個削除して好きな場所に辺を追加する、という操作を 1 回まで行えるとしたとき、すべての頂点 v に対して v を重心にできるか判定せよ。
解法
頂点 v を根として考える。もしサイズが n/2 より大きい部分木がないのであれば変更しなくても v は重心になる。存在するとき、その部分木のサイズを n/2 以下に減らす必要がある。
サイズが n/2 より大きい部分木を T とする。$\mathrm{size}(T)-\mathrm{size}(S) \le n/2,\; \mathrm{size}(S) \le n/2$ を満たすような T の部分木 S が存在すれば、S を切り取って v に繋げることで v を重心にできる。
このような S が存在するかどうかを高速に判定したい。
すべての頂点を根として DFS するのは $O(n^2)$ 掛かってしまうので、根は 0 に固定してうまく処理しよう。
v の最大の部分木が子方向にあるときと親方向にあるときでは処理が異なる。
子方向のときは、部分木のサイズを詰めこんだ multiset をマージテクで持ち上げていけば $O(n\log^2 n)$ で計算できる。euler-tour してから領域木でもできる。
親方向のときは、まず 1 回目の DFS で 自分より左側の部分木と祖先を根とする部分木を調べる。訪れ終わった頂点の部分木のサイズを multiset に入れておけば左側の部分木はすべて考慮でき、祖先は適当にやればいい。
2 回目の DFS で自分より右側の部分木を調べる。DFS の回す順番を逆にすればいい。
全方位木 DP でも解ける。これは v を根とする木での dp[v] を求める手法。
値を 1 個消すつもりで multiset::erase を呼び出してしまい、嫌なバグを生み出してしまった。気づけたから良かったけども…。
