树上战争

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

输入包含多组数据
每组第一行包含两个数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总是先移动

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

  
2 11 21 25 21 21 33 43 54 24 50 0

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





解题思路：
	并查集题。思想就是建立联系时不一次建立到根节点，而是只找到父节点即可。最后一定能建立一棵树，那么利用find函数的路径压缩来求得每个结点的深度，如果x节点的深度大于y节点的深度，那么pfz一定赢，否则lxh一定赢。




完整代码：
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;/** Constant List .. **/ //{const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;
const int maxn = 100001;
int f[maxn];
int s[maxn];
void init()
{for(int i = 0 ; i <= maxn ; i ++)f[i] = i;
}void find(int x , int &cnt)
{if(x == f[x])return ;else{cnt++;find(f[x] , cnt);}
}int main()
{#ifdef DoubleQfreopen("in.txt","r",stdin);#endifint n , m;while(~scanf("%d%d",&n,&m)){init();if(n == 0 && m == 0)break;int a , b;for(int i = 0 ; i < n - 1 ; i ++){scanf("%d%d",&a , &b);f[b] = a;}int x , y;for(int i = 0 ; i < m ; i++){scanf("%d%d",&x,&y);int cnt1 = 0 , cnt2 = 0;find(x , cnt1);find(y , cnt2);if(cnt1 > cnt2)printf("pfz\n");elseprintf("lxh\n");}}
}