1 #include
     
        2 #include
      
         3 #define M 1000009  4 using namespace std;  5 int q[2*M],cnt,n,head[M],next[2*M],u[2*M],l[2*M],du[M],c[M],t,v[M];  6 long long f[M],d[M],d1[2*M],a[2*M],ans;  7 void jia(int a1,int a2,int a3)  8 {  9     cnt++; 10     next[cnt]=head[a1]; 11     head[a1]=cnt; 12     u[cnt]=a2; 13     l[cnt]=a3; 14     du[a1]++; 15     return; 16 } 17 void dfs(int k,int x) 18 { 19     c[x]=k; 20     for(int i=head[x];i;i=next[i]) 21       if(!c[u[i]]) 22         dfs(k,u[i]); 23     return; 24 } 25 void tuopu() 26 { 27     int h=0,t=0; 28     for(int i=1;i<=n;i++) 29       if(du[i]==1) 30         { 31             t++; 32             q[t]=i; 33         } 34     for(;h
       
        1) 61             { 62                 d1[m+1]=d1[m]+l[i]; 63                 y=u[i]; 64                 break; 65             } 66       }while(i); 67     if(m==2) 68       { 69         int qq=0; 70         for(int i=head[y];i;i=next[i]) 71           if(u[i]==x) 72             qq=max(qq,l[i]); 73         d[c[x]]=max(d[c[x]],a[1]+a[2]+qq); 74         return; 75       } 76     for(int i=head[y];i;i=next[i]) 77       if(u[i]==x) 78         { 79             d1[m+1]=d1[m]+l[i]; 80             break; 81         } 82     for(int i=1;i<=m;i++) 83       { 84         a[m+i]=a[i]; 85         d1[m+i]=d1[m+1]+d1[i]; 86       } 87     int h=t=1; 88     q[1]=1; 89     for(int i=2;i<=2*m;i++) 90       { 91         for(;h<=t&&i-q[h]>=m;h++); 92         d[t1]=max(d[t1],a[q[h]]+a[i]+d1[i]-d1[q[h]]); 93         for(;h<=t&&a[q[t]]-d1[q[t]]<=a[i]-d1[i];t--); 94         t++; 95         q[t]=i; 96       } 97 } 98 int main() 99 {100     scanf("%d",&n);101     for(int i=1;i<=n;i++)102       {103         int a1,a2;104         scanf("%d%d",&a1,&a2);105         jia(i,a1,a2);106         jia(a1,i,a2);107       }108     for(int i=1;i<=n;i++)109       if(!c[i])110         {111           t++;112           dfs(t,i);113         }114     tuopu();115     for(int i=1;i<=n;i++)116       if(du[i]>1&&!v[c[i]])117         {118             v[c[i]]=1;119             dp(c[i],i);120             ans+=d[c[i]];121         }122     printf("%lld\n",ans);123     return 0;124 }
       
      
     

这个题建出图来之后，是一个基环树森林，先把非环部分的最长链用DP求出来，在把环拆开，变为两倍，找环上两点之间的距离加上在这两个点的子树中，以这两个点为端点的最长链的

长度，注意如果是两个点的环，需要特判，因为不一定能找到那条最长的边。