atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ グラフ理論 木 HLD（重軽分解） LCA（最小共通祖先） 1. 概要 本記事では，根付き木の HLD（重軽分解）について解説します． HLD は根付き木の辺を heavy edge，light edge の $2$ 種に分けて扱うことで，木の頂点全体をいくつかのパスに分解するものです． HLD は，木に対するさまざまな計算に幅広く使えるテクニックです．本記事では木のパスクエリと呼ばれるタイプの問題を主に扱うこととして，それ以外の応用については別記事で扱うこととします． 2. 前提知識 根付き木に関する用語．セグメント木などのデータ構造． 3. HLD 3.1. HLD とその性質 根付き木における子を持つ頂点について，部分木の頂点数が最も多い子をひと… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fheavy_light_decomposition" title="重軽分解（HLD） - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:13:13 rich https://info.atcoder.jp/entry/algorithm_lectures/heavy_light_decomposition 1.0 100%