首先对于一棵树我们可以tree_dp来解决这个问题，那么对于环上每个点为根的树我们可以求出这个树的一端为根的最长链，并且在tree_dp的过程中更新答案。那么我们对于环，从某个点断开，破环为链，然后再用DP来解决这个问题。
备注：很久之前的一道题，刚转的c++，然后T了，也懒得改了。
/**************************************************************
Problem: 1791
User: BLADEVIL
Language: C++
Result: Time_Limit_Exceed
****************************************************************/ //By BLADEVIL
#include <cstdio>
#include <cstring>
#define maxn 1000010
#define LL long long using namespace std; LL n,time,l;
LL other[maxn<<],last[maxn],pre[maxn<<],dfn[maxn],low[maxn],vis[maxn],que[maxn],a[maxn],xx[maxn];
LL ans;
LL len[maxn<<],max1[maxn],max2[maxn],sum[maxn],w[maxn],yy[maxn],maxlen[maxn];
LL save; void getmin(LL &x,LL y)
{if (y<x) x=y;} void connect(LL x,LL y,LL z) {
pre[++l]=last[x];
last[x]=l;
other[l]=y;
len[l]=z;
//if (y>x) printf("%d %d %lld\n",x,y,z);
} void dfs(LL x,LL fa) {
dfn[x]=low[x]=++time;
for (LL q=last[x];q;q=pre[q]) {
if (other[q]==fa) continue;
if (!low[other[q]]) {
dfs(other[q],x);
getmin(low[x],low[other[q]]);
} else getmin(low[x],dfn[other[q]]);
}
if (low[x]!=dfn[x]) save=low[x];
} void dp(LL x) {
memset(que,,sizeof que);
LL h=,t=1ll;
que[]=x; vis[x]=1ll;
while (h<t) {
LL cur=que[++h];
for (LL q=last[cur];q;q=pre[q]) {
if (low[other[q]]==low[x]) continue;
if (vis[other[q]]) continue;
vis[other[q]]=vis[cur]+1ll;
que[++t]=other[q];
}
}
//for (LL i=1;i<=t;i++) printf("%d ",que[i]); printf("\n");
for (LL i=t;i;i--)
for (LL q=last[que[i]];q;q=pre[q]) {
if (low[other[q]]==low[x]) continue;
if (vis[other[q]]!=vis[que[i]]+) continue;
//printf(" %d %d\n",que[i],other[q]);
if (max1[other[q]]+len[q]>max1[que[i]])
max2[que[i]]=max1[que[i]],max1[que[i]]=max1[other[q]]+len[q]; else
if (max1[other[q]]+len[q]>max2[que[i]]) max2[que[i]]=max1[other[q]]+len[q];
if (max1[other[q]]+max2[other[q]]>maxlen[que[i]])
maxlen[que[i]]=max1[other[q]]+max2[other[q]];
if (max1[que[i]]+max2[que[i]]>maxlen[que[i]])
maxlen[que[i]]=max1[que[i]]+max2[que[i]];
if (maxlen[que[i]]<maxlen[other[q]]) maxlen[que[i]]=maxlen[other[q]];
}
//for (LL i=1;i<=t;i++) printf("%d %lld %lld %lld\n",que[i],max1[que[i]],max2[que[i]],maxlen[que[i]]);
} void solve(LL x) {
LL now=0ll;
dfs(x,-);
//printf("%d",save);
if (save)
for (LL i=;i<=n;i++) if (low[i]==save) x=i;
save=;
/*if (xx[xx[x]]==x)
{
ans+=(yy[x]>yy[xx[x]])?yy[x]:yy[xx[x]];
return;
}*/
LL cur;
for (LL i=;i<=n;i++) if (low[i]==low[x]) dp(i),cur=i;
//printf(" %lld\n",max1[x]);
LL t=; a[t]=cur;
while () {
for (LL q=last[a[t]];q;q=pre[q]) {
now=(maxlen[a[t]]>now)?maxlen[a[t]]:now;
if (low[other[q]]!=low[x]) continue;
if (other[q]==a[t-]) continue;
a[++t]=other[q]; sum[t]=len[q]; break;
}
if (a[t]==cur) break;
}
//printf(" %d ",x);
//for (LL i=1;i<=t;i++) printf(" %lld %d %d\n",max1[a[i]],a[i],sum[i]);
t--;
for (LL i=;i<=t;i++) a[i+t]=a[i],sum[i+t]=sum[i];
t*=;
//for (LL i=1;i<=t;i++) printf(" %lld %d %d\n",max1[a[i]],a[i],sum[i]);
for (LL i=;i<=t;i++) sum[i]+=sum[i-];
LL len=t>>1ll;
memset(que,,sizeof que);
LL l=,r=; que[]=;
for (LL i=;i<=t;i++) {
if (i-que[l]+>len) l++;
w[i]=max1[a[que[l]]]+max1[a[i]]+sum[i]-sum[que[l]];
//printf("w[i]=%d",w[i]); printf(" %d %d\n",i,que[l]);
while (l<=r&&(max1[a[i]]-sum[i]>max1[a[que[r]]]-sum[que[r]])) r--;
que[++r]=i;
//for (LL i=l;i<=r;i++) printf("|%d ",que[i]); printf("\n");
}
for (LL i=;i<=t;i++) now=(w[i]>now)?w[i]:now;
//printf(" %lld ",ans);
ans+=now;
} int main() {
scanf("%d",&n);
for (LL i=;i<=n;i++) scanf("%d%lld",&xx[i],&yy[i]);
for (LL i=;i<=n;i++) {
if (xx[i]==i) continue;
if (xx[xx[i]]==i&&xx[i]>i) yy[i]=(yy[xx[i]]>yy[i])?yy[xx[i]]:yy[i],yy[xx[i]]=-1ll;
}
for (LL i=;i<=n;i++) if (yy[i]!=-) connect(i,xx[i],yy[i]),connect(xx[i],i,yy[i]);
for (LL i=;i<=n;i++) if (!low[i]) solve(i);
//for (LL i=1;i<=n;i++) printf(" %d %d %d\n",i,low[i],dfn[i]);
printf("%lld\n",ans);
return ;
}