Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 第一次将lca转化为rmq,庆祝一下

Posted by mountainhigh at 2011-06-16 11:48:46 on Problem 1330
```#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int maxn=10010;
bool visit[maxn];
int t,n,cnt,top,_N,f[maxn<<1],d[maxn<<1],p[maxn<<1],next[maxn<<1],h[maxn]={0};
int data[maxn<<1],cou,Log2[maxn<<1],RMQ[19][maxn<<1];
int stack[maxn],num[maxn];
/*struct edgetype
{
int value;
}edge[maxn];*/
{
next[++cnt]=h[x];
h[x]=cnt;
data[cnt]=y;
}
void dfs(int root)
{
int x,z,y;
stack[top=1]=root;
cou=0;
cnt=1;
//num[root]=1;
p[0]=-1;
while(top)
{
x=stack[top];
cou++;
if(p[x]==0)p[x]=cou;
d[cou]=top-1;
f[cou]=x;
for(z=h[x];z;z=next[z])
if(p[y=data[z]]==0)
{
//num[y]=++cnt;
stack[++top]=y;
break;
}
if(z)continue;
top--;
}
_N=cou;
}
void initrmq()
{
int i,j,x1,x2,l;
for(Log2[0]=-1,i=1;i<=_N;i++)
{
Log2[i]=(i&(i-1))==0?Log2[i-1]+1:Log2[i-1];
RMQ[0][i]=i;
}
for(j=1,l=2;j<=Log2[_N];l<<=1,j++)
for(i=1;i+l-1<=_N;i++)
{
x1=RMQ[j-1][i];x2=RMQ[j-1][i+(l>>1)];
RMQ[j][i]=d[x1]<d[x2]?x1:x2;
}
}
int solve(int aa,int bb)
{
int x,y,x1,x2,lca,k;
x=p[aa];
y=p[bb];
if(x>y)swap(x,y);
k=Log2[y-x+1];
x1=RMQ[k][x];x2=RMQ[k][y-(1<<k)+1];
lca=f[d[x1]<d[x2]?x1:x2];
return lca;
}
int main()
{
int i,j,x,y;
cin>>t;
while(t--)
{
cin>>n;
cnt=1;
memset(visit,true,sizeof(visit));
memset(h,0,sizeof(h));
memset(RMQ,0,sizeof(RMQ));
memset(p,0,sizeof(p));
memset(d,0,sizeof(d));
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
visit[y]=false;
}
for(i=1;i<=n;i++)
{
if(visit[i])
{
dfs(i);
break;
}
}
initrmq();
cin>>x>>y;
printf("%d\n",solve(x,y));
}
return 0;
}```

Followed by: