樹上戰爭

Time Limit: 10000/4000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 780????Accepted Submission(s): 423


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 11 21 25 21 21 33 43 54 24 50 0
Sample Output lxhpfzlxh提示： 本題輸入、輸出都很多，請使用scanf和printf代替cin、cout。 #include <cstdio> #include <cstring> using namespace std;int pre[100010];int find(int x){int num = 0;while (x != pre[x]){x = pre[x];num++;}return num; }int main(){int n, m, a, b, x, y;int i, j;while (scanf("%d%d", &n, &m), n || m){for (i = 1; i <= n; i++)pre[i] = i;for (i = 1; i < n; i++){scanf("%d%d", &a, &b);pre[b] = a;}for (i = 1; i <= m; i++){scanf("%d%d", &x, &y);x = find(x);y = find(y);if (x <= y)printf("lxh\n");elseprintf("pfz\n");}}return 0; }

總結

以上是生活随笔為你收集整理的HDOJ 2545 树上战争的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。