[算法总结] LCA倍增法 dfs

步骤

• 预处理 出 每个的2^j 的祖先
• 将两个点 移到同一位置
• 倍增从大到小的跳跃

模板

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;
const int N = 5e5+10 ;
int fa[N][31];//表示x这个点走到了2^k的点
int n,m;
int dep[N];
vector g[N];
// int cost[N][31];  代价数组 可以用于最短路径查询
void dfs(int u,int father){
	fa[u][0] = father;// u往上走1位,那么就是他的父亲节点
	dep[u] = dep[fa[u][0]] + 1; //深度为父节点+1

	//第2^i 的祖先节点 是 第2^(i-1)的祖先节点的 2^(i-1)的祖先节点
	//节点从 小到大 1 2 3 4 5 也就是从树根倒叶子
	for(int i = 1; i dep[y]) swap(x,y);
	//令y的深度大于x

	int temp = dep[y] - dep[x];
	int ans =0  ;

	//将这个差进行二进制拆分
	for(int j = 0 ; temp ; ++j , temp >>=1){
		if(temp&1){
// 		ans+=cost[y][i]
			y =  fa[y][j];
		}
	}

	//如果 他们就是他们自己的祖先
	if(y == x) return y;

	for(int j= 30; j>= 0  && y!=x ;  -- j){
		if(fa[x][j]!=fa[y][j]){
// 			ans+= cost[x][y] + cost[y][j]
			x = fa[x][j];
			y = fa[y][j];
		}
	}
// 	ans+=cost[x][0]+cost[y][0]
	return fa[y][0];
}

void solve(){
	cin>>n;
	int s = 0 ;

	for(int i=1;i>a>>b;
		if(b== -1){
			s = a;
			continue;
		}
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(s,0);
	cin>>m;
	for(int i=1;i>a>>b;
		int lcaa = lca(a,b);
		if(lcaa == a)cout