とりになりたいかものはし

プログラミング(主に競プロ)に関するひとりごとなど

Codeforces AIM Tech Round Div1C Centroids

概要

$N$個の頂点で構成された無向木が与えられる。 あなたは最大で一回、辺を削除し別の頂点と頂点を辺で結びなおすことができる。
ただし、辺を追加した結果も木でなければいけない。
この時、適切な操作を行い$i$番目の頂点を重心にすることはできるかを判定しなさい。

重心とは?

重心とは、削除して1つ以上の木に分解したとき、 それらの木のどれもが頂点数$n/2$を超えないような頂点のことである。
木の「中心」との違いに注意せよ。また、重心が複数個ある可能性にも留意せよ。

制約

$2\le N \le 4*10^5$

考察

まずは各頂点に対し、重心かどうかの判定をしよう。 これは簡単な全方位木dpで求まるため、ここでは扱わない。
次に、すでに重心である頂点は自明に(0回操作することによって)重心にすることができるので、 重心でない頂点を考える。
重心でない頂点を削除すると、定義より、$n/2$を超える大きさの連結成分ができる。
このような$n/2$を超える大きさの連結成分は一個しかないので、この連結成分をどうにかして操作することによって 2つの$n/2$以下の連結成分に分解できないかを考える。
まず、適当な重心を根として、木を再構成する。
そうすると、$n/2$を超える大きさの連結成分は必ずどの頂点の親側にあることがわかる。
根を通らずに連結な頂点をグループ分けすると、 どのグループの大きさも$n/2$を超えないので、 自分が含まれているグループ以外のグループの中で一番大きいグループと、そうでない頂点で分割するのが一番良い。(下の図を参照)
f:id:platypus999:20170501192200p:plain
ただ、一つだけ例外があり、自分のグループのサイズがちょうど$n/2$の場合、自分以外の全グループに加え、根自体もまとめて分割するのがよい。(下の図を参照)
f:id:platypus999:20170501192512p:plain
いずれにせよ、分割によって無事大きさn/2以下の二つの連結成分に分解できればOK、そうでなければその頂点は重心になれない。












木の問題、難しい