[bzoj3037/2068]创世纪[Poi2004]SZP_树形dp_并查集_基环树

创世纪 SZP bzoj-3037/2068 Poi-2004

题目大意：给你n个物品，每个物品可以且仅可以控制一个物品。问：选取一些物品，使得对于任意的一个被选取的物品来讲，都存在一个没有被选取的物品，而且选取的个数最大。

注释：$1\le n \le 10^6$。

想法：显然，和骑士类似的，是一个基环树森林。如果A物品可以控制B物品，那就有B物品向A物品连边。对于每一个基环树，如果这个基环树是树的话显然变成树形dp入门题，暴力树形dp即可。然后对于基环树来讲，我们依然记录环上两点，分别以这两点为根，然后特判树形dp即可。

最后，附上丑陋的代码... ...

#include <cstdio>

#include <cstring>

#include <iostream>

#define N 1000010

using namespace std;

int n,m,ans,now,tot;

int to[N],nxt[N],head[N],f[N],g[N],fa[N],ra[N],rb[N];

inline void add(int x,int y)

{

	to[++tot]=y;

	nxt[tot]=head[x];

	head[x]=tot;

}

int find(int x)

{

	return (fa[x]==x)?x:(fa[x]=find(fa[x]));

}

void dfs(int x)

{

	int t=1<<30;

	g[x]=0;

	for(int i=head[x];i;i=nxt[i])

	{

		if(to[i]!=now)

			dfs(to[i]);

		g[x]+=max(f[to[i]],g[to[i]]);

		t=min(t,max(f[to[i]],g[to[i]])-g[to[i]]);

	}

	f[x]=g[x]+1-t;

}

int main()

{

	scanf("%d",&n);

	int a;

	for(int i=1;i<=n;i++)

		fa[i]=i;

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a);

		if(find(a)!=find(i))

		{

			add(a,i);

			fa[fa[a]]=fa[i];

		}

		else

			ra[++m]=a,rb[m]=i;

	}

	for(int i=1;i<=m;i++)

	{

		dfs(ra[i]),now=ra[i];

		dfs(rb[i]),a=f[rb[i]];

		f[ra[i]]=g[ra[i]]+1;

		dfs(rb[i]),ans+=max(a,g[rb[i]]);

	}

	printf("%d",ans);

	return 0;

}

小结：基环树dp是一种常见的，树形dp带基环树的处理方法。这里有一个问题(By JhinLzh)，问什么输出答案上面的for循环中的第一个dfs有用？明明在第二个dfs中所有的f和g都被更新了，为什么还要dfs？因为在第一个dfs中我们对f是强行负值，这样对于一些叶子节点来讲t值是没有更改的，这就导致f值在最后是一个极小值，这样的f是不会更新答案的。如果不写第一个dfs，使得一些在本不能更新答案的点更新了答案，导致答案错误。所以第一个dfs是必要的。