P4006题解

_WAlkingDead · 2022-10-05 21:23:56 · 题解

首先确定 root，显然度数 \leq2 的点一定为 root。 然后从 root 开始构造子树。

假设下一个点为 v，若 root 存在右子树，则其一定位于 root 的右子树中，需对其右儿子进行操作。 若其存在右儿子，则可以 dp 求出子树内度数 \leq2 的最小点 f_v 作为右儿子。

若其不存在右儿子，则判断 v 与 f_v 的大小选择最优解，若其相等，则一定为右儿子。

复杂度 O(n)

code

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const int N=1e6+5;
int n,rt,f[N];
vector<int> g[N];
void dp(int u,int fa=0){
    f[u]=(g[u].size()<=2?u:0x3f3f3f3f);
    for(int v:g[u]) if(v!=fa){
        dp(v,u);
        f[u]=min(f[u],f[v]);
    }
}
bool cmp(int x,int y){
    return f[x]<f[y];
}
void dfs(int u,int fa,int check=0){
    bool flag=true;
    sort(g[u].begin(),g[u].end(),[](int x,int y){return f[x]<f[y];});
    if(check){
        for(int v:g[u]){
            if(v!=fa){
                if(g[u].size()<=2){
                    if(f[v]>u){
                        printf("%d ",u);
                        flag=false;
                    }
                    dfs(v,u,1);
                }
                else{
                    dfs(v,u,1);
                    if(flag){
                        printf("%d ",u);
                        flag=false;
                    }
                }
            }
        }
        if(flag) printf("%d ",u);
        return ;
    }
    printf("%d ",u);
    for(int v:g[u]){
        if(v!=fa){
            if(g[u].size()==2) dfs(v,u,v>=f[v]);
            else if(g[u].size()==3) dfs(v,u,check--);
        }
    }
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int k=read();
        if(k<=2&&!rt) rt=i;
        while(k--){
            int a=read();
            g[i].push_back(a);
        }
    }
    g[rt].push_back(rt);
    dp(rt);
    dfs(rt,rt);
    return 0;
}