【问题描述】
n 个小朋友在玩传球。 小朋友们用 1 到 n 的正整数编号。 每个小朋友有一个固定的传球
对象，第 i 个小朋友在接到球后会将球传给第 ai个小朋友， 并且第 i 个小朋友与第 ai个小朋
友之间的距离为 di。
一次传球接力是这样进行的：由一个小朋友发球，将球传给他的传球对象，之后接到球
的小朋友再将球传给自己的传球对象，如此传球若干次后停止。 期间，包括发球者在内，每
个小朋友至多只能拿到球一次。 一次传球接力的总距离是每次传球的距离的总和。
小朋友们想进行一次总距离最长的传球接力，现在需要你帮助他们求出满足上述要求的
传球接力的最长总距离。
【输入】
输入的第 1 行包含 1 个整数 n。
接下来的 n 行，第 i 行包含两个整数 ai 和 di，意义如题目中所述， 两个数间用一个空格
隔开。
【 输出】
输出包含 1 个数， 表示传球接力总距离的最大值。
【输入输出样例 1】
| pass.in | pass.out |
| 5 2 1 3 2 4 1 2 3 3 3 |
7 |
见选手目录下的 pass / pass1.in 与 pass / pass1.out
【输入输出样例 1 说明】
由第 5 个小朋友发球， 传给第 3 个小朋友，再传给第 4 个小朋友，总距离为 3+1+3=7
【输入输出样例 2】
见选手目录下的 pass / pass2.in 与 pass / pass2.out
【数据规模与约定】
对于 50%的数据， n≤1,000
对于 100%的数据， n≤500,000， 1≤ai≤n， ai≠i， 1≤di≤10,000
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
/*
类似于信息传递，注意环外的也要算
*/
using namespace std;
const int maxn = ;
int n,a[maxn],d[maxn],f[maxn],vis[maxn];
ll w[maxn],cir_w[maxn],ans;
bool in_cir;
int cir,is_cir[maxn],cir_u;
int read(){
char ch=getchar();
int x=,f=;
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
void dfs(int u){
vis[u] = ;
if(!vis[a[u]]){
dfs(a[u]);
}else if(vis[a[u]] == ){
cir++;
in_cir = true;
is_cir[u] = cir;
cir_w[cir] = d[u];
cir_u = a[u];
f[a[u]] = d[u];
vis[u] = ;
return;
}
if(in_cir){
is_cir[u] = cir;
cir_w[cir] += d[u];
f[a[u]] = d[u];
if(u == cir_u){
//cout<<"!!"<<u<<endl;
in_cir = false;
ans = max(ans,cir_w[cir]);
}
vis[u] = ;
return;
}
if(is_cir[a[u]]) w[u] = cir_w[is_cir[a[u]]] + d[u] - f[a[u]];
else w[u] = w[a[u]] + d[u];
ans = max(ans,w[u]);
//cout<<u<<"!!"<<w[u]<<endl;
vis[u] = ;
//cout<<u<<" "<<w[u]<<endl;
}
int main(){
int size = << ; // 256MB
char *p = (char*)malloc(size) + size;
__asm__("movl %0, %%esp\n" :: "r"(p));
freopen("pass.in","r",stdin);
freopen("pass.out","w",stdout);
n = read();
for(int i = ;i <= n;i++){
a[i] = read();
d[i] = read();
}
for(int i = ;i <= n;i++){
if(!vis[i]) dfs(i);
}
cout<<ans<<endl;
return ;
}