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

重心分解

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

問題

• 重心分解のみを使うもの
  • CF190 Ciel the Commander（入門）

• 木上のクエリ
  • CF199 Xenia and Tree（入門）
  • HR BST maintenance 解説

• 木全体についての数え上げ・最大最小
  • CSA58 Path Inversions 解説 （入門）
  • CF372 Digit Tree
  • CF458 Palindromes in a Tree 解説
  • AC 木の問題

• 以下未処理、メモ
  • http://kmjp.hatenablog.jp/entry/2017/10/03/0900 （木DPも追加で使う）
  • http://kmjp.hatenablog.jp/entry/2017/08/05/1030
  • CC Prime Distance On Tree（重心分解をするとFFTいらないって感じ？）
  • http://codeforces.com/blog/entry/52492
  • AOJ 競争
  • http://semiexp.github.io/docs/synchronization.pdf
  • https://www.codechef.com/DEC17/problems/CHEFFIB（きっかけ）解説
  • DDCC2016 予選 D. 道路網
  • CF381 Alyona and a tree 解説
  • CC Chef Cuts Tree（+任意modのNNT）解説
  • http://kmjp.hatenablog.jp/entry/2018/01/16/1000
  • http://www.learning-algorithms.com/entry/2018/01/20/031005
  • http://ei1333.hateblo.jp/entry/2018/01/21/204124
  • http://pekempey.hatenablog.com/entry/2018/01/21/164655
  • http://codeforces.com/contest/914/problem/E
  • https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_g