弊社はエンジニアを熱烈募集しています． 以下から気軽にカジュアル面談申し込んでください． 就職・転職を考えている知人にも積極的に宣伝してください．
Spir | Smart scheduling calendar
この勉強会の宣伝もお願いします． 参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会 で実況や感想，質問を呟くなども．
Join Slido: Enter #code to vote and ask questions
グラフ理論における木についての用語を知ってることを要求する． 以下の勉強会で説明されている「木（Tree）」におけるもののみで問題ない．
231218_Heavy Light Decomposition
Auxiliary Treeは根付き木上の特定の頂点集合 $U$ について，$U$ とそれらのLCA(Lowest Common Ancestor)から構成され，元の木上の子孫関係を保ったままそれらの頂点を繋いだ木のことである．必要な頂点だけ見るように木を圧縮しているとも言える．
より厳密には，頂点集合 $V$ と辺集合 $E$ からなる木 $T=(V,E)$ と頂点の部分集合 $U\subseteq V$ について，$V' = \{\textrm{lca}(x,y) | (x,y)\in U^2\}$ と 任意の頂点の組 $(x,y)\in U^2$ のLCAが元の木のLCAの変わらないように張った辺の集合 $E'$ からなる木 $T' = (V',E')$ をAuxiliary Treeと呼ぶ．
$U = \{1,4,5,10,11\}$の例，$E'$ は $U$ に LCAである $\{2,9\}$ を追加した集合になる．
$U = \{3,9,12,13\}$の例
呼び方は諸説あり，「Virtual Tree」や「LCA tree」と呼ばれることもある．「Auxiliary Tree」という名称は一般的な表現であり適切ではないという話もあるが，本勉強会では便宜上この名で呼ぶこととする．