概要

HL 分解（重軽分解, HL Decomposition, Heavy-Light Decomposition）には、与えられたパスを heavy path に含まれる path に分解する機能を付けると便利ですが、LCA を含むかどうか（いわゆる節点/辺イテレータ）、非可換なことをしたいときのパスの方向など考えるべきことが多いです。いたずらにインターフェースを増やしたり複雑にしたりすることなくそれらに対応する方法を思いついたためご紹介します。

内容

図のように path segment に分解したら、次のものを返すとよいです。

• i: 最も根側の節点
• j: 最も葉側の節点
• last: 最後の path segment である（i.e. LCA を含む path segment である）かどうか
• reverse: from --> to と i --> j が逆方向かどうか

あと次のものにアクセスできるようにしておきます（今回の説明で必要なのは index だけですが、parent, head は最後のコードを読むためとか実装の参考とかのために言及しました）

• index: 節点番号 → HL 分解の訪問時刻
• parent: 節点番号 → 親の節点番号
• head: 節点番号 → 所属する heavy path のもっとも根側の節点番号

また i, j の代わりにその index を返すようなイテレータも作っておくと、外から index にアクセスしないといけない機会が減ってよいと思います。

こうしておくと、よくあるケースに対応できます。　

• LCA だけ省きたい → index[i]..=index[j] の代わりに index[i] + usize::from(last)..=index[j] を使えばよい
• 非可換な積を計算したい → 両方の向きの積をセグ木で管理。reverse で場合分けして集約

実装はこういう感じでできます。

pub struct PathSegments<'a> {
    hld: &'a Hld,
    from: usize,
    to: usize,
    exhausted: bool,
}
impl Iterator for PathSegments<'_> {
    type Item = (usize, usize, bool, bool);

    fn next(&mut self) -> Option<Self::Item> {
        let Self { hld, from, to, exhausted } = *self;
        (!exhausted).then_some(())?;
        let Hld {
            index,
            head,
            parent,
        } = hld;
        Some(if head[from] == head[to] {
            self.exhausted = true;
            if index[from] < index[to] {
                (from, to, true, false)
            } else {
                (to, from, true, true)
            }
        } else {
            if index[from] < index[to] {
                self.to = parent[head[to]];
                (head[to], to, false, false)
            } else {
                self.from = parent[head[from]];
                (head[from], from, false, true)
            }
        })
    }
}