前置知识
解法
将 \(a_{i}\) 向 \(i\) 连一条有向边，这样就形成了基环外向树森林。
基环外向树森林内每棵基环外向树是相互独立的，需要单独处理。
对于每棵基环外向树，任取环上一点 \(x\)，断开 \(x\) 到 \(fa_{x}\) 的有向边，外向树就变成了一棵以 \(x\) 为根的树。
设 \(f_{x,0/1}\) 表示 \(x\) 不选/选时，以 \(x\) 为根的子树的最多选择个数，状态转移方程为 \(\begin{cases} f_{x,0}=\sum\limits_{y \in Son(x)} \max(f_{y,0},f_{y,1}) \\ f_{x,1}=1+\max\limits_{y \in Son(x)} \{ f_{y,0}+\sum\limits_{z \in Son(x),z \ne y} \max(f_{z,0},f_{z,1}) \}=1+f_{x,0}- \min\limits_{y \in Son(x)} \{ \max(f_{y,0},f_{y,1})-f_{y,0} \} \end{cases}\)。
将原问题拆成两部分。第一部分为 \(x\) 不限制 \(fa_{x}\)，断开 \(x\) 到 \(fa_{x}\) 的有向边，在以 \(x\) 为根的树上进行 DP，得到的结果为 \(\max(f_{x,0},f_{x,1})\)；第二部分为 \(x\) 限制 \(fa_{x}\)。故再次以 \(fa_{x}\) 为根进行 DP，得到的结果为 \(f_{fa_{x},1}\)。这两部分合起来能够覆盖整个问题，故二者取 \(\max\) 即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct node
{
int nxt,to;
}e[2000010];
int head[2000010],vis[2000010],u[2000010],v[2000010],f[2000010][2],rt,cnt=0;
void add(int u,int v)
{
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
int dfs_huan(int x)
{
vis[x]=1;
return (vis[u[x]]==1)?x:dfs_huan(u[x]);
}
void dfs(int x)
{
int minn=0x3f3f3f3f;
vis[x]=1;
f[x][0]=0;
for(int i=head[x];i!=0;i=e[i].nxt)
{
if(e[i].to==rt)
{
f[e[i].to][1]=-0x3f3f3f3f;
}
else
{
dfs(e[i].to);
f[x][0]+=max(f[e[i].to][0],f[e[i].to][1]);
minn=min(minn,max(f[e[i].to][0],f[e[i].to][1])-f[e[i].to][0]);
}
}
f[x][1]=1+f[x][0]-minn;
}
int main()
{
int n,ans=0,maxx,i;
cin>>n;
for(i=1;i<=n;i++)
{
v[i]=i;
cin>>u[i];
add(u[i],v[i]);
}
for(i=1;i<=n;i++)
{
if(vis[i]==0)
{
rt=dfs_huan(i);
dfs(rt);
maxx=max(f[rt][0],f[rt][1]);
rt=u[rt];
dfs(rt);
ans+=max(maxx,f[rt][1]);
}
}
cout<<ans<<endl;
return 0;
}