蒟蒻 85 pts 求助（

翻了下评测记录发现和大家都不一样（悲

QAQ

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <random>
#include <bitset>
#define int long long
//#define double long double
#define p1(x) x.first
#define p2(x) x.second
#define i128  __int128_t
//#pragma GCC optimize(2)
#define w(x) t[x].w
#define sw(x) t[x].sw
#define siz(x) t[x].siz
#define lc(x) t[x].c[0]
#define rc(x) t[x].c[1]
#define d(x) t[x].d
#define pii pair<int,int>
//若汁记好了以后再用Ctrl+C/+V你就是狗
using namespace std;
int n;
vector<pii>g[1000300];
stack<pii>S;
bool vis[1000300];
bool ins[1000300];
bool rg[1000300];
vector<pii>RG;
vector<pii>T;
vector<int>TR;
int dp[1000300][2];
inline void dfs(int u,int lst,int fa){
    vis[u]=1;
    ins[u]=1;
    S.push({u,lst});
    bool db=0;
    for(auto e:g[u]){
        int v=p1(e);
        int w=p2(e);
        //cout<<u<<"x"<<v<<"  ";
        if(rg[v])continue;
        if(v==fa&&!db){db=1;continue;}
        db=0;
        if(ins[v]){
            int lst=w;
            while(!S.empty()){
                pii A=S.top();
                S.pop();
                rg[p1(A)]=1;
                RG.push_back({p1(A),lst});
                lst=p2(A);
                if(p1(A)==v)
                    break;
            }
        }
        else if(!vis[v])dfs(v,w,u);
    }
    ins[u]=0;
    if(!S.empty()&&p1(S.top())==u)S.pop();
}
inline void dfs(int u){
    rg[u]=1;
    TR.push_back(u);
    for(auto e:g[u]){
        int v=p1(e);
        int w=p2(e);
        if(rg[v])continue;
        dfs(v);
        int t=dp[v][0]+w;
        if(t>dp[u][0])
            dp[u][1]=dp[u][0],dp[u][0]=t;
        else dp[u][1]=max(dp[u][1],t);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    // freopen("/Users/noip2019/Downloads/P6247_4.in","r",stdin);
//    freopen("","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,w;
        cin>>x>>w;
        g[i].push_back({x,w});
        g[x].push_back({i,w});
    }
//    for(int i=1;i<=n;i++){
//        cout<<i<<":";
//        for(auto e:g[i])
//            cout<<p1(e)<<" ";
//        cout<<endl;
//    }
    int res=0;
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            T.clear();
            RG.clear();
            TR.clear();
            while(!S.empty())S.pop();
            dfs(i,0,0);
            for(auto e:RG)
            dfs(p1(e));
            int m=RG.size();
            //cout<<m<<endl;
            int cnt=0;
            for(auto e:RG)
                T.push_back(e);
            for(int x:TR)
            cnt=max(cnt,dp[x][1]+dp[x][0]);
            for(auto e:RG)
                T.push_back(e);
           
            int t=-p2((*T.begin()));
            for(auto &e:T){

                t+=p2(e);
                p2(e)=t;
                //cout<<p1(e)<<" "<<p2(e)<<endl;
                
            }
            deque<pii>q;
            int k=2*m;
            
            for(int i=0;i<k;i++){
                pii e=T[i];
                int w=dp[p1(e)][0]+p2(e);
                while(!q.empty()&&p2(q.back())<=w)q.pop_back();
                q.push_back({i,w});
                while(!q.empty()&&p1(q.front())<=i-m+1)q.pop_front();
                //q.push_back({i,w});
                if(i>=m-1&&!q.empty())
                    cnt=max(cnt,p2(q.front())-p2(T[i-m+1])+dp[p1(T[i-m+1])][0]);
                
            }
            res+=cnt;
    }
    cout<<res<<endl;
    return 0;
}