题解：P13642 EERT

· · 题解

思路

0

枚举全排列，检验合法性。

2

菊花图。

可以发现，不管怎么走，都无法走到根节点，所以无解。

3

链。

对于所有深度为奇数的点，两点间必定没有连边，可以直接走。

偶数位同理。

所以可以先走偶数位，再走奇数位。

特判 n\le 3 时无解即可。

5

设最大深度为 dep。

对于 dep\ge3 时，有以下解法。

对于同一深度的点，两两间必定没有连边，可以直接走。

把同一深度的点看成一个点，做法同链。

当 dep=2 时，树为菊花，无解。

当 dep=3 时，显然只能先走根，再走第三层，最后走第二层。

只要保证第二层最先走到点不为第三层最后一个点的父亲即可。

所以必须满足第二层点数不为 1。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define p_q priority_queue
#define pb push_back
#define mk make_pair
#define pii pair<int,int> 
#define ve vector
#define endl '\n'
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
int dep[10000005],mx,cnt[10000005],cnt1[10000005],a[10000005],fa[105][105];
int k[10000005],vis[25],an[25],m,ans_[25],is_ans;
ve<int>ans;
void dfs(int x){
    if(is_ans) return ;
    if(x==m+1){
        is_ans=1;
        for(int i=1;i<=m;i++){
            ans_[i]=an[i];
        }
        return ;
    }
    if(x==1){
        for(int i=1;i<=m;i++){
            vis[i]=1;
            an[x]=i;
            dfs(x+1);
            vis[i]=0;
        }
    }else{
        for(int i=1;i<=m;i++){
            if(!fa[an[x-1]][i]&&!vis[i]){
                vis[i]=1;
                an[x]=i;
                dfs(x+1);
                vis[i]=0;
            }
        }
    }
}
std::vector<int> eert(int N,std::vector<int> f){
    for(int i=2;i<=N;i++){
        dep[i]=dep[f[i-2]]+1;
        cnt[dep[i]]++;
        mx=max(mx,dep[i]);
    }
    if(N<=10){//直接暴力
        m=N;
        for(int i=2;i<=m;i++){
            fa[i][f[i-2]]=1;
            fa[f[i-2]][i]=1;
        }
        dfs(1);
        if(!is_ans) return ans;
        for(int i=1;i<=m;i++) ans.pb(ans_[i]);
        return ans;
    }
    if(mx==1){
        return ans;
    }
    if(mx<=2){
        for(int i=1;i<mx;i++){
            if(cnt[i]==1){
                return ans;
            }
        }
        for(int i=1;i<=mx;i++){
            k[i]=0;
            cnt1[i]=cnt[i];
            cnt[i]+=cnt[i-1];
        }ans.pb(1);
        for(int i=2;i<=N;i++){
            a[cnt[dep[i]-1]+cnt1[dep[i]]]=i;
            cnt1[dep[i]]--;
        }
        if(cnt[2]==1){
            int _;
            for(int j=cnt[2-1]+1;j<=cnt[2];j++){
                ans.pb(a[j]);
                _=a[j];
            }
            for(int j=cnt[1-1]+1;j<=cnt[1];j++){
                if(a[j]!=f[_-2]) ans.pb(a[j]);
            }
            ans.pb(f[_-2]);
            return ans;
        }
        for(int i=2;i<=mx;i++){
            for(int j=cnt[i-1]+1;j<=cnt[i];j++){
                if(f[a[j]-2]!=a[cnt[i-2]+1]){
                    k[i]=a[j];
                    break;
                }
            }
        }
        for(int i=mx;i>=1;i--){
            for(int j=cnt[i-1]+1;j<=cnt[i];j++){
                if(a[j]!=k[i]) ans.pb(a[j]);
            }
            if(k[i]) ans.pb(k[i]);
        }
        return ans;     
    }
    else{
        for(int i=1;i<=mx;i++){
            cnt1[i]=cnt[i];
            cnt[i]+=cnt[i-1];
        }
        for(int i=2;i<=N;i++){
            a[cnt[dep[i]-1]+cnt1[dep[i]]]=i;
            cnt1[dep[i]]--;
        }     
        for(int i=1;i<=mx;i+=2){
            for(int j=cnt[i-1]+1;j<=cnt[i];j++){
                if(a[j]!=k[i]) ans.pb(a[j]);
            }
        }
        ans.pb(1);
        for(int i=2;i<=mx;i+=2){
            for(int j=cnt[i-1]+1;j<=cnt[i];j++){
                ans.pb(a[j]);
            }
        }
        return ans;
    }
}