LCA
最近公共祖先之倍增法
倍增我们一般通用两种方法。比如，如果我们需要用二的次方凑出25这个数字时，就可能是。1->2->4->8->8->2或者是1->8->16。
那么，我们其实更加倾向于使用第二种方法。因为第一种适用于不固定长度的k。而第二种则更加倾向于固定长度的k。
同时我们可以发现第一种的时间是O(2 * logn),第二种的时间就是O(k)，显然第二种才是上上册。
然后我们在求最近的公共祖先时，如果暴力，让a,b一个一个跳的话时间是O(n)的。只能解决一小部分问题，所以倍增诞生了。
我们定义：\(dp_{x,i}\) 表示编号是 \(x\) 的点向上跳 \(2^i\) 步的节点的编号是什么。那么方程应该是什么呢？
其实很好求，当前节点跳 \(2^{i - 1}\) 时再跳 \(2^{i - 1}\) 是不是就等于 \(2^i\) 那么我们可以得知方程是:
dp[x][i] = dp[dp[x][i - 1]][i - 1];
那么接下来就十分好求了，首先你要使他们的深度保持一致。那么就是只要dep[dp[x][i]] >= dep[y]。
那么我们就让x向上跳 \(dp[x][i]\) 个节点。毕竟要它两深度一样也不能不用倍增啊（否则在特殊情况下就我们的倍增形同虚设）。
然后，要注意因为我们每次倍增使看跳了后相不相等，且最后的答案肯定使 \(dp_{x,0}\) 因为我们只要中间的距离大于1，我们都是可以跳的。
所以最后我们肯定是输出 \(x\) 的父亲，但是，问题出现了。如果在我们将深度变成一致时刚好两个点相等。
也就是一个点就是另一个点的祖先。那么我们就会输出错误的答案，所以我们要特判一下这种情况。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s;
vector<int>E[500005];
int dep[500005];
int dp[500005][25];
void dfs(int u,int fa){dp[u][0] = fa;for(int i = 1 ; i <= 20 ; i ++){dp[u][i] = dp[dp[u][i - 1]][i - 1];}for(int i = 0 ; i < E[u].size() ; i ++){int v = E[u][i];if(v != fa){dep[v] = dep[u] + 1;dfs(v , u);}}return ;
}
int lca(int x,int y){if(dep[x] < dep[y]){swap(x , y);}for(int i = 20; i >= 0 ; i --){if(dep[dp[x][i]] >= dep[y]){x = dp[x][i];}} if(x == y){return x;}for(int i = 20 ; i >= 0 ; i --){if(dp[x][i] != dp[y][i]){x = dp[x][i];y = dp[y][i];}}return dp[x][0];
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n >> m >> s;for(int i = 1 ; i < n ; i ++){int u,v;cin >> u >> v;E[u].push_back(v);E[v].push_back(u);}dep[s] = 1;dfs(s , 0);while(m --){int a,b;cin >> a >> b;cout << lca(a , b) << endl;}return 0;
}