[bzoj1040]-[ZJOI2008]骑士

题目（bzoj）
这题一看就是个dp......O（n）的树形dp。
然后这就是个基环树dp，基环树dp的套路就是：断环成树，树形dp
所以就这么整吧！
dp[u][0]表示u这个点不选时的最大值，dp[u][1]表示选这个点时的最大值。
状态转移很好写，
dp[u][0]=∑max(dp[v][0],dp[v][1])，
dp[u][1]=∑dp[v][0]，
初始值为dp[u][0]=0,dp[u][1]=a[u]。
设每次断的边的两个端点为x1,x2，并且强制这个点不能选，
那么ans就加上max(dp[x1][0],dp[x2][0])；
如果没有断环，就直接ans加上dp[i][0]，
完毕。
另外注意一下重边的情况：也很简单，弄个时间戳标记一下即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <climits>
#define ll long long
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define readf(f) scanf(
using namespace std;
template <class _E> inline void read(_E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
int dfn[1000005],idx;
int n;
ll a[1000005];
ll dp[1000005][2];
int vis[1000005];
bool flag;
struct edge{
	int vk;
	int nxt;
	bool exist;
}e[2000005];
int t,head[1000005];
inline void ad(int u,int v)
{
	e[++t].vk=v;
	e[t].nxt=head[u];
	e[t].exist=true;
	head[u]=t;
}
int x1,x2;
void dfs_huan(int u,int fa)
{
	++vis[u];
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==fa) continue;
		if (vis[v]==1 && !flag)
		{
			x1=u,x2=v;
			flag=true;
		}
		else if (!vis[v])
			dfs_huan(v,u);
	}
	++vis[u];
}
void dfs_dp(int u,int fa)
{
	dfn[u]=idx;
	dp[u][0]=0,dp[u][1]=a[u];
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==fa || !e[i].exist || dfn[v]>=idx) continue;
		dfs_dp(v,u);
		dp[u][0]+=max(dp[v][0],dp[v][1]);
		dp[u][1]+=dp[v][0];
	}
}
ll ans;
int main()
{
	read(n);
	for (int i=1;i<=n;++i)
	{
		int vv;
		read(a[i]),read(vv);
		ad(i,vv),ad(vv,i);
	}
	for (int i=1;i<=n;++i)
	{
		if (!vis[i])
		{
			flag=false;
			ll tmp;
			dfs_huan(i,0);
			if (flag)
			{
				for (int k=head[x1];k;k=e[k].nxt)
					if (e[k].vk==x2) e[k].exist=false;
				for (int k=head[x2];k;k=e[k].nxt)
					if (e[k].vk==x1) e[k].exist=false;
				++idx;dfs_dp(x1,0);
				tmp=dp[x1][0];
				++idx;dfs_dp(x2,0);
				tmp=max(tmp,dp[x2][0]);
				ans+=tmp;
			}
			else
			{
				++idx;dfs_dp(i,0);
				ans+=max(dp[i][0],dp[i][1]);
			}
		}
	}
	printf(
	return 0;
}