题目描述
小 Y 是一个心灵手巧的 OIer，她有许多二叉树模型。
小 Y 的二叉树模型中，每个结点都具有一个编号，小 Y 把她最喜欢的一个二叉树模型挂在了墙上，树根在最上面，左右子树分别在树根的左下方与右下方，且他们也都满足这样的悬挂规则。为了让这个模型更加美观，小 Y 选择了一种让这棵二叉树的中序遍历序列最小的悬挂方法。所谓中序遍历最小，就是指中序遍历的结点编号序列的字典序最小。
一天，这个模型不小心被掉在了地上，幸运的是，所有结点和边都没摔坏，但是她想不起这个模型原来是怎么悬挂的了，也就是说：她想不起来树根节点的编号了。
小 Y 最近忙于准备清华集训，所以没太多时间处理别的事情，她只好找到同样心灵手巧的你帮忙复原她的二叉树模型。
输入输出格式
输入格式：
从文件 binary.in 中读入数据。
第一行为一个正整数 n ，表示点的个数。
后接 n 行，每行若干个整数：
第 i + 1 行的第一个整数为 ki ，表示编号为 i 的结点的度数，后接 ki 个整数 ai; j ，表示编号为 i 的结点与编号为 ai; j 的结点之间有一条边。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。
输出格式：
输出到文件 binary.out 中。
输出共一行， n 个整数，表示字典序最小的中序遍历。
题意：给一颗二叉树，你可以随意选择根节点和随意改变儿子顺序，求字典序最小的中序遍历；
题解：
①不断构造；
②假定选好了根节点。mn[v]表示，v的子树中开头的最小值，（根除外）一个结点的度数小于等于2，一个节点可以开头。这样从根不断向下找mn小的做左儿子贪心可以构造出序列；
③现在找根节点，首先最左面的节点一定是固定的，为度数小于等于2的最小值；从这个点u不断往上找，预处理以u为根的所有mn[],然后u对有一个儿子的情况，那么mn较小的应该是u的右儿子，mn较大的应该是u的父亲，只有一个儿子v，mn[v]小于v，那么在真正的结构里v应该是u的右儿子，否则v是u的父亲；不断递归u向上找即可；
④最后再dfs一次输出答案；
#include<cstdio>
#include<iostream>
using namespace std;
const int N=;
int n,m,d[N],rt,st,o,hd[N],ls[N],rs[N],son[N][],mn[N];
struct Edge{int v,nt;}E[*N];
char gc(){
static char *p1,*p2,s[];
if(p1==p2)p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
int rd(){
int x=; char c=gc();
while(c<''||c>'') c=gc();
while(c>=''&&c<='') x=x*+c-'',c=gc();
return x;
}
void adde(int u,int v){E[o]=(Edge){v,hd[u]};hd[u]=o++;}//
void dfsA(int u,int fa){
int cnt=;
for(int i=hd[u],v;i!=-;i=E[i].nt){
if((v=E[i].v)==fa) continue;
son[u][cnt++]=v;
dfsA(v,u);
mn[u] = min(mn[v],mn[u]);
}
}//
void find(int u){
if(d[u]==&&u!=st) {rt=u;return;}
else if(u!=st&&d[u]==||d[u]==&&u==st){
if(son[u][]<mn[son[u][]]) find(son[u][]);
else {rt=u; return;}
}
else{
if(mn[son[u][]]>mn[son[u][]]) find(son[u][]);
else find(son[u][]);
}
}//
int dfsB(int u,int fa){
if(d[u]==&&u!=rt) return u;
int tmp=n+; if(u!=rt&&d[u]==||u==rt&&d[u]==) tmp=u;
for(int i=hd[u],v,now;i!=-;i=E[i].nt){
if((v=E[i].v)==fa) continue;
if((now=dfsB(v,u))<tmp) rs[u]=ls[u],ls[u]=v,tmp=now;
else rs[u]=v;
}
return tmp;
}//
void dfsC(int u){
if(ls[u]) dfsC(ls[u]);
printf("%d ",u);
if(rs[u]) dfsC(rs[u]);
}
int main()
{ freopen("mzoj1120.in","r",stdin);
freopen("mzoj1120.out","w",stdout);
n=rd();
for(int i=;i<=n;i++){
hd[i]=-;d[i]=rd();
for(int j=;j<=d[i];j++) adde(i,rd());
if(d[i]<=) {mn[i]=i; if(!st)st=i;} else mn[i]=n+;
}
//d[st]++;
dfsA(st,);
find(st);
dfsB(rt,);
dfsC(rt);
return ;
}//by tkys_Austin;