Loj #2324. 「清华集训 2017」小 Y 和二叉树
小Y是一个心灵手巧的OIer，她有许多二叉树模型。
小Y的二叉树模型中，每个结点都具有一个编号，小Y把她最喜欢的一个二叉树模型挂在了墙上，树根在最上面，左右子树分别在树根的左下方与右下方，且他们也都满足
这样的悬挂规则。为了让这个模型更加美观，小Y选择了一种让这棵二叉树的中序遍历序列最小的悬挂方法。所谓中序遍历最小，就是指中序遍历的结点编号序列的字典
序最小。
一天，这个模型不小心被掉在了地上，幸运的是，所有结点和边都没摔坏，但是她想不起这个模型原来是怎么悬挂的了，也就是说：她想不起来树根节点的编号了。
小Y最近忙于准备清华集训，所以没太多时间处理别的事情，她只好找到同样心灵手巧的你帮忙复原她的二叉树模型。
给定小Y的二叉树模型，结点的编号为 \(1\) ~ \(n\) ，你需要给出其可能的最小的中序遍历，方便小Y更快的摆好她的模型。
输入格式
第一行为一个正整数 \(n\) ，表示点的个数。
后接 \(n\) 行，每行若干个整数：
第 \(i+1\) 行的第一个整数为 \(k_i\) ，表示编号为 \(i\) 的结点的度数，后接 \(k_i\) 个整数 \(a_{i,j}\) ，表示编号为 \(i\) 的结点与编号为 \(a_{i,j}\) 的结
点之间有一条边。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。
输出格式
输出共一行， \(n\) 个整数，表示字典序最小的中序遍历。
数据范围与提示
\(n\leq 10^6\)
假设我们知道了最优答案下的根，那么答案就很好求了。
设\(mn_i\)表示\(i\)的子树的中序遍历得到第一个点。我们可以发现，\(mn_i\)就是\(i\)子树中度数\(\leq 2\)的子节点中最小的那个。然后我们就递归：如果一个点有两个儿子，就优先走\(mn\)值小的那个；如果只有一个儿子，就要判断儿子的\(mn\)值是否比自己的值大来判断将儿子放在左边还是右边。
难点就是找根。很容易发现，答案的第一位一定是度数\(\leq 2\)的节点中最小的那个。然后我们从这个点开始递归，找到最终答案下的根。我们先找到最小的点，设为\(g\)。然后以\(g\)为根，求出\(mn\)数组。接着就是分情况讨论：
假设当前处理\(v\)节点。默认与\(v\)相邻的还没有访问到的点为\(v\)的儿子。
- 情况1：
假设\(v\)只有一个儿子\(sn_1\)，若 \(sn_1\leq mn_{sn_1}\) 则 \(sn_1\) 就作为\(v\)的父亲，递归\(sn_1\)；否则\(v\)就是最终的根。
如果\(sn_1\)不作为\(v\)的父亲，那么最终答案里，\(v\)过了就是\(mn_{sn_1}\)；反之\(v\)过了就是\(sn_1\)。所以这个贪心是正确的。
- 情况2：
假设\(v\)有两个儿子\(sn_1\),\(sn_2\)（不妨设\(mn_{sn_1}<mn_{sn_2}\)）。那么将\(sn_1\)作为右儿子，\(sn_2\)作为父亲，递归\(sn_2\)。
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n;
int r[N];
struct road {
int to,nxt;
}s[N<<1];
int h[N],cnt;
void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}
vector<int>ans;
int rt;
bool vis[N];
int mn[N];
void Get_mn(int v,int fr) {
if(r[v]<3) mn[v]=v;
else mn[v]=1e9;
for(int i=h[v];i;i=s[i].nxt) {
int to=s[i].to;
if(to==fr) continue ;
Get_mn(to,v);
mn[v]=min(mn[v],mn[to]);
}
}
int RT;
void Find_rt(int v,int fr) {
int sn1=0,sn2=0;
for(int i=h[v];i;i=s[i].nxt) {
int to=s[i].to;
if(to==fr) continue ;
if(!sn1) sn1=s[i].to;
else sn2=s[i].to;
}
if(!sn1) {RT=v;return ;}
if(!sn2) {
if(sn1<=mn[sn1]) Find_rt(sn1,v);
else {RT=v;return ;}
} else {
if(mn[sn1]>mn[sn2]) swap(sn1,sn2);
Find_rt(sn2,v);
}
}
void Print(int v,int fr) {
int sn1=0,sn2=0;
for(int i=h[v];i;i=s[i].nxt) {
int to=s[i].to;
if(to==fr) continue ;
if(!sn1) sn1=to;
else sn2=to;
}
if(mn[sn1]>mn[sn2]) swap(sn1,sn2);
if(!sn2&&mn[sn1]>v) swap(sn1,sn2);
if(sn1) Print(sn1,v);
cout<<v<<" ";
if(sn2) Print(sn2,v);
}
int main() {
mn[0]=1e9;
n=Get();
for(int i=1;i<=n;i++) {
int k=Get();
r[i]=k;
while(k--) {
int a=Get();
add(i,a);
}
}
rt=1e9;
for(int i=1;i<=n;i++) if(r[i]!=3) rt=min(rt,i);
Get_mn(rt,0);
Find_rt(rt,0);
Get_mn(RT,0);
Print(RT,0);
return 0;
}