This documentation is automatically generated by online-judge-tools/verification-helper
// BEGIN CUT
class LCA {
private:
const int n = 0;
const int log2_n = 0;
vector<vector<int>> par;
vector<vector<int>> g;
vector<int> depth; // 頂点iの深さ
vector<int> vs; // 頂点を訪問順に並べたもの
vector<int> depth_seq; // depth_seq[i] = (頂点vs[i]の深さ)
vector<int> id; // 頂点が初めてvsに登場するインデックス
struct minimum_st {
using T = PII;
static T op(const T& a, const T& b) { return min(a, b); }
};
sparseTable<minimum_st> st;
void dfs(int v, int p, int d, int &k) {
id[v] = k; vs[k] = v; depth_seq[k++] = d; depth[v] = d;
for(auto to: g[v]) if(to != p) {
dfs(to, v, d+1, k);
vs[k] = v; depth_seq[k++] = d;
}
}
public:
LCA(int n_=1e5) : n(n_), g(n), depth(n), vs(2*n-1), depth_seq(2*n-1), id(n) {}
// u-vに辺を張る
void add_edge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
// rootを根として初期化
void build(int root = 0) {
int k = 0;
dfs(root, -1, 0, k);
vector<PII> v(2*n-1);
REP(i, 2*n-1) v[i] = {depth_seq[i], i};
st.construct(2*n-1);
st.init(v);
}
// uとvのlcaを返す O(1)
int get(int u, int v) {
if(id[u] > id[v]) swap(u, v);
return vs[st.query(id[u], id[v]).second];
}
};
// END CUT