Luogu

LOJ

分析

显然最小的 $d_i\leq 2$ 的点会是答案中第一个数。设这个点为 $rt$。

考虑从 $rt$ 开始跳父边。分类讨论一下当前点的情况

• 如果度数为 $1$，说明已经找到了根。
• 如果度数为 $2$，则有一条已经确定（是左儿子），我们只需要判断另一条边作为父边还是右儿子更优，只需要比较 $v$ 子树中最小的 $d_i\leq 2$ 的点和 $v$ 的大小即可判断。
• 如果度数为 $3$，则我们只需要判断剩下两条边哪条作为右儿子更优，只需要比较两棵子树中最小的 $d_i\leq 2$ 的点即可判断。

于是我们只需要预处理出每棵子树中最小的 $d_i\leq 2$，并在上面的过程中维护一下先序遍历即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,rt,d[N];
vector<int> E[N];

int f[N],ans[N],top=0;
void dfs(int u,int fa) {
    f[u]=d[u]<=2?u:1e9;
    for (int v:E[u])
        if (v!=fa) dfs(v,u),f[u]=min(f[u],f[v]);
}
void dfs2(int u,int fa) {
    int ch[2]={0,0},s=0;
    for (int v:E[u]) if (v!=fa) ch[s++]=v;
    if (!s) ans[++top]=u;
    else if (s==1) {
        if (u<f[ch[0]]) ans[++top]=u,dfs2(ch[0],u);
        else dfs2(ch[0],u),ans[++top]=u;
    } else {
        if (f[ch[0]]<f[ch[1]]) dfs2(ch[0],u),ans[++top]=u,dfs2(ch[1],u);
        else dfs2(ch[1],u),ans[++top]=u,dfs2(ch[0],u);
    }
}
void dfs1(int u,int fa) {
    ans[++top]=u; int ch[2]={0,0},s=0;
    for (int v:E[u]) if (v!=fa) ch[s++]=v;
    if (s==1) {
        if (f[ch[0]]<ch[0]) dfs2(ch[0],u);
        else dfs1(ch[0],u);
    } else if (s==2) {
        if (f[ch[0]]<f[ch[1]]) dfs2(ch[0],u),dfs1(ch[1],u);
        else dfs2(ch[1],u),dfs1(ch[0],u);
    }
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) {
        d[i]=read();
        if (d[i]<=2&&!rt) rt=i;
        for (int j=1;j<=d[i];++j) E[i].emplace_back(read());
    }
    dfs(rt,0),dfs1(rt,0);
    for (int i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
    return 0;
}