rt，思路是使用单调队列优化求基环树直径，80pts。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 1000006
using namespace std;
struct Node{int to,next,w;}edge[N<<1];
int cnt,head[N],maxlen[N],d[N],maxd[N],ans,a[N<<2],b[N<<2],bn,ringid,flag;
int q[N<<2],hd,tl;
int dis[N];
void init()
{
    for(int i=0;i<(N<<1);i++)edge[i].next=-1;
    for(int i=0;i<N;i++)head[i]=-1;
    cnt=0;
}
void addedge(int u,int v,int w)
{
    edge[cnt]={v,head[u],w};
    head[u]=cnt++;
}
int n,vis[N],ring[N],st,h[N];
vector<int> path_len,path,r[N];
void dfs(int u,int lastedge)
{
    vis[u]=1,h[u]=1;
    for(int i=head[u];~i;i=edge[i].next)
    {
        if((i^lastedge)==1)continue;
        int v=edge[i].to;
        if(vis[v]){st=v;continue;}
        dfs(v,i);
    }
    vis[u]=0;
}
void getring(int u,int lastedge,int id)
{
    vis[u]=1,path.push_back(u);
    if(~lastedge)path_len.push_back(edge[lastedge].w);
    for(int i=head[u];~i;i=edge[i].next)
    {
        if((i^lastedge)==1)continue;
        int v=edge[i].to;
        if(vis[v])
        {
            for(int p:path)ring[p]=1;
            if(!flag)for(int j=0;j<path.size();j++)
            {
                r[id].push_back(path[j]);
                if(j>0)dis[path[j]]=path_len[j-1];
                else dis[path[j]]=edge[i].w;
            }
            flag=1;
            continue;
        }
        getring(v,i,id);
    }
    vis[u]=0,path.pop_back();
    if(~lastedge)path_len.pop_back();
}
void getd(int u,int fa,int rt)
{
    int max1=0,max2=0;
    for(int i=head[u];~i;i=edge[i].next)
    {
        int v=edge[i].to,w=edge[i].w;
        if(v==fa||ring[v])continue;
        getd(v,u,rt);
        maxlen[u]=max(maxlen[u],maxlen[v]+w);
        if(maxlen[u]>=max1)max2=max1,max1=maxlen[u];
        else if(maxlen[u]>max2)max2=maxlen[u];
    }
    d[u]=max1+max2;
    maxd[rt]=max(maxd[rt],d[u]);
}
int solve(int id)
{
    bn=0;
    for(int j:r[id])a[++bn]=j;
    for(int j:r[id])a[++bn]=j;
    b[1]=1;
    for(int i=2;i<=bn;i++)b[i]=b[i-1]+dis[a[i]];
    int ret=0;
    for(int i:r[id])ret=max(ret,maxd[i]);
    //for(int i=1;i<=bn;i++)cout<<a[i]<<' '<<b[i]<<endl;
    hd=1,tl=0;
    for(int i=1;i<=bn;i++)
    {
        int now=maxlen[a[i]]-b[i];
        while(hd<=tl&&maxlen[a[q[tl]]]-b[q[tl]]<now)tl--;
        q[++tl]=i;
        while(hd<=tl&&q[tl]-q[hd]+1>bn/2)hd++;
        ret=max(ret,maxlen[a[q[hd]]]-b[q[hd]]+maxlen[a[i]]+b[i]);
    }
        //cout<<ret<<endl;
    return ret;
}
main()
{
    init();
    scanf("%lld",&n);
    for(int i=1,v,w;i<=n;i++)
    {
        scanf("%lld%lld",&v,&w);
        addedge(i,v,w),addedge(v,i,w);
    }
    for(int i=1;i<=n;i++)
        if(!h[i])
            flag=0,dfs(i,-1),getring(st,-1,++ringid);
    for(int i=1;i<=n;i++)
        if(ring[i])getd(i,-1,i);
    for(int i=1;i<=ringid;i++)ans+=solve(i);
    printf("%lld",ans);
    return 0;
}