@zzzc18
2017-05-12T20:12:36.000000Z
字数 2071
阅读 1083
LCA
#include<cstdio>
#include<cmath>
#define MAXN 700000+900
#define MAXM 1200000+900
using namespace std;
int anc[MAXN][33];
int n,m,root;
struct E{
int next,to;
}edge[MAXM];
int head[MAXN],edge_num;
int depth[MAXN];
int logn;
void SWAP(int &x,int &y){
int t=x;x=y;y=t;
}
void addedge(int x,int y){
edge[++edge_num].next=head[x];
edge[edge_num].to=y;
head[x]=edge_num;
}
void DFS(const int &x,const int &y){
int i;
for(i=head[x];i;i=edge[i].next){
if(edge[i].to!=y){
anc[edge[i].to][0]=x;
depth[edge[i].to]=depth[x]+1;
DFS(edge[i].to,x);
}
}
}
void PRE(){
int i,j;
for(i=1;(1<<i)<=n;i++){
for(j=1;j<=n;j++){
if(anc[j][i-1]){
anc[j][i]=anc[anc[j][i-1]][i-1];
}
}
}
}
int LCA(int x,int y){
if(depth[x]<depth[y])
SWAP(x,y);
int i,j;
for(i=logn;i>=0;i--){
if(depth[y]+(1<<i)<=depth[x])
x=anc[x][i];
}
if(x==y) return x;
for(i=logn;i>=0;i--){
if(anc[x][i] && anc[x][i]!=anc[y][i]){
x=anc[x][i];y=anc[y][i];
}
}
return anc[x][0];
}
int main(){
scanf("%d%d%d",&n,&m,&root);
int i;int a,b;
for(i=1;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);addedge(b,a);
}
DFS(root,0);
PRE();
logn=floor(log(n)/log(2));
for(i=1;i<=m;i++){
scanf("%d%d",&a,&b);
printf("%d\n",LCA(a,b));
}
return 0;
}
方法:DFS,从最下层把节点加入并查集,如果询问的两个端点都出现在并查集中(首次),就可以记录答案啦,就是并查集中的fa
#include<cstdio>
#include<algorithm>
#define MAXN 600000
using namespace std;
struct E{
int next,to,id;
}edge[2*MAXN],ask[2*MAXN];
int head[MAXN],edge_num,h1[MAXN],a_num;
int root;
bool vis[MAXN];
int fa[MAXN];
int ans[MAXN];
int n,m;
void addedge(int x,int y){
edge[++edge_num].next=head[x];
edge[edge_num].to=y;
head[x]=edge_num;
}
void addask(int x,int y,int z){
ask[++a_num].next=h1[x];
ask[a_num].to=y;
ask[a_num].id=z;
h1[x]=a_num;
}
int Find(int x){
if(fa[x]!=x) fa[x]=Find(fa[x]);
return fa[x];
}
void LCA(int x){
int i;
vis[x]=1;
for(i=head[x];i;i=edge[i].next){
if(!vis[edge[i].to])
LCA(edge[i].to),fa[edge[i].to]=x;
}
for(i=h1[x];i;i=ask[i].next){
if(vis[ask[i].to])
ans[ask[i].id]=Find(ask[i].to);
}
}
int main(){
scanf("%d%d%d",&n,&m,&root);
int i;int a,b;
for(i=1;i<=n-1;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
for(i=1;i<=m;i++){
scanf("%d%d",&a,&b);
addask(a,b,i);addask(b,a,i);
}
for(i=1;i<=n;i++)
fa[i]=i;
LCA(root);
for(i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}