首页 > ACM题库 > HDU-杭电 > hdu 2545 树上战争-并查集-[解题报告]C++
2014
02-10

hdu 2545 树上战争-并查集-[解题报告]C++

树上战争

问题描述 :

给一棵树,如果树上的某个节点被某个人占据,则它的所有儿子都被占据,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总是先移动

输出:

输入包含多组数据
每组第一行包含两个数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 1
 1 2
 1 2
 5 2
 1 2
 1 3
 3 4
 3 5
 4 2
 4 5
 0 0

样例输出:

 lxh
 pfz
 lxh

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

/*
    hdu 2545
    并查集

    求出点到根节点距离
*/
#include <cstdio>
#define maxn 100005
using namespace std;
int dis[maxn],father[maxn];
int m,n;
int find(int x)
{
    if(x == father[x])  return x;
    int temp=father[x];
    father[x]=find(father[x]);
    dis[x]+=dis[temp];
    return father[x];
}
int main()
{
    while(scanf("%d%d",&n,&m))
    {
        if(n==0 && m==0)    break;
        for(int i=1; i<=n; i++)
        {
            father[i]=i;
            dis[i]=0;
        }

        int a,b;
        for(int i=0; i<n-1; i++)
        {
            scanf("%d%d",&a,&b);
            father[b]=a;
            dis[b]=1;
        }

        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&a,&b);
            find(a);
            find(b);
            //printf("father:%d %d\n",father[a],father[b]);
            //printf("dis:%d %d\n",dis[a],dis[b]);
            if(dis[a] <= dis[b])    printf("lxh\n");
            else    printf("pfz\n");
        }
    }
}

解题转自:http://blog.csdn.net/leoalwei/article/details/8889715


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c