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

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