骑士 bzoj-1040 ZJOI-2008

    题目大意:n个骑士,每个骑士有权值val和一个讨厌的骑士。如果一个骑士讨厌另一个骑士那么他们将不会一起出战。问出战的骑士最大atk是多少。

    注释:$1\le n,atk\le 10^6$。

      想法:树形dp的一道好题qwq。大师说是基环树的一道裸题。什么是基环树?就是一个点数条边的连通图,这样的连通图有且只有一个环。证明:挖坑代填。

        那么这道题,首先如果两个骑士A讨厌B,其实和B讨厌A的效果是一样的,所以我们连双向边。那么对于任意的连通块,一定存在一个环,我们取环上不同相连两点x和y,将它们之间的边强行断掉。此时,由于x和y在环上,必定仍是联通的,之前如果两点连通经过x到y的边d,那么可以将那条路径等价到现在x到y的路径。如果两点连通不经过d,无影响。那么现在就是一棵树了,相邻两点不能同时选取,每个点有权值...没有上司的舞会(没有上司的舞会?)啊!然后分别以x和y为根跑树形dp,f[i]表示选i的最大战斗力,g[i]表示不选i的最大战斗力。然后我们明白:由于x和y的边使我们强行断掉的,他们之间其实仍是相连的,所以我们在以x为根的时候钦定y一定不能选;以y为根同理。

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000010 
using namespace std;
typedef long long ll;
int fa[N];
ll g[N],f[N],val[N];
int to[N<<1],nxt[N<<1],head[N],tot;
int cnt,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 pos,int fa)//树形dp
{
	f[pos]=val[pos];//表示选取pos节点的最大权值
	g[pos]=0;//表示选取pos节点的最大权值
	for(int i=head[pos];i;i=nxt[i])
	{
		if(to[i]==fa) continue;
		dfs(to[i],pos);
		f[pos]+=g[to[i]];
		g[pos]+=max(f[to[i]],g[to[i]]);
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	ll ans=0;
	for(int b,i=1;i<=n;i++)
	{
		scanf("%lld%d",&val[i],&b);
		if(find(i)!=find(b))
		{
			add(b,i);add(i,b);
			fa[find(b)]=find(i);
		}
		else
		{
			ra[++cnt]=i;
			rb[cnt]=b;
		}
	}
	ll maxn=0;
	for(int i=1;i<=cnt;i++)
	{
		dfs(ra[i],0),maxn=g[ra[i]];//小技巧,选取x可以钦定x是g,选取y同理,这样和上述题解达到的效果一致
		dfs(rb[i],0),maxn=max(maxn,g[rb[i]]);//而且实现简单。
		ans+=maxn;
	}
	printf("%lld\n",ans);
	return 0;
}

    小结:错误1.题目中要求的是每一个maxn的综合,我直接输出了... ...

         2.49行有一个小技巧:由于已经路径压缩完毕,所以可以写成fa[fa[b]]=fa[i],省去调用函数的时间。