poj 1330 Nearest Common Ancestors 裸的LCA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 10010
using namespace std;
int dep[N],farther[N],vi[N],sec[N],Md,index[N],e,set[N];
struct Edge{
int to,next;
}edge[N];
void addedge(int from,int to)
{
edge[e].to=to;
edge[e].next=index[from];
index[from]=e++;
}
void dfs(int u)
{
int i,now;
for(i=index[u];i!=-;i=edge[i].next)
{
now=edge[i].to;
dep[now]=dep[u]+;
farther[now]=u;
dfs(now);
}
Md=max(Md,dep[u]);
}
void make_sec(int u,int Sec)
{
int i,now;//cout<<u<<" "<<Sec<<endl;
if(dep[u]<Sec)
sec[u]=;
else
{
if(dep[u]%Sec==)
sec[u]=farther[u];
else
sec[u]=sec[farther[u]];
}
for(i=index[u];i!=-;i=edge[i].next)
{
now=edge[i].to;
make_sec(now,Sec);
} }
int LCA(int a,int b)
{
while(sec[a]!=sec[b])
{
if(dep[a]>dep[b])
a=sec[a];
else
b=sec[b];
}
while(a!=b)
{
if(dep[a]>dep[b])
a=farther[a];
else
b=farther[b];
}
return a;
}
int find(int x)
{
if(x!=set[x])
set[x]=find(set[x]);
return set[x];
}
void merg(int a,int b)
{
int x,y;
x=find(a);
y=find(b);
set[y]=x;
}
void init()
{
e=;
memset(dep,,sizeof(dep));
memset(sec,,sizeof(sec));
memset(index,-,sizeof(index));
memset(farther,,sizeof(farther));
for(int i=;i<=N;i++)
set[i]=i;
}
int main()
{
int t,i,j,a,b,n;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d",&n);
for(i=;i<n-;i++)
{
scanf("%d%d",&a,&b);
merg(a,b);
addedge(a,b);
}
scanf("%d%d",&a,&b);
dfs(find());
make_sec(find(),sqrt(1.0*Md));//cout<<"ok"<<endl;
printf("%d\n",LCA(a,b));
}
return ;
}
上一篇:UVa 557 (概率 递推) Burger


下一篇:[转] 如何让CloudStack使用KVM创建Windows实例成功识别并挂载数据盘