HDU2545 树上战争

Posted on | In |

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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>

using namespace std;
int n,m;
class UF{
	public:
	vector<int>v;
	UF(int n){
		v=vector<int>(n+2);
		for(int i=0;i<=n;i++){
			v[i]=i;
		}
	}
	Union(int a,int b){
		v[b]=a;
		
	}
	int getDis(int a){
		int dis=0;
		while(a!=v[a]){
			a=v[a];
			dis++;
		}
		return dis;
	}
	
	
};
int main(){
	int x,y;
while(cin>>n>>m){
	UF u(n); 
	if(n==0&&m==0) break;
	for(int i=0;i<n-1;i++){
		cin>>x>>y;
	u.Union(x,y);
	}
	
	for(int i=0;i<m;i++){
	cin>>x>>y; 
	int l1=u.getDis(x);
	int l2=u.getDis(y);
	//cout<<l1<<" "<<l2<<endl;
	if(l1<=l2) {
		cout<<"lxh"<<endl;
	}
	else cout<<"pfz"<<endl;
	} 
}	
}