pa[a][j] 表示 a 结点的 2^j倍祖先（j = 0时 为直接父亲，j = 1时为父亲的父亲……）
1.首先预处理出所有结点的深度值dep和父亲结点
void dfs(int u, int f, int d) {
dep[u] = d;
pa[u][] = f;
for(int i = ; i < G2[u].size(); i++) {
edge& e = E[G2[u][i]];
int v = e.u == u ? e.v : e.u;
if(v != f) {
dfs(v, u, d+);
}
}
}2.预处理出所有结点的 2^j 倍祖先
void pre() {
for(int j = ; (<<j) < n; j++)
for(int i = ; i <= n; i++) if(pa[i][j-] != -)
pa[i][j] = pa[pa[i][j-]][j-];
}3.查询操作，首先将 a，b中深度较大的结点上升到与深度较小的结点同一深度，然后两个结点同步上移，直到上移到最近公共祖先的直接儿子处。
int lca(int a, int b)//最近公共祖先
{
int i, j;
if(dep[a] < dep[b]) swap(a, b);
for(i = ; (<<i) <= dep[a]; i++);
i--;
//使a，b两点的深度相同
for(j = i; j >= ; j--)
if(dep[a] - (<<j) >= dep[b])
a=pa[a][j];
if(a == b) return a;
//倍增法，每次向上进深度2^j，找到最近公共祖先的子结点
for(j = i; j >= ; j--) {
if(pa[a][j] != - && pa[a][j] != pa[b][j]) {
a = pa[a][j];
b = pa[b][j];
}
}
return pa[a][];
}