P2607 [ZJOI2008]骑士 基环树，树dp;

P2607 [ZJOI2008]骑士

本题本质上就是树dp，和没有上司的舞会差不多，只不过多了一个对基环树的处理。

#include<iostream>

#include<cstring>

#include<string>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=2e6;

int n,cnt;

ll val[maxn];

int root;

int head[maxn];

int vis[maxn];

ll fa[maxn];

ll f[maxn][2];

ll ans;

int rot;

ll max1(ll x,ll y){

	if(x>=y){

		return x;

	}

	return y;

}

inline ll read(){

	ll ret=0,f=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-'){

			f=-f;

		}

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		ret=ret*10+(ch^'0');

		ch=getchar();

	}

	return f*ret;

}

struct node{

	int nex,to;

}e[maxn];

void add(int u,int v){

	cnt++;

	e[cnt].nex=head[u];

	e[cnt].to=v;

	head[u]=cnt;

}

void dp(int x){

	vis[x]=1;//打标记，用处是表明联通块，把该联通块进行标记

	//以便遍历整连接关系，除此之外并无用处

	f[x][1]=val[x];

	f[x][0]=0;

	for(int i=head[x];i;i=e[i].nex){

		int to=e[i].to;

		if(to!=root){

			dp(to);

			f[x][0]+=max1(f[to][0],f[to][1]);

			f[x][1]+=f[to][0];

		}

		else{

			f[to][1]=-maxn;//将环删边，定有一点不能选，故定此点不选

		}

	}

}

void find(int x){

	vis[x]=1;

	root=x;

	while(!vis[fa[root]]){//我们的目的是为了找环，而且该连通块先前一定未遍历过

		//故该方法可以找出环来

		root=fa[root];

		vis[root]=1;

	}

	/*

	该题中图的特殊性

	导致找环必须要从下到上

	若从上到下

	那么如果起点为树边就无法找到环

	该图的根为环

	*/

	dp(root);

	ll t;

	t=max(f[root][1],f[root][0]);//删一条边不选边上一点的情况下，该联通块的最大值

	root=fa[root];

	dp(root);

	ans+=max1(t,max1(f[root][1],f[root][0])); //将两种情况比较；

}

int main(){

	n=read();

	int x;

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

		val[i]=read();

		x=read();

		add(x,i);

		fa[i]=x;

	}

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

		if(!vis[i]){

			find(i);

		}

	}

	cout<<ans;

	return 0;

}

快去ac吧