HL分解の実装
Heavy-Light Decomposition を参考にHL分解を実装していましたが Easiest HLD with subtree queries を見たら思ってたより短く実装できることを今更知ったのでそれについて書きます．
の子のうち，部分木のサイズが最も大きいものが g[v][0] に来るように並べ替える．これによって辺(v,g[v][0]) が heavy-edge となる．
void dfs1(ll v, ll p) { if(g[v].size() && g[v][0]==p) swap(g[v][0], g[v].back()); for(auto &to: g[v]) { if(to == p) continue; dfs1(to, v); sz[v] += sz[to]; if(sz[to] > sz[g[v][0]]) swap(to, g[v][0]); } }
頂点番号をdfsの行きがけ順で振り直す(vid)ことで，パスが連続した数字に対応するようにできる．パスに対するクエリを処理するために用いる head, par を各頂点に対して求める．heavy edge を参照しているのであれば，toはvと同じheavy pathに属するので head[to] = head[v] となる．それ以外の場合は to 自身が heavy path の先頭になる．
void dfs2(ll v, ll p, ll &k) { par[v] = p; vid[v] = k++; for(auto to: g[v]) { if(to == p) continue; head[to] = (to == g[v][0] ? head[v] : to); dfs2(to, v, k); } }
for_each や for_each_edge，lca については特に変更なしでそのまま同じ．
全体の実装
