倍增求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;
}