首先对于一棵树我们可以tree_dp来解决这个问题，那么对于环上每个点为根的树我们可以求出这个树的一端为根的最长链，并且在tree_dp的过程中更新答案。那么我们对于环，从某个点断开，破环为链，然后再用DP来解决这个问题。

　　备注：很久之前的一道题，刚转的c++，然后T了，也懒得改了。

/**************************************************************    Problem: 1791    User: BLADEVIL    Language: C++    Result: Time_Limit_Exceed****************************************************************/ //By BLADEVIL #include 
     
       #include 
      
        #define maxn 1000010 #define LL long long    using namespace std;    LL n,time,l; LL other[maxn<<1],last[maxn],pre[maxn<<1],dfn[maxn],low[maxn],vis[maxn],que[maxn],a[maxn],xx[maxn]; LL ans; LL len[maxn<<1],max1[maxn],max2[maxn],sum[maxn],w[maxn],yy[maxn],maxlen[maxn]; LL save;    void getmin(LL &x,LL y) {
    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,0,sizeof que);     LL h=0,t=1ll;     que[1]=x; vis[x]=1ll;     while (h
        
         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]]
         
          yy[xx[x]])?yy[x]:yy[xx[x]];           return;     }*/    LL cur;     for (LL i=1;i<=n;i++) if (low[i]==low[x]) dp(i),cur=i;     //printf(" %lld\n",max1[x]);     LL t=1; a[t]=cur;     while (1) {         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-1]) 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=2;i<=t;i++) a[i+t]=a[i],sum[i+t]=sum[i];      t*=2;     //for (LL i=1;i<=t;i++) printf(" %lld %d %d\n",max1[a[i]],a[i],sum[i]);     for (LL i=1;i<=t;i++) sum[i]+=sum[i-1];     LL len=t>>1ll;     memset(que,0,sizeof que);     LL l=1,r=1; que[1]=1;     for (LL i=2;i<=t;i++) {         if (i-que[l]+1>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=1;i<=t;i++) now=(w[i]>now)?w[i]:now;     //printf(" %lld ",ans);     ans+=now;  }    int main() {     scanf("%d",&n);     for (LL i=1;i<=n;i++) scanf("%d%lld",&xx[i],&yy[i]);     for (LL i=1;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=1;i<=n;i++) if (yy[i]!=-1) connect(i,xx[i],yy[i]),connect(xx[i],i,yy[i]);     for (LL i=1;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 0;}