图论————最近公共祖先（LCA）
方法：
1.标记法：
（1）将u到根节点的路径标记一遍
（2）将v到根节点的路径走一遍如果与u标记的路径相重合，则重合点为两者公共祖先
2.跳跃法：
(1)先让其中一个节点跳到另一个的同一深度
(2)两个一起跳，直到找到共同祖先
代码如下：
vector<int> g[500010]; //存节点 int d[500010]; //节点深度 int f[500010]; //节点父亲 void dfs(int u,int fa){ //计算节点深度和父节点 d[u]=d[fa]+1; f[u]=fa; for(int i=0;i<g[u].size();i++){ int v=g[u][i]; if(v==fa){ continue; } dfs(v,u); } } int lca(int u,int v){ if(d[u]<d[v]){ //保证u最深 swap(u,v); } int cha=d[u]-d[v]; for(int i=1;i<=cha;i++){ //保证让两个节点在同一深度 u=f[u]; } while(u!=v){ //两个节点同时向上爬 u=f[u]; v=f[v]; } return u; //此时u和v就都是他俩的公共祖先 }(3)利用二进制优化跳跃的过程：
状态：father[i][j]表示以i开始，长度为2^j的父亲
模板题：
P3379 P3379 【模板】最近公共祖先（LCA） - 洛谷
程序模板：
#include<bits/stdc++.h> using namespace std; int n,m,s; vector<int> g[500010]; int d[500010]; int father[500010][25]; void dfs(int u,int fa,int depth){ father[u][0]=fa; for(int i=1;i<=20;i++){ father[u][i]=father[father[u][i-1]][i-1]; } d[u]=depth; for(int i=0;i<g[u].size();i++){ int v=g[u][i]; if(v==fa) continue; dfs(v,u,depth+1); } } int lca(int a,int b){ if(d[a]<d[b]){ swap(a,b); } for(int k=20;k>=0;k--){ if(d[father[a][k]]>=d[b]){ a=father[a][k]; } } if(a==b){ return a; } for(int k=20;k>=0;k--){ if(father[a][k]!=father[b][k]){ a=father[a][k]; b=father[b][k]; } } return father[a][0]; } int main(){ cin>>n>>m>>s; for(int i=1;i<n;i++){ int x,y; cin>>x>>y; g[x].push_back(y); g[y].push_back(x); } dfs(s,0,1); while(m--){ int a,b; cin>>a>>b; cout<<lca(a,b)<<endl; } return 0; }