问题描述：
设计一个算法，对于给定的树中2 结点返回它们的最近公共祖先。

编程任务：
对于给定的树，和树中结点对，编程计算结点对的最近公共祖先。

数据输入：
由文件input.txt给出输入数据。第一行有1个正整数n，表示给定的树有n个顶点，编
号为1，2，…，n。编号为1 的顶点是树根。接下来的n 行中，第i+1 行描述与i 个顶点相关联的子结点的信息。每行的第一个正整数k表示该顶点的儿子结点数。其后k个数中，每1 个数表示1 个儿子结点的编号。当k=0 时表示相应的结点是叶结点。文件的第n+2 行是1 个正整数m，表示要计算最近公共祖先的m个结点对。接下来的m行，每行2 个正整数，是要计算最近公共祖先的结点编号。

结果输出:
将编程计算出的m个结点对的最近公共祖先结点编号输出到文件output.txt。每行3 个
正整数，前2 个是结点对编号，第3 个是它们的最近公共祖先结点编号。

输入文件示例 输出文件示例
input.txt
12
3 2 3 4
2 5 6
0
0
2 7 8
2 9 10
0
0
0
2 11 12
0
0
5
3 11
7 12
4 8
9 12
8 10

output.txt
3 11 1
7 12 2
4 8 1
9 12 6
8 10 2
#include<iostream>
#include<fstream>

using namespace std;

/********************快速排序****************************************/
inline void Swap(int &a, int &b)
{
    int temp=a;
    a=b;
    b=temp;
}///:p

int Partition(int *a, int p, int r)
{
    int i=p;
    int j=r+1;
    int x=a[p];
    while(true)
    {
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j)
        {
            break;
        }
        Swap(a[i],a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}///:p

void QuickSort(int *a, int p, int r)
{
    if(p<r)
    {
        int q=Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}///:p

/*******************************************************************/

/***************二分法查找******************************************/
int FindSource(int *array, int source, int low, int high)
{
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(source==array[mid])
        {
            return source;
        }
        else
        {
            if(source<array[mid])
            {
                high=mid-1;
            }
            else
            {
                low=mid+1;
            }
        }
    }
    return -1;
}///:p
/*******************************************************************/

class CommonTree
{
public:
    CommonTree(int Max=10);
    ~CommonTree();
    void getdata(int *treedata,int num);
    int find_same_ancestor(int Node1, int Node2, int array_num);
    void getroot(int i);
    int Size();
    void Print() const;
private:
    int *TreeArray;
    int size;
    int root;
};///:p

CommonTree::CommonTree(int Max)
{
    size=Max;
    TreeArray=new int [size];
    if(TreeArray==NULL)
    {
        exit(1);
    }
}///:p

CommonTree::~CommonTree()
{
    delete [] TreeArray;
}///:p

void CommonTree::getdata(int *treedata,int num)
{
    int *p_temp=TreeArray;
    TreeArray=treedata;
    treedata=p_temp;
    size=num;
    delete [] treedata;
    treedata=NULL;
}///:p

int CommonTree::find_same_ancestor(int Node1,int Node2, int array_num)
{
    int *array_Node1=new int [array_num];
    int *array_Node2=new int [array_num];
    if(array_Node1==NULL&&array_Node2==NULL)
    {
        exit(1);
    }

    int x=Node1, array_Node1_num=0;
    array_Node1[0]=x;
    while(x!=root)
    {
        x=TreeArray[x];
        
        array_Node1_num++;
        array_Node1[array_Node1_num]=x;
    }

    x=Node2;
    int array_Node2_num=0;
    array_Node2[0]=x;
    while(x!=root)
    {
        x=TreeArray[x];
        array_Node2_num++;
        array_Node2[array_Node2_num]=x;
    }

    QuickSort(array_Node2, 0, array_Node2_num);

    int result=0;
    for(int i=0; i<=array_Node1_num; i++)
    {
        
        result=FindSource(array_Node2, array_Node1[i], 0, array_Node2_num);
        if(result!=-1)
        {
            break;
        }
    }

    delete []array_Node1;
    delete []array_Node2;
    return result;
}///:p

inline int CommonTree::Size()
{
    return size;
}///:p

inline void CommonTree::getroot(int i)
{
    root=i;
}///:p

void CommonTree::Print() const
{
    for(int i=1;i<size;i++)
    {
        cout<<this->TreeArray[i]<<" ";
    }
    cout<<endl;
    cout<<root<<endl;
}///:p

int main()
{
    ifstream in("input.txt");
    if(in.fail())
    {
        cout<<"input error!"<<endl;
        exit(1);
    }
    ofstream out("output.txt");

    int NodeNum;
    in>>NodeNum;
    int *AncestorTree=new int [NodeNum+1];
    if(AncestorTree==NULL)
    {
        exit(1);
    }
    memset(AncestorTree, 0, sizeof(int)*(NodeNum+1));

    int father=1;
    for(int j=0; j<NodeNum; j++)
    {
        int lop;
        
        in>>lop;
        for(int i=0;i<lop;i++)
        {
            int temp;
            in>>temp;
            AncestorTree[temp]=father;
        }
        father++;
    }

    for(j=1; j<=NodeNum;j++)
    {
        if(AncestorTree[j]==0)
        {
            AncestorTree[j]=j;
            break;
        }
    }

    int find_num;
    in>>find_num;
    int *result=new int [3*find_num];
    if(result==NULL)
    {
        exit(1);
    }
    for(int i=0; i<2*find_num; i++)
    {
        in>>result[i];
    }
    CommonTree main_tree(10);
    main_tree.getdata(AncestorTree,NodeNum+1);
    main_tree.getroot(j);

    int displace=0;

    for(i=0; i<find_num; i++)
    {
        result[2*find_num+i]=main_tree.find_same_ancestor(result[displace], result[displace+1], NodeNum);
        displace+=2;
    }
    displace=0;
    for(i=0; i<find_num; i++)
    {
        out<<result[displace]<<" "<<result[displace+1]<<" "<<result[2*find_num+i];
        displace+=2;
        out<<endl;
    }

    delete [] result;
    return 0;
}