P2607求调

#include<bits/stdc++.h>
using namespace std;
long long n,fa[1100000],f[1100000][2],a[1100000],v[1100000],root,ans,cut,h[1100000];
struct node{
	long long n,t;
}q[1100000];
void add(long long from,long long to){
	cut++;
	q[cut].n=h[from];
	q[cut].t=to;
	h[from]=cut;
	return;
}
void dfs(long long x){
	v[x]=1;
	f[x][0]=0;
	f[x][1]=a[x];
	for(int i=h[x];i;i=q[i].n){
		long long y=q[i].t;
		if(y!=root){
			dfs(y);
			f[x][1]+=f[y][0];
			f[x][0]+=max(f[y][0],f[y][1]);
		}
		else{
			f[y][1]=-2000000;
		}
	}
	return;
} 
void findl(long long x){
	root=x;
	v[x]=1;
	while(!v[fa[root]]){
		root=fa[root];
		v[root]=1;
	}
	dfs(root);
	long long t=max(f[root][0],f[root][1]);
	v[root]=1;
	root=fa[root];
	dfs(root);
	ans+=max(t,max(f[root][0],f[root][1]));
	return;
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		long long k;
		scanf("%lld%lld",&a[i],&k);
		add(k,i);
	}
	for(int i=1;i<=n;i++){
		if(!v[i]){
			findl(i);
		}
	}
	printf("%lld",ans);
	return 0;
}