题目链接
瞎jb贪一发就过了。首先度数<=2且编号最小的点一定是中序遍历最靠前的点，我们从这个点开始dfs一遍算出子树中度数<=2且编号最小的点记为\(f(i)\)，然后从这个点开始一步一步确定出它到根的路径。
如果这个点度数还剩2(也就是除掉之前确定的左儿子后的度数)，那么选\(f(i)\)小的作为右儿子，如果度数剩1，那么比较\(f(i)\)与i谁更小，若\(i<=f(i)\)则把i作为父亲否则作为右儿子。每次不断跳到它的父亲，没父亲了就是根了，之后的事就是把这条链上的每个点的右儿子的子树给确定出来，这个算出\(f(i)\)后搞一搞就行了，注意i只有一个儿子时若\(i<f(ch)\)那么把这个ch调到右边去。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define P puts("lala")
#define cp cerr<<"lala"<<endl
#define ln putchar('\n')
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
inline int read()
{
char ch=getchar();int g=1,re=0;
while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();
return re*g;
}
typedef long long ll;
typedef pair<int,int> pii;
const int N=1000050;
const int inf=0x3f3f3f3f;
int deg[N],head[N],cnt=0;
pii oo=pii(inf,inf);
struct node
{
int to,next;
}e[N<<1];
inline void add(int x,int y)
{
e[++cnt]=(node){y,head[x]};head[x]=cnt;
}
int n,f[N],ch[N][2],g[N];
void dfs(int u,int fa)
{
pii minn=oo,sec=oo;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
if(pii(f[v],v)<minn)
{
if(minn<sec) sec=minn;
minn=pii(f[v],v);
}
else if(pii(f[v],v)<sec) sec=pii(f[v],v);
}
if(minn==oo) f[u]=u,ch[u][0]=ch[u][1]=0;
else if(sec==oo)
{
if(u<minn.fi) ch[u][0]=0,ch[u][1]=minn.se,f[u]=u;
else ch[u][0]=minn.se,ch[u][1]=0,f[u]=minn.fi;
}
else ch[u][0]=minn.se,ch[u][1]=sec.se,f[u]=minn.fi;
}
void dfs2(int u,int fa)
{
int tot=-1;
g[u]=inf;
if(deg[u]<=2) g[u]=u;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa) continue;
dfs2(v,u);
ch[u][++tot]=v;
g[u]=min(g[u],g[v]);
}
if(tot==1&&g[ch[u][1]]<g[ch[u][0]]) swap(ch[u][0],ch[u][1]);
else if(tot==0&&g[ch[u][0]]>=ch[u][0]) ch[u][1]=ch[u][0],ch[u][0]=0;
}
void print(int o)
{
if(ch[o][0]) print(ch[o][0]);
printf("%d ",o);
if(ch[o][1]) print(ch[o][1]);
}
void wj()
{
#ifndef ONLINE_JUDGE
freopen("binary.in","r",stdin);
freopen("binary.out","w",stdout);
#endif
}
int main()
{
wj();
int i,j,opt,T;
n=read();
int minx=inf;
for(i=1;i<=n;++i)
{
deg[i]=read();
for(j=1;j<=deg[i];++j) add(i,read());
if(deg[i]<=2&&i<minx) minx=i;
}
dfs2(minx,0);
int u=minx;
while(u)
{
if(ch[u][0]) dfs(ch[u][0],u);
u=ch[u][1];
}
u=minx;
while(u)
{
printf("%d ",u);
if(ch[u][0]) print(ch[u][0]);
u=ch[u][1];
}
return 0;
}
