Tree-lca-idx.test.cpp

#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <stack>
#include <numeric>
#include <array>
using namespace std;
#include "../../lib/40-graph/Graph.cpp"
#include "../../lib/40-graph/StaticTree.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false);
    int N,Q; cin >> N >> Q;
    Graph<int> g(N);
    for(int i=1;i<N;++i) {
        int p; cin >> p;
        g.make_bidirectional_edge(i,p,1);
    }
    auto tree = StaticTree<StaticTreeOperator<int>>::builder(g).root(0).parent().child().subtree_size().heavy_light_decomposition().build();
    while(Q--) {
        int u,v; cin >> u >> v;
        cout << tree.lca_idx(u,v) << "\n";
    }
  	return 0;
}