#1069 : 最近公共祖先·三（LCA在线）

1.HDU 2586 How far away

#include"iostream"
#include"string.h"
#include"vector"
#include"map"
using namespace std;
const int maxn=1e5+5;
int N,M,tot,cnt;
int dp[maxn][32];
int First[maxn],a[maxn],dep[maxn];
int Fa[maxn];
map<string,int> mp;
map<int,string> name;
int head[maxn];
int geshu;
struct Edge
{
    int t,next;
};
Edge E[maxn<<1];
void AddEdge(int aa,int bb)
{
    E[++tot].t=bb;
    E[tot].next=head[aa];
    head[aa]=tot;
}
int vis[maxn];
void dfs(int u,int deep)
{
    vis[u]=1;
    a[++cnt]=u;
    First[u]=cnt;
    dep[cnt]=deep;
    for(int i=head[u];i!=-1;i=E[i].next)
    {
        int t=E[i].t;
        if(vis[t])continue;
        dfs(t,deep+1);
        a[++cnt]=u;
        dep[cnt]=deep;
    }
}
void ST()
{
    for(int i=1;i<=cnt;i++)dp[i][0]=i;
    for(int j=1;(1<<j)<=cnt;j++)
    {
        for(int i=1;i+(1<<j)-1<=cnt;i++)
        {
            int a=dp[i][j-1];
            int b=dp[i+(1<<(j-1))][j-1];
            if(dep[a]<=dep[b])dp[i][j]=a;
            else dp[i][j]=b;
        }
    }
}

int RMQ(int L,int R)
{
    int k=0;
    while((1<<(k+1))<=(R-L+1))k++;
    int a=dp[L][k];
    int b=dp[R-(1<<k)+1][k];
    if(dep[a]<=dep[b])return a;
    else return b;
}
void print()
{
    for(int i=1;i<=cnt;i++)cout<<a[i]<<" ";
    cout<<"\n";
    for(int i=1;i<=cnt;i++)cout<<dep[i]<<" ";
    cout<<"\n";
    for(int i=1;i<=cnt;i++)cout<<First[i]<<" ";
    cout<<"\n";
}
int main()
{

    cin>>N;
    mp.clear();
    string s1,s2;
    geshu=tot=cnt=0;
    memset(vis,0,sizeof(vis));
    memset(head,-1,sizeof(head));
    for(int i=1;i<=N;i++)Fa[i]=i;
    for(int i=1;i<=N;i++)
    {
        cin>>s1>>s2;
        if(mp.find(s1)==mp.end())
        {
            mp[s1]=++geshu;
            name[geshu]=s1;
        }
        if(mp.find(s2)==mp.end())
        {
            mp[s2]=++geshu;
            name[geshu]=s2;
        }
        AddEdge(mp[s1],mp[s2]);
        Fa[mp[s2]]=mp[s1];
    }
    int root=1;
    for(int i=1;i<=N;i++)root=Fa[root];
    dfs(root,1);
    ST();
    cin>>M;
    for(int i=1;i<=M;i++)
    {
        cin>>s1>>s2;
        int L=First[mp[s1]];
        int R=First[mp[s2]];
        if(L>R)swap(L,R);
        int ans=RMQ(L,R);
        cout<<name[a[ans]]<<"\n";
    }
}

LCA（在线模板）
原题：poj1330

#include"iostream"
#include"cstring"
using namespace std;
const int maxn=25000;
int N,Q;
int dp[maxn][20];//保存cnt节点区间里深度最小的节点
struct Edge
{
    int t,next;
};
Edge E[maxn];
int head[maxn],tot;
int dep[maxn];
int First[maxn];
int cnt;//遍历的第cnt个节点
int id[maxn];//第cnt个节点是原来树上的第几个
void AddEdge(int aa,int bb)
{
    E[++tot].t=bb;
    E[tot].next=head[aa];
    head[aa]=tot;
}
void dfs(int u,int deep)
{
    id[++cnt]=u;
    First[u]=cnt;
    dep[cnt]=deep;
    dp[cnt][0]=cnt;
    //虽然先输入的节点后访问，但是整个都是有序的，不是乱的
    for(int i=head[u];i!=-1;i=E[i].next)
    {
        int t=E[i].t;
        dfs(t,deep+1);
        id[++cnt]=u;
        dep[cnt]=deep;
        dp[cnt][0]=cnt;
    }
}
void RMQ_ST()
{
    for(int j=1;(1<<j)<=cnt;j++)
    {
        for(int i=1;i+(1<<j)-1<=cnt;i++)
        {
            int cnt1=dp[i][j-1],cnt2=dp[i+(1<<(j-1))][j-1];
            if(dep[cnt1]<dep[cnt2])dp[i][j]=cnt1;
            else dp[i][j]=cnt2;
        }
    }
}
int query(int L,int R)
{
    L=First[L];
    R=First[R];
    if(L>R)swap(L,R);//有可能L>R
    int k=0;
    while(1<<(k+1)<(R-L+1))k++;
    int cnt1=dp[L][k],cnt2=dp[R-(1<<k)+1][k];
    if(dep[cnt1]<dep[cnt2])return id[cnt1];
    else return id[cnt2];
}
void printid(int L,int R)
{
    for(int i=L;i<=R;i++)cout<<id[i]<<" ";
    cout<<"\n";
    for(int i=L;i<=R;i++)cout<<dep[i]<<" ";
    cout<<"\n\n";
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>N;
        tot=0;
        cnt=0;
        memset(head,-1,sizeof(head));
        int fa[maxn];
        for(int i=1;i<=N;i++)fa[i]=i;
        for(int i=1;i<N;i++)
        {
            int t1,t2;
            cin>>t1>>t2;
            AddEdge(t1,t2);
            fa[t2]=t1;
        }
        int root=N;
        while(fa[root]!=root)root=fa[root];
        dfs(root,1);
        RMQ_ST();
        int u1,u2;
        cin>>u1>>u2;
        cout<<query(u1,u2)<<endl;

    }
}