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 
      
       #include 
       
        #include 
        
         #include 
         
          #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 = 100005;typedef pair
          
            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+1))   return k;    }    if(rc)    {        ans[cur]='M';        if(k=dfs(rc,t,cur+1))    return k;    }    return 0;}void run(){    int a,b,c,m,k;    scanf("%d",&n);    memset(mes,0,sizeof(mes));    for(int i=1;i<=n/2;++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,0))        {            printf("1 %s\n",ans);//            print();        }        else if(k=dfs(b,a,0))        {            printf("0 %s\n",ans);        }        else    puts("Relative");    }}int main(){    int _;    scanf("%d",&_);    while(_--)        run();    return 0;}