足跡-sokuseki-

りかの日進月歩の記録

オイラーツアーとセグ木を使ってLCA、パスのクエリに答える

本記事では以下の問題を解きます。

N 頂点の重み付きの無向木が与えられる。
Q 回、ある辺の重みを変更するクエリと、ある2つの頂点の間の距離を求めるクエリが与えられる。
これを、1≤N≤100000, 1≤Q≤100000 で解け。

オイラーツアーは木をDFSしたときの順番で頂点を記録する手法です。オイラーツアーで記録した頂点を配列に順に入れておき、それをセグ木に対応付けます。
オイラーツアー、セグ木の概要はここではこれ以上触れません。

今回使うオイラーツアーは以下のものです。dfs以外の詳細は省きます。

vector<vector<int>> g(n); //グラフの隣接リスト
vector<int> v; //オイラーツアーの頂点配列
vector<int> ind(n); //各頂点がオイラーツアー配列の何番目に最初に訪れるか

void dfs(int now, int par){//今の頂点、親の頂点
    ind[now] = v.size();
    v.push_back(now);
    for(int i = 0; i < g[now].size(); i++){
        if(g[now][i] != par){
            dfs(g[now][i],now);
            v.push_back(now);
        }
    }
}

根からある頂点への距離

今回は以下の木を例に説明します。

f:id:wk1080id:20200527180135p:plain:w500

この場合オイラーツアーの配列は{1,2,3,4,3,2,5,6,5,7,5,2,1}となります。
オイラーツアー配列では、隣り合う2要素は辺で繋がれているので、辺の距離(コスト)を対応づけることができます。
f:id:wk1080id:20200622225404p:plain:w800




では距離を計算していきましょう。

例えば根1から頂点3までの距離を考えてみると、3+1=4になってほしいです。
f:id:wk1080id:20200529235609p:plain:w400
これは先ほどの配列で考えると、配列の先頭から、オイラーツアー配列で頂点3に対応するところまでの辺のコストの総和と考えることができます。
f:id:wk1080id:20200622225153p:plain:w800



根1から頂点5までの距離はどうでしょうか。同じように木で考えると、根1から頂点5までの距離というのは、 (1から5の距離:ピンク) = (1から4の距離:青) - (2から4の距離:緑) + (2から5の距離:青) と考えることができます。
f:id:wk1080id:20200530001644p:plain:w400
これを先ほどと同じように配列でうまく考えるには、帰りがけの辺のコストを負にして打ち消してあげられるようにします。
f:id:wk1080id:20200622224958p:plain:w800
こうすると、先ほど根1から頂点3までの距離を求めたのと同様、根1から頂点5までの距離は、配列の先頭から、オイラーツアー配列で頂点5に対応するところまでの辺のコストの総和と考えることができます。
f:id:wk1080id:20200622224712p:plain:w800


これで、根からある頂点への距離を先頭からのsumで計算できるようになりました。累積和などを使えば高速に計算できます。

任意の2つの頂点間の距離

先ほどの図において、頂点3と頂点6のパスを考えます。
根から頂点3と根から頂点6の距離は計算できるので、ここから無駄な部分を引けば、頂点3と頂点6の距離はわかります。
無駄な部分というのは、根から、頂点3と頂点6のLCAの頂点の距離です。
よって、LCAを求めることができれば、任意の2つの頂点間の距離を求めることができますね。
LCAの性質を考えると、頂点3と頂点6のLCAは、頂点3から頂点6に向かうパス上にあり、かつ、その中で根からの深さが最も小さいものです。
f:id:wk1080id:20200530003402p:plain:w500

そのため、オイラーツアーの配列を求める際に、根の深さを記録してセグ木を作ってあげれば、区間minを計算することでLCAを求められます。

問題を解く

よって、この問題を解くには、オイラーツアー配列を作り、それに対応するコストの配列(帰りがけは逆符号とする)を作ってsumを計算できるようにして、根からの深さ配列を記録して区間minとその対応する頂点を計算できるようにすれば、計算クエリは処理できます。

変更クエリは、クエリで与えられた辺に対応するコストの配列の要素を変更すれば良いです。そのためには、各辺がコスト配列のどこに対応するのかを持っておく必要があります。これはそれぞれの辺がコストの配列のどのインデックスに対応するかを配列で持っておくなどの方法で実現できます。

最後に

この問題はHL分解を使って解くこともできます。
(HL分解を勉強しようとしたら遭遇したので:絶対に初心者でもわかるHL分解/Heavy-Light-Decomposition - Qiita
オイラーツアーは、ある頂点の子孫に一様に操作することしかしたことがなかったので、新鮮でした。
まあHL分解のほうが木のいろんなクエリに答えることができるので、わざわざこの方法を勉強しなくてもよいという説はあります。






図作るのめんど