版权声明：本文为博主原创文章，未经博主同意不得转载。

https://blog.csdn.net/u013912596/article/details/35311489

题目链接：http://poj.org/problem?id=1470

题目大意：给出一棵树。再给出若干组数（a，b），输出节点a和节点b的近期公共祖先（LCA）

就是非常裸的LCA。可是我用的是《挑战程序设计竞赛》上的“基于二分搜索的算法求LCA”，我看网上用的都是tarjan算法。可是我的代码不知道为什么提交上去 wrong answer，自己想的非常多測试数据也都和题解结果一样，不知道错在哪里，所以把代码保存一下。留待以后解决。。。。

。。

假设读者有什么建议。希望提出来。感激不尽！

#include <iostream>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define N 911

#define LOG_N 11

int times[N];

bool findroot[N];

#include <vector>

vector<int> g[N];//

int root;

int parent[LOG_N][N];

int depth[N];

void dfs(int v,int p,int d)

{

    parent[0][v]=p;

    depth[v]=d;

    for(int i=0;i<g[v].size();i++)

    {

        if(g[v][i]!=p) dfs(g[v][i],v,d+1);

    }

}

//预处理

void init(int V)//预处理出parent

{

    dfs(root,-1,0);

    for(int k=0;k+1<LOG_N;k++)

    {

        for(int v=1;v<=V;v++)

        {

            if(parent[k][v]<0) parent[k+1][v]=-1;

            else parent[k+1][v]=parent[k][parent[k][v]];

        }

    }

}

//计算u和v的LCA

int lca(int u,int v)

{

    //让u和v向上走到同一深度

    if(depth[u]>depth[v]) swap(u,v);

    for(int k=0;k<LOG_N;k++)

    {

        if((depth[v]-depth[u])>>k&1)

        {

            v=parent[k][v];

        }

    }

    if(u==v) return u;

    //利用二分搜索计算LCA

    for(int k=LOG_N-1;k>=0;k--)

    {

        if(parent[k][u]!=parent[k][v])

        {

            u=parent[k][u];

            v=parent[k][v];

        }

    }

    return parent[0][u];

}

int main()

{

    freopen("D:/in.txt","r",stdin);

    int n,t,a;

    while(~scanf("%d",&n))

    {

        char ch1[2],ch2[2];//吸收掉那个可恶的括号什么的东西

        memset(times,0,sizeof(times));

        memset(parent,0,sizeof(parent));

        memset(depth,0,sizeof(depth));

        memset(findroot,0,sizeof(findroot));

        for(int i=1;i<=N;i++)

            g[i].clear();

        for(int i=0;i<n;i++)

        {

            scanf("%d:(%d)",&a,&t);

            for(int j=0;j<t;j++)

            {

                int temp;

                scanf("%d",&temp);

                g[a].push_back(temp);

                findroot[temp]=true;

            }

        }

        for(int i=1;i<=n;i++)

            if(!findroot[i])

            {

                root=i;

                break;

            }

        init(n);

        int qn,fir,sec;

        scanf("%d",&qn);

        for(int i=0;i<qn;i++)

        {

            scanf("%1s%d%d%1s)",ch1,&fir,&sec,ch2);

            times[lca(fir,sec)]++;

        }

        for(int i=1;i<=n;i++)

        {

            if(times[i])

                printf("%d:%d\n",i,times[i]);

        }

        printf("\n");

    }

    return 0;

}