1 人解决，4 人已尝试。
1 份提交通过，共有 20 份提交。
9.9 EMB 奖励。
1515. Climbing Trees
单点时限: 2.0 sec
内存限制: 256 MB
Expression trees, B and B* trees, red-black trees, quad trees, PQ trees; trees play a significant role in many domains of computer science. Sometimes the name of a problem may indicate that trees are used when they are not, as in the Artificial Intelligence planning problem traditionally called the Monkey and Bananas problem. Sometimes trees may be used in a problem whose name gives no indication that trees are involved, as in the Huffman code.
This problem involves determining how pairs of people who may be part of a ``family tree’‘ are related.
输入格式
The input consists of parent-child pairs of names, one pair per line. Each name in a pair consists of lower-case alphabetic characters or periods (used to separate first and last names, for example). Child names are separated from parent names by one or more spaces. Parent-child pairs are terminated by a pair whose first component is the string ``no.child’‘. Such a pair is NOT to be considered as a parent-child pair, but only as a delimiter to separate the parent-child pairs from the query pairs. There will be no circular relationships, i.e., no name p can be both an ancestor and a descendent of the same name q.
The parent-child pairs are followed by a sequence of query pairs in the same format as the parent-child pairs, i.e., each name in a query pair is a sequence of lower-case alphabetic characters and periods, and names are separated by one or more spaces. Query pairs are terminated by end-of-file.
There will be a maximum of 300 different names overall (parent-child and query pairs). All names will be fewer than 31 characters in length. There will be no more than 100 query pairs.
输出格式
For each query-pair of names the output should indicate the relationship p is-the-relative-of q by the appropriate string of the form
child, grand child, great grand child, great great …great grand child
parent, grand parent, great grand parent, great great …great grand parent
sibling
n cousin removed m
no relation
If an m-cousin is removed 0 times then only m cousin should be printed, i.e., removed 0 should NOT be printed. Do not print st, nd, rd, th after the numbers.
样例
Input
alonzo.church oswald.veblen stephen.kleene alonzo.church dana.scott alonzo.church martin.davis alonzo.church pat.fischer hartley.rogers mike.paterson david.park dennis.ritchie pat.fischer hartley.rogers alonzo.church les.valiant mike.paterson bob.constable stephen.kleene david.park hartley.rogers no.child no.parent stephen.kleene bob.constable hartley.rogers stephen.kleene les.valiant alonzo.church les.valiant dennis.ritchie dennis.ritchie les.valiant pat.fischer michael.rabin
Output
parent sibling great great grand child 1 cousin removed 1 1 cousin removed 1 no relation
题目标签