poj1330LCA问题

裸的求最近公共祖先问题，其中poj另一个同类型的题目输入操作相当变态无聊，就拿这道题备用模板吧。 思路：先是一遍从根节点的深度优先搜索，记录些有用的信息（感觉描述起来好麻烦，不展开了，看了以下核心思想，再画画图就能看出来）。然后对信息进行一遍RMQ预处理（Nlog（N）的复杂度）。然后剩下的就是O（1）复杂度的访问随意两点的公共祖先了。

先定义一个访问顺序的概念：每个节点的访问顺序是指第一次访问到这个节点时候的排名（再翻译一下：a节点的访问顺序就是：在所有的第一次访问到每个节点的排名中，a节点是第几个先被访问到的（累死了，我的语文真得好好再学学了））；

再核心部分：要查的两个节点a，b的LCA在深度优先搜索时一定会出现在第一次访问到a和第一次访问到b的时间之间（注意：深搜回溯到某节点时也算访问一次此节点，一节点可以被访问多次）。而且在这之间a，b的LCA的访问顺序肯定是最小的。所以只需要在RMQ预处理以后，找到第一次访问到a和第一次访问到b的时间之间的最小访问顺序的节点，那就是他们的LCA了。

代码：

#include <iostream>
#include <vector>
#include <stdio.h>
#include <cstring>
#include <cmath>

using namespace std;
vector<int> vec[30910];
int rem[39100];
int tool[39010];
int firsttouch[30910];
int firstposition[30910];
int number[50000];
int rmq[50100][25];
int change[30910];
int goal1,goal2;
int tree;
int ans;
int help=0;
int touch=1;
int n;
int pow(int k)
{
    int an=1;
    int x=2;
    while(k>0)
    {
        if(k&1)
        an*=x;
        x*=x;
        k/=2;
    }
    return an;
}
void dfs(int k)
{
   // if(help>20000)
      // return ;
    firsttouch[k]=touch;
    change[touch]=k;
    touch++;
    number[++help]=k;
    firstposition[k]=help;
    for(int i=0;i<vec[k].size();i++)
    {
        dfs(vec[k][i]);
        number[++help]=k;
    }
}

void pretreat()
{
     for(int j=1;j<=help;j++)
     rmq[j][0]=firsttouch[number[j]];
    for(int i=1;pow(i)<=help;i++)
    {
        for(int j=1;j<=help;j++)
        {
            if(j+pow(i-1)>help)
            {
            rmq[j][i]=rmq[j][i-1];
            }
            else
            {
            rmq[j][i]=min(rmq[j][i-1],rmq[j+pow(i-1)][i-1]);
            }
        }
    }
}

int main()
{
    int N;
    scanf("%d",&N);
   for(int u=0;u<N;u++)
   {
       scanf("%d",&n);
       help=0;
       touch=0;
       for(int i=0;i<10000;i++)
       {
        rem[i]=0;
        tool[i]=0;
        vec[i].clear();
       }
   for(int i=1;i<n;i++)
   {
       int a,b;
       scanf("%d%d",&a,&b);
        vec[a].push_back(b);
        tool[b]++;
   }
   for(int i=1;i<=n;i++)
   if(tool[i]==0)
   {
       tree=i;
       break;
   }
   dfs(tree);
   pretreat();
       scanf("%d%d",&goal1,&goal2);
       if(goal1==goal2)
       {
       rem[goal1]++;
       continue;
       }
       int a=min(firstposition[goal1],firstposition[goal2]);
       int b=max(firstposition[goal1],firstposition[goal2]);
       int h=int(log(double(b-a)*1.0)/log(2.0));
       cout<<change[min(rmq[a][h],rmq[b-pow(h)+1][h])]<<endl;;
   }
    return 0;
}