hdu 5266 pog loves szh III(LCA)

題意：求編号l-r的lca。

做法：第一種方法是維護一個類似rmq的東西，因為abcd的lca，可以由ab的lca和cd的lca的lca得到，然後重疊也沒有關系，就比如剛才的例子，abcd的lca也可以由abc的lca和bcd的lca的lca得到，是以我們用類似rmq的查詢的就可以了。查詢2個點的lca寫的是樹上倍增。

第二種方法比較容易想到，就是先dfs一遍找出歐拉序列，然後再rmq預處理一遍，因為2個點的lca就是歐拉序列中2點之間深度最淺的位置，同時還要rmq預處理那些編号在歐拉序列中的位置區間最小最大值。這樣對于一個查詢來說我們找出在歐拉序列中最小及最大的位置，再查lca即可。處理出歐拉序列再rmq記憶體用的真心多。。

AC代碼1：

#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<ctype.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<string.h>
#include<string>
#include<sstream>
#include<bitset>
using namespace std;
#define ll __int64
#define ull unsigned __int64
#define eps 1e-8
#define NMAX 30000
#define MOD 1000000007
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI acos(-1)
template<class T>
inline void scan_d(T &ret)
{
    char c;
    int flag = 0;
    ret=0;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c == '-')
    {
        flag = 1;
        c = getchar();
    }
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
    if(flag) ret = -ret;
}
const int maxn = 3e5+5;
struct Edge
{
    int v,next;
}e[maxn<<1];
int head[maxn],nct;

void add_edge(int u, int v)
{
    e[nct].v = v; e[nct].next = head[u];
    head[u] = nct++;
}
int _log[maxn*2],tot;

int euler[maxn*2],depth[maxn],pos[maxn];

void dfs(int u, int fa, int dep)
{
    pos[u] = ++tot;
    euler[tot] = u;
    depth[u] = dep;
    for(int i = head[u]; ~i; i = e[i].next)
    {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v,u,dep+1);
        euler[++tot] = u;
    }
}

int lca[maxn*2][20];
int mi[maxn][20],mx[maxn][20];
void init(int n)
{
    for(int i = 1; i <= 2*n-1; i++)
        lca[i][0] = euler[i];
    for(int j = 1; j <= _log[2*n-1]; j++)
        for(int i = 1; i+(1<<j)-1 <= 2*n-1; i++)
        {
            if(depth[lca[i][j-1]] < depth[lca[i+(1<<(j-1))][j-1]]) lca[i][j] = lca[i][j-1];
            else lca[i][j] = lca[i+(1<<(j-1))][j-1];
        }
    for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = pos[i];
    for(int j = 1; j <= _log[n]; j++)
        for(int i = 1; i+(1<<j)-1 <= n; i++)
        {
            mi[i][j] = min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
            mx[i][j] = max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
}

int getlca(int L, int R)
{
    int k = _log[R-L+1];
    if(depth[lca[L][k]] < depth[lca[R-(1<<k)+1][k]]) return lca[L][k];
    return lca[R-(1<<k)+1][k];
}

int main()
{
#ifdef GLQ
    freopen("input.txt","r",stdin);
//    freopen("o.txt","r",stdin);
#endif
    _log[1] = 0;
    for(int i = 2; i <= 2*maxn; i++) if(i&(i-1)) _log[i] = _log[i-1]; else _log[i] = _log[i-1]+1;
    int n;
    while(~scanf("%d",&n))
    {
        memset(head,-1,sizeof(head));
        nct = tot = 0;
        for(int i = 1; i < n; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge(u,v);
            add_edge(v,u);
        }
        dfs(1,1,1);
        init(n);
        int q;
        scanf("%d",&q);
        while(q--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int k = _log[y-x+1];
            int t1 = min(mi[x][k],mi[y-(1<<k)+1][k]),t2 = max(mx[x][k],mx[y-(1<<k)+1][k]);
            printf("%d\n",getlca(t1,t2));
        }
    }
    return 0;
}
           

AC代碼2：

#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<ctype.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<string.h>
#include<string>
#include<sstream>
#include<bitset>
using namespace std;
#define ll __int64
#define ull unsigned __int64
#define eps 1e-8
#define NMAX 30000
#define MOD 1000000007
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI acos(-1)
template<class T>
inline void scan_d(T &ret)
{
    char c;
    int flag = 0;
    ret=0;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c == '-')
    {
        flag = 1;
        c = getchar();
    }
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
    if(flag) ret = -ret;
}
const int maxn = 3e5+10;
struct Edge
{
    int v,next;
}e[maxn<<1];
int head[maxn],nct;

void add_edge(int u, int v)
{
    e[nct].v = v; e[nct].next = head[u];
    head[u] = nct++;
}
int father[maxn][20],depth[maxn];

void dfs(int u, int fa, int dep)
{
    depth[u] = dep;
    for(int i = head[u]; ~i; i = e[i].next)
    {
        int v = e[i].v;
        if(v == fa) continue;
        father[v][0] = u;
        dfs(v,u,dep+1);
    }
}

int lca(int x, int y)
{
    if(depth[x] < depth[y]) swap(x,y);
    int k = depth[x]-depth[y];
    for(int i = 0; i <= 19; i++) if(k&(1<<i))
        x = father[x][i];
    if(x == y) return x;
    for(int i = 19; i >= 0; i--) if(father[x][i] != father[y][i])
    {
        x = father[x][i];
        y = father[y][i];
    }
    return father[x][0];
}

int dp[maxn][20], _log[maxn];

int RMQ(int L, int R)
{
    int k = _log[R-L+1];
    return lca(dp[L][k],dp[R-(1<<k)+1][k]);
}

int main()
{
#ifdef GLQ
    freopen("input.txt","r",stdin);
//    freopen("o.txt","r",stdin);
#endif
    _log[1] = 0;
    for(int i = 2; i <= maxn; i++) if(i&(i-1)) _log[i] = _log[i-1]; else _log[i] = _log[i-1]+1;
    int n;
    while(~scanf("%d",&n))
    {
        memset(head,-1,sizeof(head));
        nct = 0;
        for(int i = 1; i < n; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge(u,v);
            add_edge(v,u);
        }
        dfs(1,1,1);
        for(int i = 1; i <= 19; i++)
            for(int j = 1; j <= n; j++)
                father[j][i] = father[father[j][i-1]][i-1];
        for(int i = 1; i <= n; i++) dp[i][0] = i;
        for(int j = 1; j <= _log[n]; 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]);
        int q;
        scanf("%d",&q);
        while(q--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",RMQ(x,y));
        }
    }
    return 0;
}