hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 重心分解 Centroid Decomposition 資料1 資料2 資料3 「木上のクエリ」と「木全体についての数え上げ・最大最小」で使える。実装方針が全然違うので、別物で考えたほうがいい。 木上のクエリでは同心円状に伝搬させることが出来るのが良い （「部分木->オイラーツアー, パス->HL分解, 同心円状->重心分解」というイメージ） 木全体についての数え上げは重心から毎回dfsをしていく（深さがO(logN)で各深さでのdfsをまとめるとO(N)となり、O(NlogN)となる） 問題 重心分解のみを使うもの CF190 Ciel the Commander（入門） 木上のクエリ CF… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2017%2F12%2F19%2F152143" title="競技プログラミングにおける重心分解問題まとめ - はまやんはまやんはまやん" 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 2017-12-19 15:21:43 rich https://blog.hamayanhamayan.com/entry/2017/12/19/152143 1.0 100%