树上战争
Time Limit: 10000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1012 Accepted Submission(s): 572
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总是先移动
每组第一行包含两个数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 11 21 25 21 21 33 43 54 24 50 0
Sample Output
lxhpfzlxh提示： 本题输入、输出都很多，请使用scanf和printf代替cin、cout。
Source
UESTC 6th Programming Contest Online
思路：其实是求哪个点离他们的根节点近，sta[i]更新i点到根节点的距离。
# include <stdio.h>
# include <string.h>
const int MAXN = 100000;
int pre[MAXN+1], sta[MAXN+1];int find(int x)
{if(x == pre[x])return x;else{int t= pre[x];pre[x] = find(pre[x]);sta[x] = sta[t] + sta[x];return pre[x];}
}
int main()
{int n, m, a, b;while(~scanf("%d%d",&n,&m), n+m){for(int i=1; i<=n; ++i)pre[i] = i;memset(sta, 0, sizeof(sta));for(int i=1; i<n; ++i){scanf("%d%d",&a,&b);int px = find(a);int py = find(b);if(px != py){pre[py] = px;sta[py] = sta[a] + sta[b] + 1;}}while(m--){scanf("%d%d",&a,&b);find(a);find(b);if(sta[a] <= sta[b])puts("lxh");elseputs("pfz");}}return 0;
}
![洛谷P2545 [AHOI2004]实验基地](https://img-blog.csdnimg.cn/20181218125621607)
