树上倍增
<pre><code class="language-cpp">void dfs(int u, int f){
deep[u] = deep[f] + 1;
fa[u][0] = f;
for(int i = 0; i < mp[u].size(); i++){
int v = mp[u][i];
if(v == f) continue;
dfs(v, u);
}
}
void init(){
int k = log(n*1.0)/log(2.0);
for(int i = 1; i <= k; i++){
for(int j = 1; j <= n; j++){
fa[j][i] = fa[fa[j][i-1]][i-1];
}
}
}
int LCA(int u, int v){
int i;
if(deep[u] < deep[v]) swap(u, v);
for(i = 0; (1 << i) <= deep[u]; i++);
i--;
for(int j = i; j >= 0; j--){
if(deep[u] - (1 << j) >= deep[v]) u = fa[u][j];
}
if(u == v) return u;
for(int j = i; j >= 0; j--){
if(fa[u][j] != fa[v][j]){
u = fa[u][j];
v = fa[v][j];
}
}
return fa[u][0];
}</code></pre>