由于每个点只能向外连一条边，\(n\) 个点 \(n\) 条边，中间有环，故不能再向外连边，所以构成基环内向树森林。
叶子节点入度为 \(0\)，故可以判断叶子结点，倒推回环根，存每个子树的最大深度。
最终 dp 处理每个基环树的环，分两种情况：
- 经过环：分两种情况：顺时针和逆时针，前缀和优化跑一边即可。
- 不经过环：答案为子树直径
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[1000010],w[1000010];
int ind[1000010];
queue<int> q;
int l[1000010],d[1000010];
bool vis[1000010];
int ans;
int max(int a,int b,int c){
return max(a,max(b,c));
}
int solve(int rt){
int p=rt;
int max1=l[rt],max2=l[rt],ret1=0,ret2=-2147483648,ret3=d[rt];
int sum=w[rt];
while((p=a[p])!=rt){
vis[p]=1;
ret1=max(ret1,l[p]+sum+max1);
ret2=max(ret2,l[p]-sum+max2);
ret3=max(ret3,d[p]);
max1=max(max1,l[p]-sum);
max2=max(max2,l[p]+sum);
sum+=w[p];
}
return max(ret1,ret2+sum,ret3);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>w[i];
ind[a[i]]++;
}
for(int i=1;i<=n;i++)if(!ind[i])q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
int v=a[u];
d[v]=max(d[v],d[u],l[v]+l[u]+w[u]);
l[v]=max(l[v],l[u]+w[u]);
ind[v]--;
if(!ind[v])q.push(v);
}
for(int i=1;i<=n;i++){
if(ind[i]&&!vis[i])ans+=solve(i);
}
cout<<ans;
return 0;
}