专栏文章

题解：P13642 EERT

RRecall_cpp
P13642题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miogzqfu
此快照首次捕获于
2025/12/02 19:03
3 个月前
此快照最后确认于
2025/12/02 19:03
3 个月前
查看原文

思路

#0

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

#2

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

#3

链。
对于所有深度为奇数的点，两点间必定没有连边，可以直接走。
偶数位同理。
所以可以先走偶数位，再走奇数位。
特判 n≤3n\le 3 时无解即可。

#5

设最大深度为 depdep。
对于 dep≥3dep\ge3 时，有以下解法。
对于同一深度的点，两两间必定没有连边，可以直接走。
把同一深度的点看成一个点，做法同链。
当 dep=2dep=2 时，树为菊花，无解。
当 dep=3dep=3 时，显然只能先走根，再走第三层，最后走第二层。
只要保证第二层最先走到点不为第三层最后一个点的父亲即可。
所以必须满足第二层点数不为 11。

代码

CPP
#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;
	}
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...