atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ グラフ理論 木 オイラーツアー LCA（最小共通祖先） スパーステーブル 1. 概要 本記事では，オイラーツアーテクニック について解説します． オイラーツアーテクニックは 論文 3 において導入されたテクニックです．これは木の情報を，頂点全体や辺全体を特定の方法で $1$ 列に並べることによって表現するものです．このテクニックによって木に対するさまざまな問題を列に対する問題へと変換することができます． 本記事では特に，部分木クエリ，パスクエリ，最小共通祖先クエリへの応用を扱います． 2. 前提知識 DFS．セグメント木などのデータ構造． 3. オイラーツアーテクニック 根付き木に対して，根から DFS を行うことで，全ての辺を双方向に $1$ 度ずつ通るようなウォ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Feuler_tour_technique" title="オイラーツアーテクニック - 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:15:48 rich https://info.atcoder.jp/entry/algorithm_lectures/euler_tour_technique 1.0 100%