yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ 考察パート 求めたいのは木の重心みたいなやつ。 今見てる点に、markされた木の半分以上を持つ部分木があったらその方向に動く、みたいなのを繰り返すと行き着く場所。 頂点を1,2,...,nと塗っていって、その度にこの重心を求め、その点までの距離の総和を求めるという問題。 で、i+1番目まで塗られた時の重心はi番目まで塗られた時の重心と、頂点i+1のパスのうちどっかにあるってことがわかる。これが最重要。 これがわかるとHL分解やらLC-Treeで解ける。今回はLC-Treeを使った。 変数はいつもの(親と子のポインタとreverse_flagとsize)抜いて7個。めっちゃ大変。 Do use … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2015%2F12%2F17%2F180901" title="Distance Sum - よすぽの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-12-17 18:09:01 rich https://yosupo.hatenablog.com/entry/2015/12/17/180901 1.0 100%