uva7291 Kinfolk(最近公共祖先)

uva7291 Kinfolk(最近公共祖先)

7291 Kinfolk
The English language abounds with terms for describing family (genetic) relationships. The basic
relationships are:
• Self, parent (mother and father), and child (daughter and son) are well understood.
• Another child of your parent is your sister (if female) or brother (if male).
• The child of your sister or brother is your niece (if female) or nephew (if male). You would be
their aunt (if female) or uncle (if male).
• Two people who share a common grandparent but not a common parent are 1st cousins. If they
share a common great-grandparent but not a common grandparent, they are 2nd cousins. This
can be extended to 3rd cousins and so on.
These relationships are extended to later generations as follows:
• The daughter, son, niece, and nephew relationships can be extended to later generations by prepending
“grand”, “great-grand”, or “great-great-grand”. Thus the son of one’s son or daughter is
a grandson. The son of your niece or nephew is your grandnephew. Your grandnephew’s daughter
would be your great-grandniece, and so on. (In theory, we could extend this to any number of
additional “great-” prefixes, but we will stop with “great-great-grand” in this problem.)
• The mother, father, aunt, and uncle relationships are extended symmetrically by the same prefix.
Thus you would be the grandmother or grandfather of your granddaughter or grandson, the
great-granduncle or great-grandaunt of your great-grandnieces and great-grandnephews, etc.
• The cousin relationship is extended to your cousin’s descendants by degrees of removal. The
children of your 1st cousin are your 1st cousins once removed (and, symmetrically, you are their
1st cousin once removed). The grand-children of your 3rd cousin are your 3rd cousins twice
removed. The great-grandchildren of your 2nd cousin are your 2nd cousins thrice removed. All
of the cousin-based relationships are symmetric, so if someone is your Kth cousin something
removed, you are theirs as well.
Write a program to determine the relationship of one person to another.
Input
Input will consist of one or more datasets. Each dataset consists of a single line containing two integers
A and B (0 ≤ A, B ≤ 32767) and a character. A negative number for the first integer indicates end of
input.
The integers identify persons A and B. The character will be either ‘M’ or ‘F’, designating the gender
of person B as male or female.
The integers identify the positions of person A and person B in a family tree envisioned as follows:
consider a full binary tree in which the root is numbered 0, its children are numbered 1 and 2, the
children of 1 are 3 and 4, the children of 2 are 5 and 6, and numbering proceeds in that manner,
level by level, left to right. This numbering scheme is shown in the diagram below. A parent-child
relationship in this tree represents a parent-child relationship in the family.
ACM-ICPC Live Archive: 7291 – Kinfolk 2/2
Output
For each dataset, print a single line indicating the relationship of B to A.
This relationship must be constructed from the phrases ‘self’, ‘sister’, ‘brother’, ‘daughter’,
‘son’, ‘mother’, ‘father’, ‘niece’, ‘nephew’, ‘aunt’, ‘uncle’, ‘cousin’, ‘grand’, ‘great-’, ‘1st’, ‘2nd’,
‘3rd’, ‘once removed’, ‘twice removed’, and ‘thrice removed’.
• No more than two ‘great-’ prefixes may be applied.
• If ‘1st’, ‘2nd’, or ‘3rd’ is used, it should be separated from the following part of the line by a
single blank.
• If ‘once removed’, ‘twice removed’, or ‘thrice removed’ is used, it must be separated from the
preceding part of the line by a single blank.
If it is not possible to describe the relationship of B to A under the above limitations, then print
‘kin’.
Sample Input
1 5 M
0 0 M
1 11 F
0 8 F
5 7 M
0 32767 F
-1 -1 M
Sample Output
nephew
self
grandniece
great-granddaughter
1st cousin once removed
kin

输入a和b，和一个字符，F表示女，M表示男，问b是a的什么关系的亲戚
用LCA求出a和b的最近公共祖先lca，判断a,b与lca相差的层数，根据层数判断他们之间的关系，多于great-great-grand的关系输出kin

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;typedef long long ll;
#define memset(a,n) memset(a,n,sizeof(n))
#define MAX 32767
struct node
{int fa;int deep;int l;int r;
} nod[MAX+5];
void dfs(int n,int d)
{if(n>MAX)return ;nod[n].l=n*2+1;nod[n].r=n*2+2;nod[n].deep=d;if(n==0)nod[n].fa=0;else if(n%2==0)nod[n].fa=n/2-1;elsenod[n].fa=n/2;dfs(nod[n].l,d+1);dfs(nod[n].r,d+1);
}int LCA(int a,int b)
{int x,y;x=a;y=b;// x=nod[a].fa;//y=nod[b].fa;while(x!=y){if(x<y)y=nod[y].fa;elsex=nod[x].fa;}return x;
}
int main()
{int a,b;char c;dfs(0,1);while(scanf("%d %d %c",&a,&b,&c)!=EOF){if(a==-1&&b==-1)break;int lca=LCA(a,b);//cout<<lca<<endl;int da=nod[a].deep-nod[lca].deep;int db=nod[b].deep-nod[lca].deep;// cout<<da<<" "<<db<<endl;if(a==b)cout<<"self";else if(da==1&&db==1)    //亲兄妹{if(c=='F') cout<<"sister";else cout<<"brother";}else if(da==0)    //b是a的子女{if(db==2)cout<<"grand",db-=1;else if(db==3)cout<<"great-grand",db-=2;else if(db==4)cout<<"great-great-grand",db-=3;if(db==1){if(c=='F') cout<<"daughter";else cout<<"son";cout<<endl;continue;}cout<<"kin";}else if(db==0)     //a是b的父母，祖父母{if(da==2)cout<<"grand",da-=1;else if(da==3)cout<<"great-grand",da-=2;else if(da==4)cout<<"great-great-grand",da-=3;if(da==1){if(c=='F') cout<<"mother";else cout<<"father";cout<<endl;continue;}cout<<"kin";}else if(nod[a].fa==lca&&nod[a].deep<nod[b].deep)    //侄子{if(db==3)cout<<"grand",db-=1;else if(db==4)cout<<"great-grand",db-=2;else if(db==5)cout<<"great-great-grand",db-=3;if(db==2){if(c=='F') cout<<"niece";else cout<<"nephew";cout<<endl;continue;}cout<<"kin";}else if(nod[b].fa==lca&&nod[b].deep<nod[a].deep)    //叔叔阿姨{if(da==3)cout<<"grand",da-=1;else if(da==4)cout<<"great-grand",da-=2;else if(da==5)cout<<"great-great-grand",da-=3;if(da==2){if(c=='F') cout<<"aunt";else cout<<"uncle";cout<<endl;continue;}cout<<"kin";}else if(da>=2&&db>=2)     //堂兄堂妹{int minn,maxx;minn=min(da,db);maxx=max(da,db);int cha=maxx-minn;if(minn<=4&&cha<=3){if(minn==2) cout<<"1st cousin";else if(minn==3) cout<<"2nd cousin";else if(minn==4) cout<<"3rd cousin";if(cha==1)  cout<<" once removed";else if(cha==2) cout<<" twice removed";else if(cha==3) cout<<" thrice removed";}elsecout<<"kin";}elsecout<<"kin";cout<<endl;}return 0;
}