情况有点多…
显然的贪心就是我们要让最小的一个叶子节点作为最左边的点
然后考虑从这个点向上走
对于2个儿子
显然是把子树最小值小的那一个设成右儿子
另一个当成父亲
然后讨论的情况有点多…
反正自己咕咕了
具体选哪个根不重要
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<17|1;
#define pb push_back
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob)?EOF:*ib++;
}
#define gc getchar
inline int read(){
char ch=getchar();
int res=0,f=1;
while(!isdigit(ch))f^=(ch=='-'),ch=getchar();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
return f?res:-res;
}
const int N=1000005;
int n,mn[N],in[N],rt;
int adj[N],nxt[N<<1],to[N<<1],cnt;
inline void addedge(int u,int v){
nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
inline void chemn(int &a,int b){
a=a>b?b:a;
}
void dfs(int u,int fa){
if(in[u]<3&&u!=rt)mn[u]=u;
else mn[u]=n;
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(v==fa)continue;
dfs(v,u),chemn(mn[u],mn[v]);
}
}
void solve(int u,int fa){
if(u!=rt&&in[u]==1){rt=u;return;}
if(in[u]<3)rt=u;
int son1=0,son2=0;
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(v==fa)continue;
son2=son1,son1=v;
}
if(son2&&mn[son1]<mn[son2])swap(son1,son2);
if(in[u]==3)solve(son1,u);
else if(in[son1]==2&&son1<mn[son1])solve(son1,u);
else if(in[son1]==3){
int ms=n;
for(int e=adj[son1];e;e=nxt[e]){
int v=to[e];
if(v==u)continue;
ms=min(ms,mn[v]);
}
if(son1<ms)solve(son1,u);
}
}
void write(int u,int fa){
int son1=0,son2=0;
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(v==fa)continue;
son2=son1,son1=v;
}
if(son2&&mn[son2]<mn[son1])swap(son1,son2);
if(!son2&&mn[son1]>u)swap(son1,son2);
if(son1)write(son1,u);
cout<<u<<" ";
if(son2)write(son2,u);
}
int main(){
int size=100<<20;//40M
//__asm__ ("movl %0, %%esp
"::"r"((char*)malloc(size)+size));//调试用这个
__asm__ ("movq %0,%%rsp
"::"r"((char*)malloc(size)+size));//提交用这个
//main函数代码
n=read();
for(int i=1;i<=n;i++){
in[i]=read();
if(in[i]<3&&!rt)rt=i;
for(int j=1;j<=in[i];j++)addedge(i,read());
}
dfs(rt,0);
if(in[rt]==1)solve(rt,0);
else {
int son1=0,son2=0;
for(int e=adj[rt];e;e=nxt[e]){
int v=to[e];
son2=son1,son1=v;
}
if(mn[son2]>mn[son1])swap(son2,son1);
solve(son1,rt);
}
dfs(rt,0);
write(rt,0);
exit(0);//必须用exit
}