倍增法

思路：对于暴力算法当中，我们求LCA需要进行两种操作：

第一步：判断两点是否在同一高度，如果不在同一高度，将下面的点提高同一高度下，这一步我们可以用swap保证永远操作下面的点

第二步：首先判断两者是不是已经位于同一个点，如果是的话，直接返回，这是LCA出现在两点之间的特殊情况；如果不是，那么我们让两点一起上升，当两点相遇的情况，我们就找到最近公共父节点了

所以倍增的思路就是使用二进制将上述过程优化到logn的时间复杂度，我们维系一个新的数组，f[N][logN],一维代表当前结点i，二维代表跳2^j位置，数组存的是从i结点跳2^j距离能抵达的位置，所以我们很容易发现一个递推公式f[u][i]=f[f[u][i-1]][i-1],带入可知，等式左边代表处于u的位置跳2^i抵达的位置,等式右边代表处于（u跳2^i-1的位置）跳2^i-1抵达的位置，很明显2^j==2^j-1+2^j-1,所以这是合理的。

那么树的深度我们可以用dfs来求，所以预处理我们也可以在dfs的同时进行处理,下面代码有详细解析:

<#include <bits/stdc++.h>  
using namespace std;  
const int N=500010;  
int h[N],e[N<<1],ne[N<<1],idx;//邻接表存树   
int n,m,root;  
int f[N][20];//代表从第i个结点开始跳2^j抵达的位置    
int d[N];//存当前结点深度   
void add(int a,int b){  
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;  
}  
void dfs(int u,int p){  
	d[u]=d[p]+1;//树的深度比他的父节点深度大1  
	f[u][0]=p;//当前结点向上跳2^0抵达他的父节点  
	for(int i=1;(1<<i)<=d[u];i++){  
		f[u][i]=f[f[u][i-1]][i-1];  
	}//加入所有合法跳转的距离   
	for(int i=h[u];~i;i=ne[i]){  
		int j=e[i];  
		if(j==p) continue;//不能递归处理回他的父节点  
		dfs(j,u);//递归处理所有子树   
	}  
}  
int LCA(int x,int y){  
	//第一步,让处于下面的结点上升到上面结点的相同位置  
	if(d[x]<d[y]) swap(x,y);//保证x是位于下面的结点,接下来上升x   
	for(int i=19;i>=0;i--){  
		if(d[x]-(1<<i)>=d[y])//只有x仍然在y的下面才处理  
		x=f[x][i];//更新x,让他向上跳   
	}  
	if(x==y) return x;//最近公共父节点可能出现在x和y之间,如果刚好出现,直接返回  
	//第二步,让x和y一起向上跳,如果两人跳到了相同的点,那这个点就是他们的最近公共父节点   
	for(int i=19;i>=0;i--){  
		if(f[x][i]!=f[y][i])//如果两人跳转相等,说明跳过了,退回来  
		x=f[x][i],y=f[y][i];//如果两人跳转不相等,就更新   
	}   
	return f[x][0];//最后找到的是两人公共父节点前一个位置,直接返回当前结点的父节点即可 
}  
int main(){  
	cin>>n>>m>>root;  
	memset(h,-1,sizeof h);  
	for(int i=1;i<n;i++){  
		int a,b;  
		scanf("%d%d",&a,&b);  
		add(a,b);add(b,a);//存无向树   
	}  
	dfs(root,0);//递归处理每个结点的深度和可跳跃的位置   
	for(int i=0;i<m;i++){  
		int x,y;  
		scanf("%d%d",&x,&y);  
		cout<<LCA(x,y)<<endl;  
	}  
	return 0;  
}  
``` ``` 
# tarjan算法  
###### 事先声明,不知道是不是样例被卡,这里提交的tarjan算法附加案例是无法通过的，但一样会被给100分
###### 对于tarjan算法我们事先要做好一些准备，tarjan算法会将全部的查询先一并读入，在一起返回，只用一个dfs得到全部的答案，所以这里我们另开一个邻接表用来存储查询的数据，查询数据存储的方式就差不多是图的存储，他的含义是，选定（x，y）这样一组查询数据，我们另其中一个作为主要对象，当我们递归处理到主要对象时，就通过这个查看一下查询数据当中也没有这样一对（x，y）如果有，我们就输出他的值
###### 那么我们是如何输出这样一个值的呢，实际上这涉及到我们的查找方式，如果我们通过dfs后续遍历查找一个值y，并且我们找到它就将它标记为已找到，那么当我们找到一个结点u时，如果我们找到结点u时发现结点y和x都已经找到了，结点u就是他们两个的公共父节点
###### 而找到这样一个结点u，我们就用到了并查集，下面代码有解析:
``` cpp  
#include <bits/stdc++.h>  
using namespace std;  
const int N=500010;  
int h[N],e[N<<1],ne[N<<1],idx;//这个邻接表储存树的结点   
int hs[N],es[N<<1],nes[N<<1],id[N<<1],idxs;//这个邻接表储存树的查询   
int f[N],ans[N];//f是并查集 , ans用来储存所有返回结果   
bool st[N];//用来判断当遍历到x时,y也没有被遍历过   
void add(int a,int b){  
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;  
}  
void adds(int a,int b,int c){  
	  es[idxs]=b,nes[idxs]=hs[a],id[idxs]=c,hs[a]=idxs++;  
}  
int find(int x){//并查集找根结点   
	return f[x]==x?x:find(f[x]);  
}  
void tarjan(int u){  
	st[u]=true;    
	for(int i=h[u];~i;i=ne[i]){
		int y=e[i];  
		if(!st[y]){  
			tarjan(y);//遍历子节点   
			f[y]=u;//合并并查集:把子节点y合并到父节点x上   
		}  
	}//通过这一步就建立了一个所有的y能够走到x的集合   
	for(int i=hs[u];~i;i=nes[i]){  
		int y=es[i];  
		if(st[y]){  
			ans[id[i]]=find(y);  
		}  
	}  
}   
int main(){   
	int n,m,root;  
	cin>>n>>m>>root;  
	memset(h,-1,sizeof h);  
	memset(hs,-1,sizeof hs);  
	for(int i=1;i<n;i++){  
		f[i]=i;//初始时每个结点是独立的  
		int a,b; scanf("%d%d",&a,&b);  
		add(a,b);add(b,a);   
	}  
	f[n]=n;//把没有被初始化的最后一个结点初始化  
	for(int i=1;i<=m;i++){  
		int a,b; scanf("%d%d",&a,&b)  ;
		adds(a,b,i);adds(b,a,i);//i代表他是第几个被读入的数据,方便存入ans数组中   
	}  
	tarjan(root);//本质是一个递归,处理出所有的结果,从根节点后续遍历整个树  
	for(int i=1;i<=m;i++) cout<<ans[i]<<endl;   
}    
``` ```