考察パート

求めたいのは木の重心みたいなやつ。

今見てる点に、markされた木の半分以上を持つ部分木があったらその方向に動く、みたいなのを繰り返すと行き着く場所。

頂点を1,2,...,nと塗っていって、その度にこの重心を求め、その点までの距離の総和を求めるという問題。

で、i+1番目まで塗られた時の重心はi番目まで塗られた時の重心と、頂点i+1のパスのうちどっかにあるってことがわかる。これが最重要。

これがわかるとHL分解やらLC-Treeで解ける。今回はLC-Treeを使った。

変数はいつもの(親と子のポインタとreverse_flagとsize)抜いて7個。めっちゃ大変。

Do use + 考察 + 更に実装 という感じでDo useよりは難しいと感じた。