记录：https://www.luogu.com.cn/record/152030816

/*
对于环上的 dp 处理：
复制两倍
f[i]=max(f[i],f[i]+f[j]+s[i]-s[j])
单调队列维护
*/
#include<iostream>
#include<vector>
#include<cstring>
#include<deque>
#define int long long
using namespace std;
int n,to[100010],dis[100010];
int a[200010],s[200010],cur;
int sz[100010],f[100010];//f[i] 表示 i 及 i 的子树中到 i 的最大距离
int maxn,maxn2,maxid,ans;
struct edge{int x,w;};
vector<edge>v[100010];
bool flag[100010],flag2[100010];
struct node{int id,x;};
deque<node>q;
void dfs1(int x,int last)
{
    sz[x]=1;
    for(auto e:v[x])
        if(!flag[e.x])
        {
            dfs1(e.x,x);
            sz[x]+=sz[e.x];
            f[x]=max(f[x],f[e.x]+e.w);
        }
}
void dfs2(int x,int last,int d)
{
    if(d>maxn2)maxn2=d,maxid=x;
    for(auto e:v[x])
        if(!flag[e.x])
            dfs2(e.x,x,d+e.w);
}
void dfs3(int x,int last,int d,int y)
{
    maxn2=max(maxn2,d);
    for(auto e:v[x])
        if(!flag[e.x]&&e.x!=y)
        {
            flag[e.x]=1;
            dfs3(e.x,x,d+e.w,y);
        }
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>to[i]>>dis[i];
        v[i].push_back({to[i],dis[i]});
        v[to[i]].push_back({i,dis[i]});
    }
    for(int i=1;i<=n;i++)
        if(!flag[i])
        {
            //找出当前基环树的环
            int now=i;
            while(!flag2[now])flag2[now]=1,now=to[now];
            int now2=now;
            cur=0;
            do
            {
                flag[now]=1,a[++cur]=now,s[cur]=s[cur-1]+dis[now],now=to[now];
            }while(now!=now2);
            for(int j=cur+1;j<=2*cur;j++)
                a[j]=a[j-cur],s[j]=s[cur]+s[j-cur];
            for(int j=1;j<=2*cur;j++)s[j]-=dis[a[j]];
            //在每个子树中做 dp
            maxn=0;
            memset(f,0,sizeof(f));
            for(int j=1;j<=cur;j++)
            {
                maxn2=-1;
                dfs1(a[j],0);
                dfs2(a[j],0,0);
                flag[maxid]=1;
                dfs3(maxid,0,0,a[j]);
                maxn=max(maxn,maxn2);
            }
            while(!q.empty())q.pop_front();
            for(int j=1;j<=2*cur;j++)
            {
                while(!q.empty()&&q.front().id<=j-cur)q.pop_front();
                maxn=max(maxn,q.front().x+f[a[j]]+s[j]);
                //cout<<j<<" "<<q.front().x+f[a[j]]+s[j]<<endl;
                int now=f[a[j]]-s[j];
                while(!q.empty()&&q.back().x>=now)q.pop_back();
                q.push_back({j,now});
            }
            //cout<<maxn<<endl;
            ans+=maxn;
            //cout<<"======================"<<endl;
            
        }
    cout<<ans<<endl;
    return 0;
}