传送门:CF
[前题提要]:一道基环树dp,但是题目有点绕,当时卡了我整整半天,到了第二天换了和清醒的脑子然后和别人讨论才整明白,故记录一下
题目很绕,故不再介绍.
首先对于这种下标和值有关系的题目.其实不难想到建图(CF上有大量这种 t r i c k trick trick),随便举个类似的题目:CF1768D.所以我们考虑每一个位置下标连向值建图.(注意我们建出来的图中的所有点都是点下标之前的关系)
首先,按照套路,每一个点都有且只有一条出边,也就是每一个点的出度都为1,那么这张图其实是一棵内向基环树.
然后想一下这样建图有什么意义.我们发现我们圈出一个点,其实多出来的是这个点的下标的贡献,那么我们想要选出这个点,按照题意,我们得需要一个值为我们选出来的点的下标的点留下来.那么这个点在哪里呢.就是我们选出来的这个点的入点.(请仔细理解这一部分).
所以我们想要选出一个点,必须得存在一个入点留下来.
然后我们考虑一个点想要留下来.要满足什么条件.我们一个点留下来了,多出来的是这个点的值的贡献,所以我们得需要一个下标为这个值的点被选出来.这个点在哪里呢,这个点显然就是我们当前点的出点.(因为我们每一个点都指向下标为该点值的点).
总结一下就是:
一个点想要留下来,它的父亲必须删除.一个点想要删除,必须存在一个儿子留下来
然后根据上述结论,其实我们不难发现,叶子节点都是得保留下来的,因为没有一个点指向叶子节点,也就是,没有一个点的值等于我们的叶子结点的下标
所以我们考虑对这棵基环树进行拓扑(其实这也是基环树dp的经典套路,拓扑排序).从叶子节点开始倒推,一步一步的确定每一个点的状态(此时我们会发现一个点的状态其实是一定的,因为有一个点只要有儿子留下来,该点就必须删除,没有儿子留下来的时候,该点又只能留下来).所以我们可以使用树形 d p dp dp来推出每一个根节点的状态(保留或者删除).
这里补一下上述做法:因为该图是一个基环树,按照经典做法,我们考虑求出环上的每一个点,那么对于每一个点来说,他都是一棵树的根节点(基环树的性质).所以我们可以对每一个根节点形成的树进行树形 d p dp dp.然后求出每一个根节点的状态最后进行环形 d p dp dp.
所以我们现在是求出了环上每一个点的状态.所以我们考虑环上该怎么办.
详细讨论一下就会发现存在以下几种情况:
- 环上的每一个点独立状态都是保留.此时需要注意的是,我们环上的点其实相互都是有入点和出点的.所以此时的保留状态其实是可以变为删除状态的.此时我们只要随便选一个点保留,然后对应的出点需要删除.显然的,我们会发现只要是奇数点必然会出现矛盾,是偶数环则不会.
- 环上存在一个点是删除状态的.我们考虑从这个删除状态出发.因为环上一个点如果删除了.它的出点就不会有这个点的贡献.所以出点如果是删除状态,那么还是删除状态;如果是保留状态,那么需要变为删除状态,然后使用之前的性质递推下去.这里需要注意的是,我们需要从删除状态出发.
举个栗子:
0代表独立状态为删除,1代表保留.如果我们从下面那个3出发,我们会发现4变为0,3也变为0.但是当3变为0的时候,4不能变为0.所以此时出现了问题.
但是为什么从0出发就没有问题呢.因为从0出发,我们最后循环到自己这个位置的时候因为他是0,所以无论后面是1还是0,他都可以是0(不会对初始状态产生影响).所以我们会发现这样构造一定是成立的.
还有一点需要注意的是,本题可能是一个基环树森林
下面是具体的代码部分:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline void print(__int128 x){
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const int mod=998244353;
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];vector<int>edge[maxn];
int in[maxn];int n;int vis[maxn],mp[maxn];int cnt=0;
void dfs(int u,int per_u) {//找环
for(auto v:edge[u]) {
if(v==per_u) continue;
if(in[v]==1||vis[v]==1) continue;
mp[++cnt]=v;vis[v]=1;
dfs(v,u);
}
}
int state[maxn];//1保留,0删除
void solve(int u,int per_u) {//树形dp
if(edge[u].size()==1) {
state[u]=1;return ;
}
int this_cnt=0;
for(auto v:edge[u]) {
if(v==per_u) continue;
if(in[v]==2) continue;
solve(v,u);
this_cnt+=state[v];
}
if(this_cnt!=0) state[u]=0;
else state[u]=1;
}
void init() {
for(int i=1;i<=cnt;i++) {
mp[i]=0;
}
}
int flag=0;
void topo() {
queue<int>q;
for(int i=1;i<=n;i++) {
if(in[i]==1) {
q.push(i);
}
}
while(!q.empty()) {
int u=q.front();q.pop();
for(auto v:edge[u]) {
in[v]--;
if(in[v]==1) {
q.push(v);
}
}
}
for(int i=1;i<=n;i++) {
if(in[i]==2&&vis[i]==0) {
cnt=0;
mp[++cnt]=i;vis[i]=1;
dfs(i,0);
for(int j=1;j<=cnt;j++) {
solve(mp[j],0);
}
int pos=0;int this_cnt=0;
for(int j=1;j<=cnt;j++) {
this_cnt+=state[mp[j]];
if(state[mp[j]]==0) {
pos=j;
}
}
if(this_cnt==cnt) {//全是1,说明可以乱填,但如果是奇数,不行
if(cnt&1) {
flag=1;break;
}
else {
int num=1;
for(int j=1;j<=cnt;j++) {
state[mp[j]]=num;num^=1;
}
}
}
else {//如果不是,那么如果一个点没有儿子,那这个1不能变成0
//反之可以变为0(因为环中也可以保留点),所以应该从0出发
for(int j=pos;j<=pos+cnt-1;j++) {
if(state[mp[(j-1+cnt)%cnt+1]]==1) {
if(state[mp[(j+cnt)%cnt+1]]) {
state[mp[(j+cnt)%cnt+1]]=0;
}
}
}
}
if(flag) break;
init();
}
}
if(flag) {
cout<<-1<<endl;
}
else {
int this_cnt=0;
for(int i=1;i<=n;i++) {
if(state[i]==1) {
this_cnt++;
}
}
cout<<this_cnt<<endl;
for(int i=1;i<=n;i++) {
if(state[i]==1) {
cout<<a[i]<<" ";
}
}
cout<<endl;
}
}
signed main() {
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) {
a[i]=read();
edge[i].push_back(a[i]);
edge[a[i]].push_back(i);
in[i]++;in[a[i]]++;
}
topo();
return 0;
}
