1. 概要 本記事では，オイラーツアーテクニック について解説します． オイラーツアーテクニックは 論文 3 において導入されたテクニックです．これは木の情報を，頂点全体や辺全体を特定の方法で $1$ 列に並べることによって表現するものです．このテクニッ…

1. 概要 本記事では，根付き木の HLD（重軽分解）について解説します． HLD は根付き木の辺を heavy edge，light edge の $2$ 種に分けて扱うことで，木の頂点全体をいくつかのパスに分解するものです． HLD は，木に対するさまざまな計算に幅広く使えるテク…

1. 概要 根付き木における $2$ 頂点 $u, v$ に対して， $u$ から $v$ へのパスが通る，深さ最小の頂点を $u,v$ の LCA といい， $\mathrm{LCA}(u,v)$ と書きます． LCA の計算については，オイラーツアーテクニック などでも触れました．本記事ではそれより…