parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ HL分解 復習用コメント付きコード /* 思いつき方 頂点を黒く塗る その黒い頂点を含む部分木は？ 根まで行く距離が長過ぎる HL分解する */ /* HL分解 Heavy-Light Decomposition 木の構築 O(|V|+|E|) あらかじめ与えられた木について、頂点u,v間のパスをセグメント木などで扱える半開区間の集合に変換する。区間の数はO(log(|V|))個。 ひとつの区間は連結した頂点たちにIDをふったもので、頂点の深さは全て異なる。その区間内では、(深さの値の差)=(IDの値の差) になっている． 1クエリ O(log(|V|)) スタックオーバーフロー回避版 */ class… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F05%2F03%2F113153" title="Birjik and Nicole&#39;s Tree Game | HourRank 20 - parukiのブログ" 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-05-03 11:31:53 rich https://par.hateblo.jp/entry/2017/05/03/113153 1.0 100%