Problem 2057 家谱

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

FZU 2057 家谱(dfs)-LMLPHP Problem Description

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

FZU 2057 家谱(dfs)-LMLPHP 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的关系。

FZU 2057 家谱(dfs)-LMLPHP Output

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

若x是y的祖辈,则输出:

0 S

若y是x的祖辈,则输出:

1 S

若都不是以上两种情况,则输出:

Relative

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

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

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

以此类推。

FZU 2057 家谱(dfs)-LMLPHP Sample Input

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

FZU 2057 家谱(dfs)-LMLPHP 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 ;
}
05-11 18:31