no_imi https://blog.hatena.ne.jp/no_imi/ のいみのいみのいみのいみ https://noimi.hatenablog.com/ この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 17 日目の記事です。 木クエリゴリゴリ問題です。 問題概要 頂点の木がある。頂点 の親は であり、その間の距離は である。 について、 を求めよ。 制約 解法 大体重心を求めたいという問題です。 頂点のうち、 頂点しか気にならないのでそれらからなる圧縮木を作ってみます。すると、重心の性質から求める はその圧縮木上の頂点としてよいことが分かります。(特に、 が簡単にわかる。) さて、重心はある頂点から部分木のサイズが 以上の方向に移動することを繰り返すことで求まる。また、圧縮木上でも普通の木と変わらず、移動すると… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnoimi.hatenablog.com%2Fentry%2F2022%2F12%2F17%2F020753" title="Distance Sum (AOJ2636) - のいみのいみのいみのいみ" 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 2022-12-17 02:07:53 rich https://noimi.hatenablog.com/entry/2022/12/17/020753 1.0 100%