FZU 2057 家谱（dfs）

Problem 2057 家谱

Accept: 129    Submit: 356
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

由于计划生育的实行，我们以及将来几代人都会是独生子女，即每对夫妇只会有一个孩子。那么给你XXXX年某人的一张树形族谱，你能指出其中任意两人的关系吗？

 Input

输入数据第一行一个整数T表示有T组数据。

每组数据第一行一个正整数N (2 < N < 10000 ，且N为奇数)，表示族谱中有N个家族成员。

接下来N/2行，每行三个整数a b c，表示a的父亲是b，a的母亲是c。数据保证所给的是一棵树，家族成员的编号为1到N。

接下来一行一个正整数M (0 < M < 100)，表示有M询问。

接下来M行，每行两个整数x y (x!=y)，表示询问x y的关系。

 Output

对于每一个询问，输出一行。

若x是y的祖辈，则输出：

0 S

若y是x的祖辈，则输出：

1 S

若都不是以上两种情况，则输出：

Relative

前两种情况中的S表示一个由大写字母F和M组成的字符串，F表示父亲，M表示母亲，表示前者是后者的XXX。例如：

0 FMM 表示x是y的父亲的母亲的母亲。

1 MFMF 表示y是x的母亲的父亲的母亲的父亲。

以此类推。

 Sample Input

1
9
3 6 7
5 8 9
1 2 3
2 4 5
3
8 2
1 7
3 9

 Sample Output

0 MF
1 MM
Relative

 

 

搜索一下就ok了

 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#define REP(i,n) for(i=0;i<(n);++i)

#define FOR(i,n) for(i=1;i<=(n);++i)

using namespace std;

const int N = ;

typedef pair<int,int> pii;

struct _node{

    int fa,lc,rc;

    char val;

};

_node mes[N];

int n,sz;

char ans[N];

void add(int f,int l,int r)

{

    mes[f].lc = l;

    mes[f].rc = r;

    mes[l].fa = mes[r].fa = f;

    mes[l].val = 'F';

    mes[r].val = 'M';

}

int dfs(int s,int t,int cur)

{

    if(s==t)

    {

        ans[cur]='\0';

        return cur;

    }

    int lc=mes[s].lc,rc=mes[s].rc,k;

    if(lc)

    {

        ans[cur]='F';

        if(k=dfs(lc,t,cur+))   return k;

    }

    if(rc)

    {

        ans[cur]='M';

        if(k=dfs(rc,t,cur+))    return k;

    }

    return ;

}

void run()

{

    int a,b,c,m,k;

    scanf("%d",&n);

    memset(mes,,sizeof(mes));

    for(int i=;i<=n/;++i)

    {

        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);

    }

    scanf("%d",&m);

    while(m--)

    {

        scanf("%d%d",&a,&b);

        if(k=dfs(a,b,))

        {

            printf("1 %s\n",ans);

//            print();

        }

        else if(k=dfs(b,a,))

        {

            printf("0 %s\n",ans);

        }

        else    puts("Relative");

    }

}

int main()

{

    int _;

    scanf("%d",&_);

    while(_--)

        run();

    return ;

}