题面：https://www.luogu.com.cn/paste/4p1b2el1

调了半天没调出来

代码有点长（有注释）

#include<cstdio>
#include<vector>
using namespace std;
namespace Main{
	const int N=110;
	int n,root;
	int f[N];
	char op[2];
	vector<int> s[N],t[N],q[N];
	inline void init(){
		for(int i=1;i<=n;i++){
			f[i]=i;
		}
		return ;
	}
	inline void dfsq(int x){
		for(auto i:s[x]){
			printf("%c",i+'A'-1);
			if(!(s[i].end()-s[i].begin())){
				continue;
			}
			dfsq(i);
		}
		return ;
	}
	inline void dfsz(int x){
//		int len=s[x].end()-s[x].begin();
		if(q[x].size()>=1){
			dfsz(q[x][0]);
		}
		printf("%c",x-1+'A');
		if(q[x].size()>=2){
			dfsz(q[x][1]);
		}
		return ;
	}
	inline void dfsh(int x){
		for(auto i:s[x]){
			if(!(s[i].end()-s[i].begin())){
				printf("%c",i+'A'-1);
				continue;
			}
			dfsh(i);
			printf("%c",i+'A'-1);
		}
		return ;
	}
	inline bool check(int r){
		//节点r的下标就为r
		for(int i=1;i<=n;i++){
			for(auto j:s[i]){
				if(j==r){
					return 1;
				}
			}
		}
		return 0;
	}
	/*
	示例:
	ABCDEFGHI
	123456789
	*/
	inline void main(){
		scanf("%d",&n);
		init();
		for(int i=1,r;i<=n;i++){
			scanf("%s",&op);
			r=op[0]-'A'+1;
			while(~scanf("%s",&op)&&op[0]!='0'){
				s[r].push_back(op[0]-'A'+1);
				f[op[0]-'A'+1]=r;
			}
		}
		for(int i=1;i<=n;i++){
			if(f[i]==i){
				root=i;
				break;
			}
		}
		for(int i=1;i<=n;i++){
			int o=i,res=1;
			while(f[o]!=o){
				res++;
				o=f[o];
			}
			t[res].push_back(i);
		}
		for(int i=1;i<=n;i++){
			while(s[i].size()>1){
				s[i].pop_back();
			}
		}
		for(int i=2;i<=n;i++){
			if((!(t[i].end()-t[i].begin()))||(t[i].end()-t[i].begin())==1){
				continue;
			}
			for(int j=1;j<=(t[i].end()-t[i].begin())-1;j++){
				if(check(t[i][j])){//如果该节点有父亲,则跳过
					continue;
				}
				s[t[i][j-1]].push_back(t[i][j]);
			}
		}
		for(int i=1;i<=n;i++){
			for(auto j:s[i]){
				if('A'<=(j-1+'A')&&(j-1+'A')<='Z'){
					q[i].push_back(j);
				}
			}
		}
		printf("%c",root-1+'A');
		dfsq(root);
		putchar('\n');
		dfsz(root);
		putchar('\n');
		dfsh(root);
		printf("%c",root-1+'A');
	}
}
signed main(){
	Main::main();
	return 0;
}