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;
}