LCA & RMQ 模板 POJ 1330

就是模板啊。。

这个题用 O（n） 的LCA 也能过，毕竟只有一次查询。

#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include <set>
#include <stack>
#include <list>
using namespace std;

#define READ freopen("acm.in","r",stdin)
#define WRITE freopen("acm.out","w",stdout)
#define ll long long
#define ull unsigned long long 
#define uint unsigned int
#define PII pair<int,int>
#define PDD pair<double,double>
#define fst first
#define sec second
#define MS(x,d) memset(x,d,sizeof(x))
#define INF 0x3f3f3f3f
#define ALL(x) x.begin(),x.end()
#define PB push_back
#define MOD 99991
#define MAX 111111


int cnt,vs[MAX*3],id[MAX],depth[MAX*3];
int pre[MAX];
vector<int> G[MAX];
int d[MAX*3][15];
void dfs(int u,int deep)
{
    cnt++;
    depth[cnt]=deep;
    vs[cnt]=u;
    id[u]=cnt;
    for(int i=0;i<G[u].size();i++)
    {
        dfs(G[u][i],deep+1);
        cnt++;
        depth[cnt]=deep;// 出来的深度是进去前的 deep
        vs[cnt]=u;
    }
}

void RMQ_init()
{
    for(int i=1;i<=cnt;i++)
        d[i][0]=i;
    for(int j=1;(1<<j)<=cnt;j++)
    {
        for(int i=1;i+(1<<j)-1<=cnt;i++)
        {
            int v1=d[i][j-1];
            int v2=d[i+(1<<j-1)][j-1];
            d[i][j]=depth[v1]<depth[v2]?v1:v2;
        }
    }
}

int LCA(int L,int R)
{
    int k=0;
    L=id[L],R=id[R];
    if(L>R)
        swap(L,R);
    while((1<<(k+1))<=R-L+1) k++;
    int v1=d[L][k];
    int v2=d[R-(1<<k)+1][k];
    return depth[v1]<depth[v2]?vs[v1]:vs[v2];
}

int main()
{
    READ;
    int cas;
    scanf("%d",&cas);
    for(int T=1;T<=cas;T++)
    {  
        cnt=0;
        MS(pre,0);
        for(int i=0;i<MAX;i++)
            G[i].clear();
        int n;
        scanf("%d",&n);
        for(int i=1;i<n;i++)
        {
            int p,c;
            scanf("%d%d",&p,&c);
            pre[c]=p;
            G[p].PB(c);
        }
        int root=1;
        while(pre[root]) root=pre[root];
        dfs(root,0);
        RMQ_init();
        int L,R;
        scanf("%d%d",&L,&R);
        cout<<LCA(L,R)<<endl;
    }
    return 0;
}