Input
Output
Example
| input | output |
|---|---|
7 1 2 1 3 2 4 2 5 2 6 3 7 3 4 6 3 4 5 7 |
2 1 1 |
7 1 3 3 5 5 6 7 5 1 4 2 4 3 4 5 5 6 6 7 |
1 5 5 |
题意就不描述了，是个水题，预处理出i和i+1的lca，然后询问的时候跑线段树就行，这里线段树用到了寻找区间中最小的点的位置，存一下。
懒得改非递归，要手动开栈。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 200010
int n,m;
int v[N<<1],__next[N<<1],first[N],e;
void AddEdge(int U,int V)
{
v[++e]=V;
__next[e]=first[U];
first[U]=e;
}
int fa[N],dep[N],top[N],son[N],siz[N],tot;
void dfs(int U)
{
siz[U]=1;
for(int i=first[U];i;i=__next[i])
if(v[i]!=fa[U])
{
fa[v[i]]=U;
dep[v[i]]=dep[U]+1;
dfs(v[i]);
siz[U]+=siz[v[i]];
if(siz[v[i]]>siz[son[U]])
son[U]=v[i];
}
}
void df2(int U)
{
if(son[U])
{
top[son[U]]=top[U];
df2(son[U]);
}
for(int i=first[U];i;i=__next[i])
if(v[i]!=fa[U]&&v[i]!=son[U])
{
top[v[i]]=v[i];
df2(v[i]);
}
}
int lca(int U,int V)
{
while(top[U]!=top[V])
{
if(dep[top[U]]<dep[top[V]])
swap(U,V);
U=fa[top[U]];
}
if(dep[U]>dep[V])
swap(U,V);
return U;
}
int minv[N<<2];
void update(int p,int v,int rt,int l,int r)
{
if(l==r)
{
minv[rt]=v;
return;
}
int m=(l+r>>1);
if(p<=m) update(p,v,rt<<1,l,m);
else update(p,v,rt<<1|1,m+1,r);
minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);
}
int lcas[N];
int query(int ql,int qr,int rt,int l,int r)
{
if(ql<=l&&r<=qr) return minv[rt];
int m=(l+r>>1),res=2147483647;
if(ql<=m) res=min(res,query(ql,qr,rt<<1,l,m));
if(m<qr) res=min(res,query(ql,qr,rt<<1|1,m+1,r));
return res;
}
int Find2(int v,int rt,int l,int r)
{
if(l==r) return l;
int m=(l+r>>1);
if(minv[rt<<1]==v) return Find2(v,rt<<1,l,m);
else return Find2(v,rt<<1|1,m+1,r);
}
int Findp(int ql,int qr,int v,int rt,int l,int r)
{
if(ql<=l&&r<=qr)
{
if(minv[rt]==v)
return Find2(v,rt,l,r);
return -1;
}
int m=(l+r>>1);
if(ql<=m)
{
int tmp=Findp(ql,qr,v,rt<<1,l,m);
if(tmp!=-1) return tmp;
}
return Findp(ql,qr,v,rt<<1|1,m+1,r);
}
int main()
{
// freopen("j.in","r",stdin);
int x,y;
scanf("%d",&n);
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
AddEdge(x,y);
AddEdge(y,x);
}
top[1]=1;
dfs(1);
df2(1);
for(int i=1;i<n;++i)
{
lcas[i]=lca(i,i+1);
update(i,dep[lcas[i]],1,1,n-1);
}
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
if(x==y)
printf("%d\n",x);
else
printf("%d\n",lcas[Findp(x,y-1,query(x,y-1,1,1,n-1),1,1,n-1)]);
}
return 0;
}
【最近公共祖先】【线段树】URAL - 2109 - Tourism on Mars
原文：http://www.cnblogs.com/autsky-jadek/p/6337636.html