记录编号	370285	评测结果	AAAAAAAAAE
题目名称	[ZJOI 2008] 骑士	最终得分	90
用户昵称	Cydiater	是否通过	未通过
代码语言	C++	运行时间	1.439 s
提交时间	2017-02-13 09:50:34	内存使用	122.38 MiB

//BZOJ1040
//by Cydiater
//2017.2.13
#include <iostream>
#include <map>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <queue>
#include <bitset>
#include <set>
#include <vector>
#include <complex>
using namespace std;
#define ll long long
#define up(i,j,n)	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)
#define FILE		"bzoj_1040"
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int N,LINK[MAXN],dfn[MAXN],low[MAXN],dfs_clock=0,stack[MAXN],top=0,NN,len=0;
struct edge{
	int y,next;
}e[MAXN<<1];
ll val[MAXN],f[MAXN][2],arr[MAXN][2],g[MAXN][2][2],ans=0;
vector<int>E[MAXN<<1];
namespace solution{
	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}
	inline void Insert(int x,int y){insert(x,y);insert(y,x);}
	void Prepare(){
		N=read();
		up(i,1,N){
			val[i]=read();int y=read();
			Insert(i,y);
		}
		NN=N;
	}
	void Tarjan(int node){
		dfn[node]=low[node]=++dfs_clock;
		stack[++top]=node;
		Auto(i,node)if(!dfn[e[i].y]){
			Tarjan(e[i].y);
			cmin(low[node],low[e[i].y]);
			if(low[e[i].y]>=dfn[node]){
				NN++;int tmp;
				do{
					tmp=stack[top--];
					E[NN].push_back(tmp);
				}while(tmp!=e[i].y);
				E[node].push_back(NN);
			}
		}else cmin(low[node],dfn[e[i].y]);
	}
	void TreeDP(int node){
		int siz=E[node].size();
		f[node][0]=f[node][1]=0;
		if(node>N){
			up(i,0,siz-1)TreeDP(E[node][i]);
			//cout<<node<<' '<<siz+1<<endl;
			up(i,0,siz-1){
				arr[i][0]=f[E[node][i]][0];
				arr[i][1]=f[E[node][i]][1];
				g[i][0][0]=g[i][0][1]=g[i][1][0]=g[i][1][1]=0;
			}
			g[siz][0][0]=g[siz][0][1]=g[siz][1][0]=g[siz][1][1]=0;
			arr[siz][0]=arr[siz][1]=0;
			//up(i,0,siz)cout<<arr[i][0]<<' '<<arr[i][1]<<"| ";
			//cout<<endl;
			g[0][1][1]=arr[0][1];
			g[0][0][0]=arr[0][0];
			up(i,1,siz){
				up(j,0,1){
					cmax(g[i][0][j],g[i-1][0][j]+arr[i][0]);
					cmax(g[i][0][j],g[i-1][1][j]+arr[i][0]);
					cmax(g[i][1][j],g[i-1][0][j]+arr[i][1]);
				}
			}
			f[node][0]=max(g[siz][0][0],g[siz][0][1]);
			f[node][1]=g[siz][1][0];
			//cout<<f[node][0]<<' '<<f[node][1]<<endl<<endl;
		}else{
			up(i,0,siz-1){
				TreeDP(E[node][i]);
				f[node][0]+=max(f[E[node][i]][0],f[E[node][i]][1]);
				f[node][1]+=f[E[node][i]][1];
			}
			f[node][1]+=val[node];
		}
	}
	void Solve(){
		up(i,1,N)if(!dfn[i]){
			Tarjan(i);
			TreeDP(i);
			ans+=max(f[i][0],f[i][1]);
		}
		cout<<ans<<endl;
	}
}
int main(){
	//freopen("input.in","r",stdin);
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}