记录编号	459960	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008] 骑士	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.775 s
提交时间	2017-10-16 11:14:01	内存使用	31.15 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000005
int read() {
	register int s=0,f=1;
	register char ch=getchar();
	for( ; ch<'0'||ch>'9'; f=(ch=='-')?-1:f,ch=getchar()) ;
	for( ; ch>='0'&&ch<='9'; s=s*10+(ch^48),ch=getchar()) ;
	return s*f;
}
int L,R,n,r[N*2],tot,s[N*2];
long long f[N][2],Ans,Max,power[N*2];
bool vis[N],flag;
struct DATE {int to,next;} c[N*2];
void add(int x,int y) {
	c[++tot]=(DATE) {y,r[x]};
	r[x]=tot;
}
void dfs(int x,int fa) {
	vis[x]=true;
	for(int i=r[x]; ~i; i=c[i].next) {
		if(c[i].to!=fa) {
			if(vis[c[i].to]) {
				L=x,R=c[i].to;s[i]=s[i^1]=-1;
				flag=true; break;
			} dfs(c[i].to,x);
		} 
	}
}
void Dp(int fr,int fa,int to) {
	vis[fr]=true;
	if(fr!=to) f[fr][1]=power[fr];
	else f[fr][1]=0;
	f[fr][0]=0;
	for(int i=r[fr]; ~i; i=c[i].next) {
		if(c[i].to!=fa&&s[i]!=-1) {
			Dp(c[i].to,fr,to);
			f[fr][0]+=max(f[c[i].to][0],f[c[i].to][1]);
			f[fr][1]+=f[c[i].to][0];
		}
	}
}
int Main() {
	freopen("bzoj_1040.in","r",stdin);
	freopen("bzoj_1040.out","w",stdout);
	n=read(),tot=-1;
	memset(r,0xff,sizeof(r));
	for(int x,i=1; i<=n; ++i) {
		power[i]=read(),x=read();
		add(i,x),add(x,i);		
	}
	for(int i=1; i<=n; ++i) {
		if(!vis[i]) {
			Max=0,flag=false;
			dfs(i,0);
			Dp(L,0,R),Max=max(f[L][0],f[L][1]);
			Dp(R,0,L),Max=max(Max,max(f[R][0],f[R][1]));
			Ans+=Max;
		}
	} printf("%lld",Ans);
	return 0;
} 
int hehe=Main();
signed main(){;}