初めに

この記事は、Heavy-Light分解(重軽分解、HL分解)・オイラーツアー・その融合形についての記事です。先日ある方のエントリに感動したのでこの記事を書きます。 HL分解とオイラーツアーは、論点を木から配列にずらすことで木に関するクエリをうまく処理する手法です。この記事ではこれらに加え、HL分解と「部分木に関するクエリを処理するオイラーツアー」を融合させることで、パス・部分木に絡むクエリ両方を処理できるよう方法を紹介します。

＿人人人人人人人人人人人人人人人人人人人人＿
＞　多分これが一番わかりやすいと思います　＜
￣ＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹ￣

初めに
オイラーツアー
- パスに関するET
- 部分木に関するET
HL分解
Easiest HLD with subtree queries
- 実装例
  - HLD本体
〆

※クッソ長いです。ごめんね

オイラーツアー

雑にネットで調べたのですが、主に2種類あるようです。

パスに関するクエリを処理するオイラーツアーと
部分木に関するクエリを処理するオイラーツアーです。

どちらも「クエリを列処理に還元できるようにBFS(深さ優先探索)をして頂点を並べる」のは変わりません。以下オイラーツアー(Euler Tour)をETと略すことにします。宇宙人ではありません。

冒頭のHL分解+部分木ETの理解のためには、パスETの方の理解は必ずしも必要ではありません。面倒な方はこれからのパスETは飛ばしてお読みください。

パスに関するET

次のような木を考えます。

ペイント最高!

この木上でDFSを行います。根から始めて素直に左側の子から訪れると、下の図のように訪れることになります。頂点の左の青い数字は来た順番です(一度来た頂点も記録します)。

今このBFSで訪れた順に、頂点を並べてみます。 $n$ 番目の頂点を $vi[n]$ とします:

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$vi[n]$	0	1	2	4	2	5	2	6	7	6	2	1	3	1	0

次に各頂点 $v$ について、

「 $v$ が始めて訪れた時の添え字」 $\displaystyle{vd[v]}$
「 $v$ が最後に訪れた時の添え字」 $\displaystyle{vu[v]}$

を記録します:

$v$	0	1	2	3	4	5	6	7
$\displaystyle{vd[v]}$	0	1	2	12	3	5	7	8
$\displaystyle{vu[v]}$	14	13	10	12	3	5	9	8

この2つは以下のBFSで求められます

void bfs(vector<vector<int>>& childs,int v,int& ind){
    vd[v]=ind++;
        for(int ch:childs[v]){
            bfs(childs,ch,ind);
            ind++;
        }
    vu[v]=ind-1;
}

この時2頂点 $\displaystyle{u,v}$ (ただし $\displaystyle{vd[u]\leq vd[v]}$ )について、以下が成り立ちます:

頂点 $\displaystyle{vi[vd[u]]=u\rightarrow vi[vd[u+1]]\rightarrow \cdots\rightarrow vi[vd[v]]=v}$ は $u\rightarrow v$ のパスになる(ただし最短のパスではない)

例えば

$u=1,v=6$ について、 $\displaystyle{vd[1]=1,vd[6]=7}$
$\displaystyle{vi[1]～vi[7]}$ ,つまり $\displaystyle{1\rightarrow 2\rightarrow 4\rightarrow 2\rightarrow 5\rightarrow 2\rightarrow 6}$ は $u$ から $v$ へのパスである
$u=7,v=3$ について、 $\displaystyle{vd[7]=8,vd[3]=12}$
$\displaystyle{vi[8]～vi[12]}$ ,つまり $\displaystyle{7\rightarrow 6\rightarrow 2\rightarrow 1\rightarrow 3}$ は $u$ から $v$ へのパスである

この性質を用いて、以下の問題を解いてみます。

頂点数 $V$ の木が与えられる。各辺 $(v,p(v))$ には整数 $\displaystyle{a _ {v}}$ が定められている。初期値は $0$ 。
2種類のクエリが飛んでくる
更新クエリ $(v,x)$ : $\displaystyle{a _ {v}}+= x$
パス和クエリ $(u,v)$ :頂点 $\displaystyle{u}$ から $\displaystyle{v}$ (ただし $\displaystyle{LCA(u,v)=u}$ )への、最短のパス上の辺の $a _ {*}$ の総和を出力する

要素数 $2V-1$ の配列 $A$ を用意します。各クエリを以下のように配列の処理に置き換えます。

更新クエリ $(v,x)$ : $\displaystyle{A[vd[v]-1]+=x,A[vu[v]]-=x}$
パス和クエリ $(u,v)$ : $\displaystyle{\sum _ {i=vd[u]}^ {vd[v]-1}A[i]}$ を求める

この処理はセグ木に任せることで $O(log\ n)$ で実現可能です。

$vi[*]$	$0$	$1$	$2$	$4$	$2$	$5$	$2$	$6$	$7$	$6$	$2$	$1$	$3$	$1$	$0$
$A _ {*}$	$a _ {1}$	$a _ {2}$	$a _ {4}$	$-a _ {4}$	$a _ {5}$	$-a _ {5}$	$a _ {6}$	$a _ {7}$	$-a _ {7}$	$-a _ {6}$	$-a _ {2}$	$a _ {3}$	$-a _ {3}$	$-a _ {1}$

具艇的なコードは書きません、めんどいので...。

$(u,v)$ の一方が $LCA(u,v)$ でなくとも、LCAを取ることでこのパターンに帰着できます。また辺の重みの足し算ではなくほかの演算でも可能です。この演算が可換でない場合も、二方向の演算結果を持っておくことで適用できます。ただし逆元や単位元を持つ必要があります。したがって行列積や最大最小には使えません。総じて、いわゆる群っちゅう奴なら乗せられるということです。

LCAも求められます。DFSの時各頂点の深さも配列 $D$ に記録しておきます。頂点 $u,v$ のLCAは、 $\displaystyle{D[vd[u]]からD[vd[v]]}$ の中で値が最も小さくなるような頂点です。

部分木に関するET

この場合も同様の準備を行います。ただし今度のBFSでは一度訪れた頂点は飛ばして記録します。

$l[v]$	0	1	2	3	4	5	6	7
$v$	0	1	2	4	5	6	7	3

以下、頂点 $v$ を何番目に訪れたかを $l[v]$ で表します。頂点 $6$ の部分木は $6,7$ です。これは先の表下段の $l[6]=5,6$ 番目です(0-index)。同様に、頂点 $2$ の部分木は $2,4,5,6,7$ です。これは先の表下段の $l[2]=2～6$ 番目です。このように、各部分木が表下段の数列の部分列に対応しています。
よって、頂点 $v$ に関する情報を配列の $l[v]$ 番目においておけば、部分木に関するクエリは列に関するクエリに変換できます。具体的に以下のような問題で見てみます。

頂点数 $V$ の木が与えられる。各頂点 $v$ には整数 $\displaystyle{a _ {v}}$ が定められている。初期値は $0$ 。
2種類のクエリが飛んでくる
更新クエリ $(v,x)$ : $\displaystyle{a _ {v}}+= x$
部分木和クエリ $(v)$ :頂点 $\displaystyle{v}$ の部分木に含まれるすべての頂点 $u$ の $a _ {u}$ の和を出力する

まず次のようなBFSを行います。

void bfs(vector<vector<int>>& childs,int v,int& ind){
    l[v]=ind++;
        for(int ch:childs[v]){
            bfs(childs,ch,ind);
        }
    r[v]=ind-1;
}

BFS順に頂点を並べた時に、頂点 $v$ の部分木は $\displaystyle{l[v]}$ 番目～ $\displaystyle{r[v]}$ 番目の部分列に対応します。次に要素数 $V$ の配列 $A$ を用意します。 $\displaystyle{a _ {l}}$ は $\displaystyle{A[l[v]]}$ に入れます。
更新クエリ $(v,x)$ に対しては、 $\displaystyle{A[l[v]]+=x}$ をします。
部分木和クエリに対しては、 $\displaystyle{A[l[v]]～A[r[v]]}$ の和を求めればいいです。
したがってこの問題はセグ木で解くことができます。

以上のようにETは、枝をうまい具合に列に変換して部分木・パス関連のクエリをうまく捌こうという案だと思っています。

HL分解

一方HL分解そのものは、「列がノードである扱いやすい木に変換する」という手法です。扱いやすいというのは、深さが低い、という意味です。

まず辺を2種類の辺、Heavyな辺とLightな辺に分けます:

(高さ $1$ 以上の)各頂点から、部分木が最も大きい子頂点への辺をHeavyな辺、
それ以外の辺はLightな辺

水色の数字は各頂点の部分木の要素数、水色の辺がHeavyな辺です。例えば頂点 $2$ の子頂点は $4,5,6$ ですが、それぞれの部分木の要素数は $1,1,2$ です。よって頂点 $2$ から葉方向へのHeavyな辺は $2\rightarrow 6$ です。

次に、Heavyな辺で結ばれた頂点たちを、元の木での上下関係をとどめ一つにまとめます。以下この1つにまとめたものを「Heavy集合」とでも呼ぶことにします。あるHeavy集合に含まれる集合と、別のHeavy集合に含まれる頂点がLightな辺で結ばれている場合2つのHeavy集合を結ぶと、元の木より低い木ができます。各Heavy集合は持っている頂点列を管理します。

この図の場合、

$0$ 番目のHeavy集合が持つ頂点は、根の方から順に $0,1,2,6,7$
$1$ 番目のHeavy集合が持つ頂点は、根の方から順に $4$
$2$ 番目のHeavy集合が持つ頂点は、根の方から順に $5$
$3$ 番目のHeavy集合が持つ頂点は、根の方から順に $3,8$

深く書く気力もないので証明等は割愛しますが(は?)、この変換で木の深さを $log\ V$ 程度に抑えることができます。

この方法の利点は、長い枝を配列で処理し木上を行き来する回数を抑えられることです。具体的にどういう処理を行うか、改めて「パスに関するET」での例題で考えることにします。うまい抽象論を述べる日本語力がないので。

頂点数 $V$ の木が与えられる。各頂点 $v$ には整数 $\displaystyle{a _ {v}}$ が定められている。初期値は $0$ 。
2種類のクエリが飛んでくる
更新クエリ $(v,x)$ : $\displaystyle{a _ {v}}+= x$
パス和クエリ $(u,v)$ :頂点 $\displaystyle{u}$ から $\displaystyle{v}$ (ただし $\displaystyle{LCA(u,v)=u}$ )への、最短のパス上の頂点の $a _ {*}$ の総和を出力する

やはり具体的な実装は疲れるのでやめときますが(気が向いたら書くかも)、図を使いつつまあざっくり説明します。

前準備:HL分解をします
- 各頂点の部分木のサイズを求める
- 各頂点についてどのHeavy集合に属するか求める(私はHeavy集合を最も根に近い頂点で見分けてます)
- 各Heavy集合の(Heavy集合のみの木での)深さを求める...LCAを求める際には必要です
- 各Heavy集合にセグ木を用意させる
更新クエリの場合、
- 頂点 $v$ を含むHeavy集合を求め、セグ木の $v$ に対応する場所を $+=x$ する
パス和クエリの場合、
- の属するHeavy集合との属するHeavy集合が異なる間、(whileループ)
  - $H$ の持つ一番根に近い頂点 $t$ から $v$ までの和を $H$ のセグ木で求める
  - $u$ を $t$ の親で置き換え
- $u$ から $v$ までの和を求める

Heavy集合の木を1個ずつ上がっているわけですが、深さは高々 $log\ V$ ですから計算量は $O(log^ 2\ V)$ です。

Easiest HLD with subtree queries

正直ここからが本題です。長いね。すずろに書いてたらめちゃくちゃ長くなりました。ごめんね

ご紹介するのは、CodeForces上のadamant様のこのエントリです。まあざっくりとアイデアを日本語にすると、「0番目の子がHeavyな辺でつながってくれれば、オイラーツアーしただけでHeavy集合がならんでくれるよね」という話です。

codeforces.com

ソースコード部分の下、おじさん?お兄さん?の上の英文は大体つぎのような感じです:

このBFSすれば、

頂点 $v$ の部分木が $\displaystyle{[in _ v,out _ v)}$ に、

$v$ からHeavy集合の一番上の頂点 $nxt _ v$ へのパスが $\displaystyle{[in _ {nxt _ v},in _ v]}$ に

対応する配列がゲットできるよこれで同じセグ木でパスと部分木両方処理できるよ

具体的にソースコードを見てみます。

void dfs_sz(int v = 0) {
    sz[v] = 1;
    for(auto &u: g[v]) {
        dfs_sz(u);
        sz[v] += sz[u];
        if(sz[u] > sz[g[v][0]]) {
            swap(u, g[v][0]);
        }
    }
}

基本的には頂点 $v$ の部分木のサイズ $sz[v]$ を求める処理です。普通と違うのは、swapの部分です。
これはつまり、「部分木のサイズが一番大きい子を強制的に0番目にする」わけです。もっと言うと、Heavy辺の決め方から「0番目の子が親と同じHeavy集合に属する」わけです。

次に2個目のDFS関数を見てみます。

void dfs_hld(int v = 0) {
    in[v] = t++;
    for(auto u: g[v]) {
        nxt[u] = (u == g[v][0] ? nxt[v] : u);
        dfs_hld(u);
    }
    out[v] = t;
}

まず $\displaystyle{in,out}$ は前に示した通り、部分木に関するETにおける頂点 $v$ の部分木の範囲です。一方、子 $u$ について、

$u == g[v][0]$ 、つまり $u$ と $v$ が同じHeavy集合ならば $\displaystyle{nxt[v]}$ は $nxt[u]$
$u \neq g[v][0]$ 、つまり辺 $(u,v)$ はLightな辺ならば $\displaystyle{nxt[u] = u}$

これで $nxt$ は各頂点が属するHeavy集合の、最も根に近い頂点になります。

わざわざ2つの子をswapしたのにも意味があります。素直に0番目の子から訪ねるオイラーツアーをした結果がHeavy集合を並べた形になるからです。例えば先の図の木の場合、ETの結果は $0,1,2,6,7,5,4,3,8$ になります。この列は確かにHeavy集合を並べた形になっています。

実装例

HLD本体

class HLD {
public:
    Tree& tree;
    LL V;
    VLL depth;   //各頂点が属するHeavy集合の深さ
    VLL top;   //各頂点が属するHeavy集合の一番上の頂点
    VLL in;   //各頂点がEuler-Tourでどこにいるか
    VLL out;   //各頂点の部分木の終わり
    HLD(Tree& t, LL root = 0):tree(t) {
        V = t.size();
        VLL subtrees(V, -1);
        //各部分木のサイズを求める
        {
            stack<LL> order;
            stack<LL> hold;
            hold.push(root);
            while (!hold.empty()) {
                LL cur = hold.top();
                hold.pop();
                order.push(cur);
                for (LL ch : tree[cur].childs) {
                    hold.push(ch);
                }
            }
            while (!order.empty()) {
                LL cur = order.top();
                order.pop();
                subtrees[cur] = 1;
                for (LL& ch : tree[cur].childs) {
                    subtrees[cur] += subtrees[ch];
                    if (subtrees[ch] > subtrees[tree[cur].childs[0]]) {
                        swap(ch, tree[cur].childs[0]);
                    }
                }
            }
        }
        //HL分解 with eulertour
        {
            in.resize(V);
            out.resize(V);
            depth.resize(V);
            top.resize(V);
            LL cur = root;
            LL nextid = 0;
            dfs(cur, nextid);
        }
    }
    void dfs(LL cur,LL& nextind) {
        in[cur] = nextind++;
        for (auto ch : tree[cur].childs) {
            //0番目の子は同じHeavy集合
            if (ch == tree[cur].childs[0]) {
                top[ch] = top[cur];
                depth[ch] = depth[cur];
            }
            //それ以外は新しいHeavy集合
            else {
                top[ch] = ch;
                depth[ch] = depth[cur] + 1;
            }
            dfs(ch, nextind);
        }
        out[cur] = nextind - 1;
    }
    LL LCA(LL u, LL v) {
        //uの属するnode.depth >= vの属するnode.depthにする
        if (depth[u] < depth[v]) {
            swap(u, v);
        }
        while (depth[u] > depth[v]) {
            u = tree[top[u]].parent;
        }
        while (top[u] != top[v]) {
            u = tree[top[u]].parent;
            v = tree[top[v]].parent;
        }
        if (in[u] > in[v])return v;
        else return u;
    }
};

LLはlong longです(たぶん定数倍的にはよくないんですよね)
bfs_szに対応する部分はコンストラクタ中にいて、bfs_hldはbfsという名前になっています。LCAに対応するために、bfsで各頂点の属するHeavy集合の深さdepthも求めています。
LCAも求められます。

uのHeavy集合とvのHeavy集合を一個ずつ上がり続ける(u,vも一緒に更新)
両者が一緒になったら(つまりtop[u] == top[v])、オイラーツアーで先に来た方をLCAとする

<そのうち増やす>

〆

疲れました。思ったよりめちゃくちゃ長くなりました。最初からもうちょっとソーシャルディスタンスな感じで書けばよかったですね。

ano3のブログ

HL分解・オイラーツアー入門

初めに