HDU 5266 pog loves szh III （LAC）

問題描述

pog在與szh玩遊戲，首先pog在紙上畫了一棵有根樹，這裡我們定義1為這棵樹的根，然後szh在這棵樹中選了若幹個點，想讓pog幫忙找找這些點的最近公共祖先在哪裡，一個點為S的最近公共祖先當且僅當以該點為根的子樹包含S中的所有點，且該點深度最大。然而，這個問題是十分困難的，出于szh對pog的愛，他決定隻找編号連續的點，即
  
   l i  
  

~
  
   r i  
  

。      

輸入描述

若幹組資料(不超過
  
   3 
  

組
  
   n≥10000 
  

或
  
   Q≥10000 
  

)。
每組資料第一行一個整數
  
   n(1≤n≤300000) 
  

，表示樹的節點個數。
接下來
  
   n−1 
  

行，每行兩個數
  
   A i ，B i  
  

，表示存在一條邊連接配接這兩個節點。
接下來一行一個數
  
   Q(1≤Q≤300000) 
  

，表示有
  
   Q 
  

組詢問。
接下來Q行每行兩個數
  
   l i ,r i (1≤li≤ri≤n) 
  

，表示詢問編号為
  
   l i  
  

~
  
   r i  
  

的點的最近公共祖先。
      

輸出描述

對于每組的每個詢問，輸出一行，表示編号為li~ri的點的最近公共祖先的編号。      

輸入樣例

5
1 2
1 3
3 4
4 5
5
1 2
2 3
3 4
3 5
1 5
      

輸出樣例

1
1
3
3
1
      

思路：

做這題的方法有很多。下面給出2種解法。
1：維護一個跳表，表示編号為
   
    i 
   ~
   
    i+2 j −1 
   的LCA，注意在這裡求LCA必須用
   
    O(1) 
   的做法才能通過所有資料。可以轉換為RMQ，每次查詢時隻需查詢兩個數的LCA即可。
2：考慮dfs序，通過在簡單的證明可知L~R的LCA為
   
    L 
   ~
   
    R 
   中dfs序較小的那個位置與dfs序較大的那個位置的LCA。是以隻要通過st表處理L~R最大dfs序與最小dfs序的編号即可。

      

方法一：      

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
const int N = 300000+1000;
int Q,n;
int head[N];
struct Edge
{
    int v,nxt;
}es[N<<1];
int cnt;

inline void add_edge(int u,int v)
{
    es[cnt].v=v;
    es[cnt].nxt=head[u];
    head[u]=cnt++;
    es[cnt].v=u;
    es[cnt].nxt=head[v];
    head[v]=cnt++;
}

int index;
int vs[N*2],id[N],dep[N];
int lca[N*2][20];
int minn[N][20];
int maxn[N][20];
void dfs(int u,int fa,int h)
{
    id[u]=++index;
    vs[index]=u;
    dep[u]=h;
    for(int i=head[u];~i;i=es[i].nxt)
    {
        int v=es[i].v;
        if(v==fa)continue;
        dfs(v,u,h+1);
        vs[++index]=u;
    }
}

int mm[2*N+100];
void ini()
{
    memset(head,-1,sizeof(head));
    cnt=index=0;
}
int main()
{
    mm[0]=-1;
    for(int i=1;i<=2*N;i++) mm[i]= (((i-1)&i)==0)? mm[i-1]+1:mm[i-1];
    while(~scanf("%d",&n))
    {
        ini();
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge(u,v);
        }
        dfs(1,1,0);
        for(int i=1;i<=index;i++) lca[i][0]=vs[i];
        for(int j=1;j<=20;j++)
            for(int i=1;i+(1<<j)-1<=index;i++)
            {
                int a=lca[i][j-1],b=lca[i+(1<<(j-1))][j-1];
                lca[i][j] = dep[a]<dep[b] ? a:b;
            }
        for(int i=1;i<=n;i++) minn[i][0]=maxn[i][0]=id[i];
        for(int j=1;j<=20;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
            {
                minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
                maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]);
            }

        scanf("%d",&Q);
        for(int i=1;i<=Q;i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            int k=mm[r-l+1];
            int L=min(minn[l][k],minn[r-(1<<k)+1][k]);
            int R=max(maxn[l][k],maxn[r-(1<<k)+1][k]);
            k=mm[R-L+1];
            int a=lca[L][k],b=lca[R-(1<<k)+1][k];
            int ans = dep[a]<dep[b]? a:b;
            printf("%d\n",ans);

        }
    }
    return 0;
}
           
   

方法二：（防止爆棧就換成bfs）      

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N = 300000+1000;
const int DEG  = 20;
int Q,n;
int pa[N][20];
int dep[N];
int head[N];
struct Edge
{
    int v,nxt;
}es[N<<1];
int cnt;
inline void add_edge(int u,int v)
{
    es[cnt].v=v;
    es[cnt].nxt=head[u];
    head[u]=cnt++;
    es[cnt].v=u;
    es[cnt].nxt=head[v];
    head[v]=cnt++;
}
/*
void bfs(int root)
{
    queue<int>q;
    dep[root]=0;
    pa[root][0]=root;
    q.push(root);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=1;i<DEG;i++)
            pa[u][i]=pa[pa[u][i-1]][i-1];
        for(int i=head[u];~i;i=es[i].nxt)
        {
            int v=es[i].v;
            if(v==pa[u][0]) continue;
            pa[v][0]=u;
            dep[v]=dep[u]+1;
            q.push(v);
        }
    }
}
*/
void dfs(int u,int fa,int h)
{
    dep[u]=h;
    pa[u][0]=fa;
    for(int i=1;i<DEG;i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for(int i=head[u];~i;i=es[i].nxt)
    {
        int v=es[i].v;
        if(v!=fa) dfs(v,u,h+1);
    }
}
int dp[N][20];
int LCA(int u,int v)
{
    if(dep[u]>dep[v]) swap(u,v);
    for(int det=dep[v]-dep[u],i=0;det;det>>=1,i++)
        if(det&1) v=pa[v][i];
    if(u==v) return u;
    for(int i=DEG-1;i>=0;i--)
        if(pa[u][i]!=pa[v][i]) v=pa[v][i],u=pa[u][i];
    return pa[u][0];
}
int mm[N];
void ini()
{
    memset(head,-1,sizeof(head));
    cnt=0;
}
int main()
{
    mm[0]=-1;
    for(int i=1;i<=N-1;i++)mm[i]= (((i-1)&i)==0)? mm[i-1]+1:mm[i-1];
    while(~scanf("%d",&n))
    {
        ini();
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge(u,v);
        }
        dfs(1,1,0);
        for(int i=1;i<=n;i++) dp[i][0]=i;
        for(int j=1;j<=20;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
                dp[i][j]=LCA(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);

        scanf("%d",&Q);
        for(int i=1;i<=Q;i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            int k=mm[r-l+1];
            int ans=LCA(dp[l][k],dp[r-(1<<k)+1][k]);
            printf("%d\n",ans);
        }
    }
    return 0;

}