题目链接：点击打开链接
题目大意：略。
解题思路：略。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; struct cmp { bool operator()(const char* s1,const char* s2) const { return strcmp(s1,s2)<0; // default：map 根据 key 排序（字典序） } }; map<char*,int,cmp> mp; struct node { char name[20]; int par,space; }*tree; int n,m; int calSp(char name[]) { char c; int cnt=0,k=0; while((c=getchar())==' ') cnt++; do { name[k++]=c; }while((c=getchar())!='\n'); name[k]='\0'; return cnt; } // 往前遍历第一个比他缩进少的就是他的父亲,否则就是亚当夏娃 int trace(int child) { for(int i=child-1;i>=0;i--) if(tree[i].space<tree[child].space) return i; return -1; } int jde_child_parent(int aid, int bid) { if(tree[aid].par==aid) tree[aid].par=trace(aid); return tree[aid].par==bid; } int jde_sibling(int aid, int bid) { if(tree[aid].par==aid) tree[aid].par=trace(aid); if(tree[bid].par==bid) tree[bid].par=trace(bid); return tree[aid].par==tree[bid].par; } int jde_desce_ancest(int aid, int bid) { while(aid!=-1) if(jde_child_parent(aid,bid)) return 1; else aid=tree[aid].par; return 0; } void solve() { char a[20],with[20],b[20]; scanf("%s%*s%*s%s%*s%s",a,with,b); int rs,aid=mp[a],bid=mp[b]; char op=with[0]; if(op=='c') rs=jde_child_parent(aid,bid); else if(op=='p') rs=jde_child_parent(bid,aid); else if(op=='s') rs=jde_sibling(aid,bid); else if(op=='d') rs=jde_desce_ancest(aid,bid); else if(op=='a') rs=jde_desce_ancest(bid,aid); puts(rs?"True":"False"); } int main() { while(~scanf("%d%d",&n,&m)) { mp.clear(); tree=(node*)malloc(sizeof(node)*n); getchar(); for(int i=0;i<n;i++) { tree[i].space=calSp(tree[i].name); tree[i].par=i; // init mp[tree[i].name]=i; } tree[0].par=-1; for(int i=0;i<m;i++) solve(); } return 0; }
