Lib/オイラーツアー
☆再帰を使わないオイラーツアーの実装☆
code:cpp
//index,rev_indexをN取る
ll pt = 0;
while(!stk.empty()){
auto ほげほげ,type = stk.top();
stk.pop();
if(type){
indexp = pt;
//処理 (cf : seg.set(pt,w);
pt++;
stk.push({ほげほげ,false});
for(auto ふがふが : gp){
if(indexnext == -1) stk.push({ほげほげ,true});
}
}else{
//帰りがけ処理 (cf: seg.set(pt,-w);
rev_indexp = pt;
pt++;
}
}
0→任意の頂点へのパスクエリ、部分木に対するクエリ、最小共通祖先(LCA)の取得などができる
パスクエリ+LCAで任意の2頂点間の距離が取れる