UVa 115 Climbing Trees-平芜编程栈

题目分析

本题要求根据输入的父子关系对（child-parent pairs\texttt{child-parent pairs}child-parent pairs）构建一个家族树，然后对一系列查询对（query pairs\texttt{query pairs}query pairs）判断两人之间的亲属关系，并按照特定格式输出。关系包括直接父子、祖孙、兄弟姐妹、堂表亲等。

关键定义：

ppp是qqq的kkk-descendent\texttt{descendent}descendent（kkk-ancestor\texttt{ancestor}ancestor）当且仅当存在一条长度为kkk的父子链。
关系分类：
1. child / parent\texttt{child / parent}child / parent：直接父子（k=0k=0k=0），grand child/parent\texttt{grand child/parent}grand child/parent（k=1k=1k=1），great grand child/parent\texttt{great grand child/parent}great grand child/parent（k≥2k \ge 2k≥2，前缀great\texttt{great}great重复k−1k-1k−1次）。
2. sibling\texttt{sibling}sibling：共享同一父母（即000代表000次removed\texttt{removed}removed的000-th cousin\texttt{th cousin}th cousin）。
3. cousin\texttt{cousin}cousin：设ppp和qqq的最小公共祖先为rrr，ppp是rrr的mmm-descendent\texttt{descendent}descendent，qqq是rrr的nnn-descendent\texttt{descendent}descendent，则：
  - 他们是kkk-th cousin\texttt{th cousin}th cousin，其中k=min⁡(m,n)k = \min(m, n)k=min(m,n)。
  - removed\texttt{removed}removedjjj次，其中j=∣m−n∣j = |m - n|j=∣m−n∣。
4. no relation\texttt{no relation}no relation：不在同一家族树中。

输入限制：

最多300300300个不同名字，名字长度不超过303030。
最多100100100个查询对。
无循环关系。

输出要求：

按格式输出关系，若removed\texttt{removed}removed次数为000则不输出removed 0。
数字后不加序数后缀（如st,nd,rd,th）。

解题思路

本题虽然名为“树”，但不需要显式建树，只需维护每个节点的父节点映射即可。由于名字是字符串，我们使用map<string, int>将名字映射为整数编号，便于处理。

步骤：

读取父子关系：
- 每行读入child\texttt{child}child和parent\texttt{parent}parent，直到遇到no.child no.parent。
- 为新名字分配编号，记录parent[child] = parent。
处理查询：
对每个查询对(p,q)(p, q)(p,q)：
- 检查是否存在：若任一名字不在映射中，输出no relation。
- 检查是否在同一棵树：分别找到ppp和qqq的根祖先（不断找父节点直到DUMMY），若不同则输出no relation。
- 判断直接关系：
  - 若ppp是qqq的祖先：根据深度输出parent / grand parent / great ... grand parent\texttt{parent / grand parent / great ... grand parent}parent / grand parent / great ... grand parent。
  - 若ppp是qqq的后代：根据深度输出child / grand child / great ... grand child\texttt{child / grand child / great ... grand child}child / grand child / great ... grand child。
  - 若ppp和qqq是兄弟姐妹（同一父母）：输出sibling。
- 判断堂表亲关系：
  - 先计算ppp和qqq到根节点的深度（mmm和nnn）。
  - 将ppp和qqq提升到同一深度，然后同时向上找，直到找到同一父母。
  - 计算k=min⁡(m′,n′)k = \min(m', n')k=min(m′,n′)（提升后剩余深度），j=∣m−n∣j = |m - n|j=∣m−n∣（深度差）。
  - 输出k cousin（若j=0j=0j=0）或k cousin removed j。

注意：题目要求removed\texttt{removed}removed为000时不输出removed 0，且数字后不加序数词。

代码

// Climbing Trees// UVa ID: 115// Verdict: Accepted// Submission Date: 2011-11-27// UVa Run Time: 0.008s//// 版权所有（C）2011，邱秋。metaphysis # yeah dot net//// [解题方法]// 模拟题。由于只需要保存父子关系，不一定要构建树。虽然方法是直接的，但是有点繁琐。#include<bits/stdc++.h>usingnamespacestd;#defineMAXN310#defineDUMMY(-1)intparent[MAXN];map<string,int>genealogy;boolisAncestor(string fName,string sName){intnFirst=genealogy[fName];intnSecond=genealogy[sName];intdepth=0;boolfound=false;while(parent[nSecond]!=DUMMY){if(parent[nSecond]==nFirst){found=true;break;}nSecond=parent[nSecond];depth++;}if(found){if(depth==0)cout<<"parent\n";elseif(depth==1)cout<<"grand parent\n";else{for(inti=1;i<depth;i++)cout<<"great ";cout<<"grand parent\n";}returntrue;}returnfalse;}boolisDescendent(string fName,string sName){intnFirst=genealogy[fName];intnSecond=genealogy[sName];intdepth=0;boolfound=false;while(parent[nFirst]!=DUMMY){if(parent[nFirst]==nSecond){found=true;break;}nFirst=parent[nFirst];depth++;}if(found){if(depth==0)cout<<"child\n";elseif(depth==1)cout<<"grand child\n";else{for(inti=1;i<depth;i++)cout<<"great ";cout<<"grand child\n";}returntrue;}returnfalse;}boolisInTree(string fName,string sName){if(genealogy.find(fName)==genealogy.end()||genealogy.find(sName)==genealogy.end()){cout<<"no relation\n";returnfalse;}returntrue;}boolisInSameTree(string fName,string sName){intnFirst=genealogy[fName];intnSecond=genealogy[sName];while(parent[nFirst]!=DUMMY)nFirst=parent[nFirst];while(parent[nSecond]!=DUMMY)nSecond=parent[nSecond];if(nFirst!=nSecond){cout<<"no relation\n";returnfalse;}returntrue;}boolisSibling(string fName,string sName){intnFirst=genealogy[fName];intnSecond=genealogy[sName];if(parent[nFirst]!=DUMMY&&parent[nSecond]!=DUMMY&&parent[nFirst]==parent[nSecond]){cout<<"sibling\n";returntrue;}returnfalse;}boolisCousin(string fName,string sName){intnFirst=genealogy[fName];intnSecond=genealogy[sName];intn=0,m=0;while(parent[nFirst]!=DUMMY){nFirst=parent[nFirst];n++;}while(parent[nSecond]!=DUMMY){nSecond=parent[nSecond];m++;}nFirst=genealogy[fName];nSecond=genealogy[sName];intbackN=n,backM=m;if(n>m){while(n>m){nFirst=parent[nFirst];n--;}while(parent[nFirst]!=parent[nSecond]){nFirst=parent[nFirst];nSecond=parent[nSecond];n--;}backN-=n;backM-=n;cout<<backM<<" cousin removed "<<(backN-backM)<<"\n";}elseif(m>n){while(m>n){nSecond=parent[nSecond];m--;}while(parent[nFirst]!=parent[nSecond]){nFirst=parent[nFirst];nSecond=parent[nSecond];m--;}backN-=m;backM-=m;cout<<backN<<" cousin removed "<<(backM-backN)<<"\n";}else{while(parent[nFirst]!=parent[nSecond]){nFirst=parent[nFirst];nSecond=parent[nSecond];n--;m--;}cout<<(backN-n)<<" cousin\n";}returntrue;}intmain(intargc,charconst*argv[]){intnNames=0;string allNames[MAXN];string childName,parentName;for(inti=0;i<MAXN;i++)parent[i]=DUMMY;while(cin>>childName>>parentName){if(childName=="no.child"&&parentName=="no.parent")break;if(genealogy.find(childName)==genealogy.end()){genealogy[childName]=nNames;allNames[nNames++]=childName;}if(genealogy.find(parentName)==genealogy.end()){genealogy[parentName]=nNames;allNames[nNames++]=parentName;}parent[genealogy[childName]]=genealogy[parentName];}while(cin>>childName>>parentName){if(!isInTree(childName,parentName))continue;if(!isInSameTree(childName,parentName))continue;if(isAncestor(childName,parentName))continue;if(isDescendent(childName,parentName))continue;if(isSibling(childName,parentName))continue;if(isCousin(childName,parentName))continue;}return0;}