11.21学习小结 //LCA

倍增求LCA

参考博文：https://www.cnblogs.com/hulean/p/11144059.html
参考博文：https://www.cnblogs.com/jvxie/p/4854719.html
· 记录每个点的深度，和往前2^i的祖先。
· 先把两个点提到同一高度，再统一开始跳。不可以直接跳到相同祖先处，因为可能是LCA的祖先
· 裸板子：洛谷P3379
waring：祖先是在dfs里面更新的

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
vector<int>e[MAXN];
int dep[MAXN];
int vis[MAXN];
int fa[MAXN][25];
void dfs(int x){
	vis[x]=1;
	for(auto i:e[x]){
		if(vis[i])continue;
		dep[i]=dep[x]+1;
		fa[i][0]=x;
		for(int j=1;(1<<j)<=dep[i];j++){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
		dfs(i);
	}
}
void lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int j=20;j>=0;j--){
		if((1<<j)>dep[u]-dep[v])continue;
		u=fa[u][j];
	}
	if(u==v){
		cout<<u<<endl;
		return;
	}
	for(int j=20;j>=0;j--){
		if((1<<j)>dep[u])continue;
		if(fa[u][j]==fa[v][j])continue;
		u=fa[u][j];v=fa[v][j];
	}
	cout<<fa[u][0]<<endl;
}
int main(){
	int n,m,root;
	cin>>n>>m>>root;
	int u,v;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dep[root]=0;
	fa[root][0]=root;
	dfs(root);
	while(m--){
		cin>>u>>v;
		lca(u,v);
	}
	return 0;
} 

·洛谷P5836
waring:记录本身颜色！！！

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
vector<int>e[MAXN];
int dep[MAXN];
int vis[MAXN];
int cl[MAXN];
int fa[MAXN][25][3];
void dfs(int x){
	vis[x]=1;
	for(auto i:e[x]){
		if(vis[i])continue;
		dep[i]=dep[x]+1;
		fa[i][0][0]=x;
		fa[i][0][1]=cl[x]==1;
		fa[i][0][2]=cl[x]==2; 
		for(int j=1;(1<<j)<=dep[i];j++){
			fa[i][j][0]=fa[fa[i][j-1][0]][j-1][0];
			fa[i][j][1]=fa[i][j-1][1]||fa[fa[i][j-1][0]][j-1][1];
			fa[i][j][2]=fa[i][j-1][2]||fa[fa[i][j-1][0]][j-1][2];
		}
		dfs(i);
	}
}
bool lca(int u,int v,int k){
	int ck=0;
	if(cl[u] == k || cl[v] == k)return true;
	if(dep[u]<dep[v])swap(u,v);
	for(int j=20;j>=0;j--){
		if((1<<j)>dep[u]-dep[v])continue;
		if(fa[u][j][k]==1){
			ck=1;
			return ck;
		}
		u=fa[u][j][0];
	}
	if(u==v){
		if(cl[u]==k)ck=1;
		return ck;
	}
	for(int j=20;j>=0;j--){
		if((1<<j)>dep[u])continue;
		if(fa[u][j][0]==fa[v][j][0])continue;
		if(fa[u][j][k] || fa[v][j][k]){
			ck=1;
			return ck;
		}
		u=fa[u][j][0],v=fa[v][j][0];
	}
	if(cl[fa[u][0][0]]==k)ck=1;
	return ck; 
}
int main(){
	int n,m;
	cin>>n>>m;
	int u,v;
	char c;
	for(int i=1;i<=n;i++){
		cin>>c;
		if(c=='G')cl[i]=1;
		else cl[i]=2;
	}
	for(int i=1;i<=n-1;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	int root=1;
	dep[root]=0;
	fa[root][0][0]=root;
	dfs(root);
//	
//	for(int i=1;i<=n;i++){
//		for(int j=0;(1<<j)<=dep[i];j++){
//			for(int k=0;k<=2;k++){
//				cout<<fa[i][j][k];
//			}
//			cout<<endl;
//		} 
//		cout<<endl;
//	}
//	
	while(m--){
		cin>>u>>v>>c;
		if(c=='G')cout<<lca(u,v,1);
		else cout<<lca(u,v,2);
	}
	return 0;
}