はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける重心分解問題まとめ

重心分解

  • Centroid Decomposition
  • 資料1 資料2 資料3
  • 「木上のクエリ」と「木全体についての数え上げ・最大最小」で使える。実装方針が全然違うので、別物で考えたほうがいい。
    • 木上のクエリでは同心円状に伝搬させることが出来るのが良い
    • (「部分木->オイラーツアー, パス->HL分解, 同心円状->重心分解」というイメージ)
    • 木全体についての数え上げは重心から毎回dfsをしていく(深さがO(logN)で各深さでのdfsをまとめるとO(N)となり、O(NlogN)となる)