bzoj 1040: [ZJOI2008]骑士【基环树+树形dp】

没考虑可以连着两个不选……直接染色了

实际上是基环森林，对于每棵基环树，dfs找出一个环边，然后断掉这条边，分别对这条边的两端点做一边treedp，取max加进答案里

treedp是设f[u]为选u点，g[u]为不选u点，然后随便转移一下就行了

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1000005;

int n,h[N],cnt=1,x,y,eg;

long long a[N],f[N],g[N],ans;

bool v[N];

struct qwe

{

	int ne,to;

}e[N<<1];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	h[u]=cnt;

}

void dfs(int u,int fr)

{

	v[u]=1;

	for(int i=h[u];i;i=e[i].ne)

		if((i^1)!=fr)

		{

			if(v[e[i].to])

				x=u,y=e[i].to,eg=i;

			else

				dfs(e[i].to,i);

		}

}

void dp(int u,int fr)

{

	f[u]=a[u],g[u]=0;

	for(int i=h[u];i;i=e[i].ne)

		if((i^1)!=fr&&i!=eg&&(i^1)!=eg)

		{

			dp(e[i].to,i);

			f[u]+=g[e[i].to];

			g[u]+=max(f[e[i].to],g[e[i].to]);

		}

}

int main()

{

	n=read();

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

	{

		a[i]=read(),u=read();

		add(i,u),add(u,i);

	}

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

		if(!v[i])

		{

			dfs(i,0);

			dp(x,0);

			long long nw=g[x];

			dp(y,0);

			ans+=max(nw,g[y]);

		}

	printf("%lld\n",ans);

	return 0;

}

巴特西

bzoj 1040: [ZJOI2008]骑士【基环树+树形dp】

最新文章

热门文章