[数据结构与算法]HDU2545树上战争（并查集简要

Problem Description

给一棵树，如果树上的某个节点被某个人占据，则它的所有儿子都被占据，lxh和pfz初始时分别站在两个节点上，谁当前所在的点被另一个人占据，他就输了比赛，问谁能获胜

Input

输入包含多组数据
每组第一行包含两个数N，M（N，M<=100000），N表示树的节点数，M表示询问数，N=M=0表示输入结束。节点的编号为1到N。
接下来N-1行，每行2个整数A，B(1<=A,B<=N)，表示编号为A的节点是编号为B的节点的父亲
接下来M行，每行有2个数，表示lxh和pfz的初始位置的编号X，Y(1<=X,Y<=N,X!=Y)，lxh总是先移动

Output

对于每次询问，输出一行，输出获胜者的名字

Sample Input

2 1
1 2
1 2
5 2
1 2
1 3
3 4
3 5
4 2
4 5
0 0

Sample Output

lxh
pfz
lxh
提示：
本题输入、输出都很多，请使用scanf和printf代替cin、cout。

并查集：一种树型的数据结构，用于处理一些不相交集合的合并及查询问题

表示元素a与元素b属于一个集合，只需要看father[a]是否等于father[b]（是否拥有相同的父亲结点）
参考代码：

#define MAX 100005
int father[MAX];
//初始化
void init(){
	int i = 0;
	for(i = 0;i < MAX;i++) father[i] = i;
}
//查找
int find(int x){
	return father[x] == x?x:(father[x] = find(father[x]));
}
 //合并
void union(int a,int b){
	int ra = find(a);
	int rb = find(b);
	if(ra == rb) return;
	if(ra<rb) father[rb] = ra;
	else father[ra] = rb;
}

解决HDU2545题思路：赢家是输家的父亲结点，那么就还存在一个祖父结点(赢家自己也可能是祖父结点），判断赢家和输家与祖父结点之间的距离，显然赢家距离更近
每人每轮走一步，lxh先走。两人均向上走。lxh和pfz距离祖父结点相同时lxh赢

#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
int tree[100005];

int find(int x)//离顶点父节点的长度
{
    int sum=0;
    while(x!=tree[x])
    /*以第二个样例为例
    数组初始化遍历到顶点时x=1,x=f[x]=1
    不初始化要遍历顶点时x=0,x=f[x]=0*/
    {
        x=tree[x];//x变成他的父节点即向上走一步
        sum++;
    }
    return sum++;
}

int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m)&&(n+m))
    {
        int a,b;
        for(int i=1;i<=n;i++)//一定要初始化不然会超时
            tree[i]=i;
        for(int i=0;i<n-1;i++)//构建树,数值是下标的父亲
        {
            scanf("%d %d",&a,&b);
            tree[b]=a;
        }
        while(m--)//查询
        {
            int lxh,pfz;
            scanf("%d %d",&lxh,&pfz);
            if(find(lxh)<=find(pfz))
                printf("lxh\n");
            else
                printf("pfz\n");
        }
    }
    return 0;
}