洛谷P3379 【模板】最近公共祖先（LCA）
输入格式
第一行包含三个正整数 �,�,�，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 �−1 行每行包含两个正整数 �,�，表示 � 结点和 � 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 � 行每行包含两个正整数 �,�，表示询问 � 结点和 � 结点的最近公共祖先。
输出格式
输出包含 � 行，每行包含一个正整数，依次为每一个询问的结果。
输入输出样例 #1
输入 #1
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5输出 #1
4 4 1 4 4说明/提示
对于 30% 的数据，�≤10，�≤10。
对于 70% 的数据，�≤10000，�≤10000。
对于 100% 的数据，1≤�,�≤5×105，1≤�,�,�,�≤�，不保证�≠�。
样例说明：
该树结构如下：
第一次询问：2,4 的最近公共祖先，故为 4。
第二次询问：3,2 的最近公共祖先，故为 4。
第三次询问：3,5 的最近公共祖先，故为 1。
第四次询问：1,2 的最近公共祖先，故为 4。
第五次询问：4,5 的最近公共祖先，故为 4。
故输出依次为 4,4,1,4,4。
2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。
这题是最近公共祖先(LCA)的标准模板题
我们可以预处理出两点上跳的行为
定义dp[i][j]:从节点i出发走2^j步能到达的节点
那么类似于ST表
{
lastpos=dp[i][j-1]
dp[i][j]=dp[lastpos][j-1]
}
就是先走2^(j-1)步走到lastpos
再从lastpos走2^(j-1)步到达节点dp[lastpos][j-1]
总步数2(j-1)+2(j-1)=2^j
起点i，终点dp[lastpos][j-1]=dp[i][j]
所以递推式就是：
dp[i][j]=dp[dp[i][j-1][j-1]
还有一点就是我们用dp[i][0]记录i的父亲节点
这些都可以用dfs来解决：
void dfs(int pos,int fa){ deep[pos]=deep[fa]+1; dp[pos][0]=fa; for(auto v:g[pos]){ if(v==fa) continue; dfs(v,pos); } } -----再者就是LCA函数
先传入两个节点x，y
确保deepx<deep[y]
那么显然的要求y节点先跳上与x节点等高的位置：
int d=deep[y]-deep[x]; for(int k=0;k<=20;k++){ if(d>>k&1) y=dp[y][k]; }如果x==y，说明两者的LCA就是x！！！！
if(x==y) return x;如果x!=y:
那就一起往上跳
注意！要从最大的步数开始跳，因为从最小步数开始跳的话，一旦答案再很高的位置就会浪费很多时间复杂度！
for(int k=20;k>=0;k--){ if(dp[x][k]!=dp[y][k]) //如果发现跳了这么多步还没有公共的节点 x=dp[x][k],y=dp[y][k]; //直接跳，就不用再中间的节点了，省时省力！ }跳到最后，x，y都离最近公共祖先差一个位置，直接c++ return dp[x][0](或者c++ return dp[y][0]一样的)
ACcode:
#include<bits/stdc++.h> using namespace std; const int N=5e5+5; int n,m,s; int dp[N][25],deep[N]; //father=dp[i][0]; vector<int> g[N]; /* dp[i][j]:从节点i往上跳2^j步，达到的节点编号 lastpos=dp[i][j-1] 先从i跳2^(j-1)步 dp[i][j]=dp[lastpos][j-1] 再从lastpos跳2^(j-1)步 所以：dp[i][j]=dp[dp[i][j-1]][j-1]; */ void dfs(int pos,int fa){ deep[pos]=deep[fa]+1; dp[pos][0]=fa; for(auto v:g[pos]){ if(v==fa) continue; dfs(v,pos); } } int LCA(int x,int y){ if(deep[x]>deep[y]) swap(x,y); int d=deep[y]-deep[x]; for(int k=0;k<=20;k++) if(d>>k&1) y=dp[y][k]; if(x==y) return x; //倒序先大步跳 for(int k=20;k>=0;k--) if(dp[x][k]!=dp[y][k]) x=dp[x][k],y=dp[y][k]; return dp[x][0]; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>s; for(int i=1;i<=n-1;i++){ int x,y; cin>>x>>y; g[x].push_back(y); g[y].push_back(x); } dfs(s,s); for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) dp[i][j]=dp[dp[i][j-1]][j-1]; while(m--){ int x,y; cin>>x>>y; cout<<LCA(x,y)<<endl; } return 0;