Problem

Description

给出$N$个点，每个点的出度均为$1$，给出这$N$个点初始指向的点 $A_i$，和改变这个点指向的目标所需要的价值$C_i$.

求让所有点强连通的最小花费.

Input

$N$

$A_i$ $C_i$

…

Output

一行输出答案，即最小需要的代价。

Sample Input

4
2 2
1 3
4 2
3 3

Sample Output

4

HINT

$1 \le N 10^5$

时限200ms

Solution

Analysis

一个显然的结论是最后形成的图一定是个环。

考虑一种贪心策略，即每次保证一个点的入度权值最大点。

考虑保留之后形成的状态可能是若干个rho形状，考虑破环为链。

即 分割最小的点。

Attention

特判一开始是环的情况

Code

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il void filejudge(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
namespace io{
    这是快读
}
using io::read;
/*----- head end -----*/
const int N=100010;
ll n,a[N],c[N],vis[N],mx[N],mx2[N],ans;
int main(){
    n=read();
    rep(i,1,n) a[i]=read(),c[i]=read(),ans+=c[i];
    rep(i,1,n){
        int u=i,sz=0;
        for(;!vis[u];u=a[u]) vis[u]=i;
        if(i==vis[u]){
            for(;vis[u]!=-1;u=a[u]){ sz++;vis[u]=-1;}
            if(sz==n){ puts("0");return 0;}
        }//环上的点被标记为-1
    }
    rep(i,1,n){
        mx[a[i]]=max(mx[a[i]],c[i]);
        if(vis[i]!=-1) mx2[a[i]]=max(mx2[a[i]],c[i]);
        //环上额外记录
    }
    //贪心减少第一类点
    rep(i,1,n) ans-=mx[i];
    rep(i,1,n){
        if(vis[i]==-1){
            //环上找最小点
            ll res=LLONG_MAX;
            for(register int u=i;vis[u]==-1;u=a[u]){
                vis[u]=0;
                res=min(res,mx[u]-mx2[u]);
            }
            ans+=res;
        }
    }
    printf("%lld",ans);
    return 0;
}