正题

题目大意

每个物品有一个可以限制的物品，要求一个集合内所有的物品都有一个不在集合内物品限制。求这个集合可以保护的最多物品

解题思路

类似没有上司的舞会

其实就是在基环树森林，我们可以利用二次树形dp的方法。

先找到环，然后强行将环断开进行一次dp，然后强行连上进行一次dp，两个答案的最小值就得这棵树的最大物品。

其实也可以贪心，这里就不放了。

code

#include
   
    #include
    
     #include
     
      #define N 1000010using namespace std;struct node{
   	int to,next;}a[N];int n,x,ans,tot,fa[N],root,f[N],g[N],ls[N],d[N],mark;bool v[N];void addl(int x,int y){
   	a[++tot].to=y;	a[tot].next=ls[x];	ls[x]=tot;}void check_c(int x)//判环{
   	v[x]=true;	if(v[d[x]]) mark=x;	else check_c(d[x]);	return;}void dp(int x)//树形dp{
   	v[x]=true;	f[x]=1;g[x]=2147483647/3;	if(x==root) g[x]=0;	for(int i=ls[x];i;i=a[i].next)	{
   		int y=a[i].to;		if(i==mark||y==fa[x]) continue;		fa[y]=x;		dp(y);		g[x]+=min(f[y],g[y]);		g[x]=min(g[x],f[x]+f[y]-1);		f[x]+=min(f[y],g[y]);	}	return;}int main(){
   	scanf("%d",&n);	for(int i=1;i<=n;i++)	    scanf("%d",&d[i]),addl(d[i],i);	for(int i=1;i<=n;i++)	{
   		if(v[i]) continue;		check_c(i);		root=d[mark];dp(mark);//断开环		int maxs=f[mark];		root=0;dp(mark);//连接环		ans+=min(maxs,g[mark]);	}	printf("%d",n-ans);}