重心分解 - ferinの競プロ帳

参考文献
https://www.hamayanhamayan.com/entry/2017/12/19/152143
https://qiita.com/drken/items/4b4c3f1824339b090202

木の重心: その頂点を取り除いたときにできる部分木の要素数が元の半分以下になる頂点
重心は1個か2個必ず存在する

部分木の要素数を求める木DPを行うことで重心列挙ができる
実装例

vector<vector<ll>> g(n);  
  
vector<ll> sz(n, 1), centroid;  
void dfs(ll v, ll p) {  
    bool iscentroid = true;  
    for(auto to: g[v]) if(to != p) {  
        dfs(to, v);  
        if(sz[to] > n/2) iscentroid = false;  
        sz[v] += sz[to];  
    }  
    if(n-sz[v] > n/2) iscentroid = false;  
    if(iscentroid) centroid.push_back(v);  
}

重心を意識すると構築を考えやすいとか
列の中心の代わりに重心を使うと列だけじゃなくて木でも解けるとか例題1 例題2
を見たことがある

https://www.quora.com/q/threadsiiithyderabad/Centroid-Decomposition-of-a-Tree
重心分解を行うと木に分解できる．この木の特徴として
* 元の木と同じ $N$ 頂点の木である(辺集合が違う)
* 木の高さは $O(\log N)$
サイズを二分割することを繰り返しているので
* 重心分解した後の木で頂点 $A,B$ のLCAは，元の木におけるパス $A,B$ に含まれる
* 重心分解した後の木は $O(N \log N)$ 個のパスに分解でき，任意のパスは異なる2つのパスのmergeで表せる
各頂点について根の方向へ向かう $O(\log N)$ 個のパスを保持しておく．LCAまでのパスを取ってくると2つのパスのmergeで表せる．

重心分解の実装

重心を見つける
その重心をグラフから取り除く
取り除いた後にできる連結成分それぞれについて，再帰的に同じことをする

Problem - 321C - Codeforces

重心分解のときの再帰の深さに対応するアルファベットを配置する
$2^26$ は頂点数より大きいので全パターンで構成可能

https://codeforces.com/contest/321/submission/72283144

パスの数え上げ

以下は条件を満たすパス（など）の数を数え上げる系の問題
分割統治で条件を満たす区間（など）の数を数え上げることを重心を用いることで木上でも行える

分割統治: [l,mid) [mid, r) に分割しそれぞれ解いてマージを繰り返す

// [l, r) について解く  
void dfs(ll l, ll r) {  
    ll mid = (l+r)/2;  
    // mid をまたぐような分について計算  
    // [l,mid) と [mid,r) と midをまたぐような分 の結果をマージする  
}

毎回区間が半分になっていくので，midをまたぐ分の計算に $O(r-l)$ かけたとしても $O(n\log n)$ で終わる
例題

No.1002 Twotone - yukicoder

パスグラフのときを考えると分割統治のように計算ができる
区間[l,r) で mid をまたぐようなちょうど2色含むようなパスを数える
区間[l,mid) の頂点xから頂点midまでのパスに含まれる色に対して，頂点midから頂点yまでのパスが含む色の条件を考える

頂点xから頂点midまでのパスが含む色が(色1,色2)
(色1,色2) or 色1のみ or 色2のみ or 何も含まない(ようするにy=mid)
頂点xから頂点midまでのパスが含む色が色1のみ
色1以外の色のみを含む or (色1,色i) (ただし色i!=色1)

あとは(色1,色2)を含むパスの数をそれぞれ数えておくことでmidをまたぐ分の計算ができ，分割統治で解ける

一般の木については頂点midのかわりに重心cを用いて，cをまたぐようなパスを数えることで同様に解ける

各パスについて両端点で数えてるので最後に2で割る必要がある
頂点xから頂点midまでのパスが含む色が色1のみかつ (色1,色i) のパターンについては，頂点xから頂点midまでのパスが含む色が(色1,色2) かつ色1のみ含む(色2のみ含む) のパターンを2倍して数えるようにすると楽

https://yukicoder.me/submissions/437248

CS Academy

転倒数についての記述があるが，実はこれはあまり関係ない． $K+1$ 要素の数列 $A$ とこれを反転した数列 $\text{rev}(A)$ の転倒数の和は $k(k+1)/2$ で一定である．

よって，あとは長さが $K$ のパスの個数を数えられればよい．twotone と同じ要領で重心分解して，該当する頂点の分だけ参照するように，重心を含むパスの個数を数える操作を繰り返す．

$\text{cnt} \lbrack i \rbrack = ($ 重心からの距離が $i$ の頂点の個数 $)$ とした配列を用意しておく．距離が $d$ の頂点が存在した場合，距離が $k-d$ の頂点とのパスが長さ $k$ になる．つまり $\text{cnt} \lbrack k-d \rbrack$ 個パスが存在する．ただし，重心から同じ方向にある，重心をまたがないような2点を選択してはならない．そこでその分を引く処理を行う．

これでパスの個数を数えたあと $k(k+1)/2$ を掛ければよい．

https://ideone.com/YZcEiI

Contest Page | CodeChef

twotoneと同じ要領で該当するパスを数え上げます

重心 $c$ を含むパスのうち長さが素数のものを数える． $\text{cnt_dist} \lbrack i \rbrack = ($ 重心からの長さが $i$ のパスの個数 $)$ とした配列を用意する．重心 $c$ からの距離が $d$ の頂点が存在するとき，長さが素数 $p_i$ となるパスの個数は "大体" $\text{cnt_dist} \lbrack p_i-d \rbrack$ 個である．

ただし，重心 $c$ に隣接する頂点のうち同一の頂点を根とする部分木内から2頂点を選択すると，重心 $c$ を含むパスとはならないことから，この分を数えてはならない．これを実現するための単純な方法として， $c$ に隣接する各方向の分の cnt_dist を数えておき，余計に数えた分を引くという方法があるが， $n$ 要素の配列である cnt_dist を各方向の分用意するとMLEしてしまう．

このMLEを回避するために cnt_dist をin-placeに取り扱う．まず，cnt_dist を一旦全部数え上げる．重心 $c$ に隣接する頂点 $to$ の方向に進んだ頂点を端点とする分を数える．まず， $to$ の方向に進んだ頂点の分，cnt_dist を減少させる．これで $c$ をまたがないパスの分を計算することはなくなったので， $\text{cnt_dist} \lbrack p_i-d \rbrack$ の総和を求めればよい．この後，減少させた cnt_dist の分を増加させて元に戻す．別の $to$ についても同様の処理を繰り返す．

このあと別の重心について計算を行うためには，cnt_dist を全て0にする必要がある． $n$ 要素の配列全てに0を代入しているとTLEだが，cnt_dist が非0であるような個数は重心分解している途中で重心から連結な頂点数で抑えられる．また， $\text{cnt_dist} \lbrack i \rbrack =0$ ならば $i$ 以上の位置についても全て0なので，0が出てきた時点で打ち切ってよい．

https://www.codechef.com/viewsolution/30036393

Problem - C - Codeforces

重心 $c$ を含むパスで $m$ の倍数となるものを数える
$x$ と $d$ 桁の数 $y$ をこの順につないだときに， $m$ の倍数となる条件を考える
$10^{d}x + y \equiv 0 (\text{mod } m)$
$x \equiv -10^{d}y (\text{mod } m)$

$x$ の方 $($ つまり，頂点 $u$ から重心 $c$ に向かうパスに対応する数 $)$ について $\text{mp} \lbrack x \rbrack = (x$ の個数 $)$ となるような map を持っておくと，各 $y$ について $mp \lbrack -10^{d}y \bmod m \rbrack$ を足し上げることで求められる．

重心 $c$ から同じ方向の2頂点を選ぶのはだめなので，その分を引く処理を Prime Distance On Tree と同様にin-placeに書くと，重心分解の分とmapの分でlog2個になる．

https://codeforces.com/contest/715/submission/72510660

http://techtipshoge.blogspot.com/2016/09/centroid-decomposition.html　に載ってる解法
重心 $c$ から $to$ の方向に進んだときの $y$ の分を計算し， $x$ の分を mp に足すという処理を繰り返す．次に $to$ を見る順番を逆にして，同様の処理を繰り返す．このとき各 $x,y$ の組み合わせ方をそれぞれ一回ずつ試しているので漏れなく数えられている．0のときだけ2回数えてしまうのでその分は2で割って調整する．

これでもlog2個な気がするけど，全組み合わせを参照するのがこれでもできるの賢い

Problem - E - Codeforces

重心 $c$ を含む回文にできるパス $P$ が存在 → $P$ 上の頂点に+1したい

並べ替えて回文にできるか？の判定は奇数個存在する文字種が高々1個か？でできます．このような判定を行うためのハッシュとして， $i$ 番目の文字種が奇数個存在するなら $i$ 桁目を1とするハッシュが有用です．このハッシュで1が立っている桁が1個以下なら回文にすることが可能と判定できます．パス $P(=A\to B), Q(=B\to C)$ をつなげたパス $A\to C$ のハッシュは $P,Q$ のハッシュのXORで高速に求められるのがうれしいポイントです．

$\text{cnt} \lbrack i \rbrack = ($ ハッシュが $i$ である重心を一端とするパスの個数 $)$ とした配列を用意します．ハッシュが x の頂点が存在した場合， $\text{cnt} \lbrack x \oplus (\text{回文にできるハッシュ})$ の分のパスをつくれます．このパスの分の数を重心側の頂点に伝播させることでパス上の頂点に一律に加算する処理を実現できます．

同じ方向の2頂点を選ぶ分を減算する処理を，in-placeに行えばokです．

https://codeforces.com/contest/914/submission/72518429

C - 木の問題

重心 $c$ をまたぐような，頂点 $v$ から距離 $k$ のパスの数を数える
$\text{cnt} \lbrack i \rbrack = ($ 重心からの距離が $i$ の頂点 $)$ とした配列を持っておく

$\text{query} \lbrack v \rbrack = ($ 頂点 $v$ のクエリに関連する $(k,i)$ のペアの集合 $)$ の形で持っておく
各頂点 $v$ にたどり着くタイミングで $\text{query} \lbrack v \rbrack$ のクエリに寄与する分を数える

in-placeっぽくcntを減算する処理をすればok

https://atcoder.jp/contests/yahoo-procon2018-final-open/submissions/10557394

数えるものをin-placeアルゴリズムっぽく配列とかを持つのかなり汎用性がある気がしてきた

重心分解した木の高さを利用する問題

以下は重心分解した後の木の高さは $O(\log N)$ なことを使うやつ

Problem - 342E - Codeforces

重心分解を行った木をつくっておく．この木上で $\text{dist_to_red} \lbrack v \rbrack = v$ を根とする部分木でvに最も近い赤い頂点までの距離を保持する．この情報が存在していれば，頂点 $v$ にもっとも近い赤い頂点までの距離は $\min(\text{dist_to_red} \lbrack u \rbrack + \text{dist}(u, v))$ $($ ただし，頂点 $u$ は $v$ から根までのパスに含まれる $)$ となる．

頂点 $v$ を赤くした際に， $\text{dist_to_red} \lbrack u \rbrack$ が変化する頂点 $u$ は $v$ から根までのパスに含まれる頂点 $u$ となる．この頂点 $u$ について $\text{chmin}(\text{dist_to_red} \lbrack u \rbrack , \text{dist}(u,v))$ を行えばよい．

重心分解を行った木の高さは $O(\log n)$ となるため，各クエリ $O(\log n)$ で答えられる．
(下の実装はLCAを $O(\log n)$ でやったので各クエリ $O(\log^2 n)$ です)

2点間の距離を計算するのに重心分解した後の木ではなく，元の木を使わなければならないことに注意

https://codeforces.com/contest/342/submission/72284993

SPOJ.com - Problem QTREE5

上の問題とほとんど同じだが，色を白から黒に戻す操作が加わった．部分木に存在する(白い頂点,白い頂点までの距離)のペアをsetで保持することでこの処理に対応する．色を変更する場合はsetへの挿入/削除，距離を答える場合はsetの中の距離が最小のものを求めることで処理できる．

setの要素数は各クエリで $O(\log n)$ 個増えるので，全クエリ通して $O(q \log n)$ 個でメモリは問題ない．

https://ideone.com/QhYs5x

距離を求めたい2頂点は $(v, v\text{の祖先})$ という関係が存在する．dist[i][j] = (i回目の分解の根からjまでの距離) を持っておくとLCAを使わずに配列を見るだけで $O(1)$ で求められるようになる．

BST maintenance | HackerRank

二分探索木を実際に構成する．平衡してないのでsort列とかを突っ込むと普通に $O(n^2)$ かかって終了するので， $x$ を追加するときは， $x$ 未満の最大の頂点の右の子・ $x$ 以上の最小の頂点の左の子のどちらかに追加するとすればよい．

重心分解して木をつくる．この木上で $a_0, a_1, a_2, \ldots$ と順に頂点をactiveに変更していく． $i$ 番目の頂点を追加したときの答えは，( $i-1$ 番目の頂点までの答え) + ( $i$ 番目の頂点とactiveな頂点の距離の総和) となる．したがって，各 $i$ について ( $i$ 番目の頂点とactiveな頂点の距離の総和) を求められればよい．

これを行うために，以下の3つの情報を保持する．

$\text{dist} \lbrack i \rbrack = (i$ を根とする部分木で $i$ からactiveな頂点の距離の総和 $)$
$\text{contribution} \lbrack i \rbrack = (\text{dist} \lbrack \text{par} \lbrack i \rbrack \rbrack$ に $i$ を根とする部分木が寄与する分 $)$
$\text{cnt} \lbrack i \rbrack = (i$ を根とする部分木でactiveな頂点の個数 $)$

( $i$ 番目の頂点とactiveな頂点の距離の総和) を計算する上で， $\text{par} \lbrack v \rbrack$ を根とする部分木の頂点を2タイプに分割する．

頂点 $v$ を祖先にする頂点
ボトムアップで計算していくので，前に計算した結果からわかる
頂点 $v$ を祖先にしない頂点
頂点 $v$ からこれらの頂点のうちactiveなものまでの距離の総和でok

これらをまとめると，( $i$ 番目の頂点とactiveな頂点の距離の総和) は $\text{dist} \lbrack a \lbrack i \rbrack \rbrack + \sum_{\text{par} \lbrack v \rbrack \text{はa \lbrack i \rbrack の祖先}} \text{dist} \lbrack \text{par} \lbrack v \rbrack \rbrack - \text{contribution} \lbrack v \rbrack + (\text{cnt} \lbrack \text{par} \lbrack v \rbrack \rbrack - \text{cnt} \lbrack v \rbrack ) \times \text{distance}(a \lbrack i \rbrack , \text{par} \lbrack v \rbrack )$ となる．
$\text{dist} \lbrack a \lbrack i \rbrack \rbrack$ → 頂点 $a \lbrack i \rbrack$ と部分木に存在するactiveな頂点までの距離の総和

$\sum$ の中の項については $v$ を祖先にしない頂点の分を計算する．
$\text{dist} \lbrack \text{par} \lbrack v \rbrack \rbrack - \text{contribution} \lbrack v \rbrack$ → 祖先にしない頂点について， $\text{par} \lbrack v \rbrack$ からactiveな頂点までの距離の和を求める
$(\text{cnt} \lbrack \text{par} \lbrack v \rbrack \rbrack - \text{cnt} \lbrack v \rbrack ) \times \text{distance}(a \lbrack i \rbrack , \text{par} \lbrack v \rbrack )$ → 祖先にしない頂点については $a \lbrack i \rbrack$ から $\text{par} \lbrack v \rbrack$ までの距離の分を足す必要がある

あとは $a \lbrack i \rbrack$ をactiveにしたときに情報をupdateできればよい．
$\text{dist} \lbrack \text{par} \lbrack v \rbrack \rbrack += \text{distance}(v, a \lbrack i \rbrack )$
$\text{contribution} \lbrack v \rbrack += \text{distance}(v, a \lbrack i \rbrack )$
$\text{cnt} \lbrack v \rbrack += 1$

TLが結構厳しくて，

2点間の距離は $O(1)$ LCA を使う
endlは使わない
llをできるだけ使わない

をしないと通らなかった
（ただTLEしたケースを手元で実行したら0.4secで動いた　謎）

https://ideone.com/JiLYK8

Problem - D - Codeforces

JAG2017のday2で使ったセットにあったやつ
頂点 $v$ から距離 $d$ 以下の頂点を色 $c$ にするクエリと頂点 $v$ の色を聞くクエリが飛んでくる

ググったら出てきたACコードを解読して投げたら通ったのでその解法のことを書くけど，ちゃんとケースつくると怪しい気がする

頂点 $u$ から距離が $d$ 以下の頂点に色 $c$ を塗るようなクエリ $i$ が存在する状況を保持する．
$\text{info} \lbrack u \rbrack = (d, i, c)$ で $d$ について降順となるように管理する
また，距離が $d$ 以下を塗るときにすでに存在する距離が $d$ 以下のクエリの分は上書きされて消えるので，その分はちゃんと消すように管理する