#include<iostream>
#include<cstdio>
#define M 1000009
using namespace std;
int q[*M],cnt,n,head[M],next[*M],u[*M],l[*M],du[M],c[M],t,v[M];
long long f[M],d[M],d1[*M],a[*M],ans;
void jia(int a1,int a2,int a3)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
l[cnt]=a3;
du[a1]++;
return;
}
void dfs(int k,int x)
{
c[x]=k;
for(int i=head[x];i;i=next[i])
if(!c[u[i]])
dfs(k,u[i]);
return;
}
void tuopu()
{
int h=,t=;
for(int i=;i<=n;i++)
if(du[i]==)
{
t++;
q[t]=i;
}
for(;h<t;)
{
h++;
int p=q[h];
for(int i=head[p];i;i=next[i])
if(du[u[i]]!=)
{
du[u[i]]--;
d[c[p]]=max(d[c[p]],f[p]+f[u[i]]+l[i]);
f[u[i]]=max(f[u[i]],f[p]+l[i]);
if(du[u[i]]==)
{
t++;
q[t]=u[i];
}
}
}
}
void dp(int t1,int x)
{
int m=,y=x,i;
do
{
a[++m]=f[y];
du[y]=;
for(i=head[y];i;i=next[i])
if(du[u[i]]>)
{
d1[m+]=d1[m]+l[i];
y=u[i];
break;
}
}while(i);
if(m==)
{
int qq=;
for(int i=head[y];i;i=next[i])
if(u[i]==x)
qq=max(qq,l[i]);
d[c[x]]=max(d[c[x]],a[]+a[]+qq);
return;
}
for(int i=head[y];i;i=next[i])
if(u[i]==x)
{
d1[m+]=d1[m]+l[i];
break;
}
for(int i=;i<=m;i++)
{
a[m+i]=a[i];
d1[m+i]=d1[m+]+d1[i];
}
int h=t=;
q[]=;
for(int i=;i<=*m;i++)
{
for(;h<=t&&i-q[h]>=m;h++);
d[t1]=max(d[t1],a[q[h]]+a[i]+d1[i]-d1[q[h]]);
for(;h<=t&&a[q[t]]-d1[q[t]]<=a[i]-d1[i];t--);
t++;
q[t]=i;
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int a1,a2;
scanf("%d%d",&a1,&a2);
jia(i,a1,a2);
jia(a1,i,a2);
}
for(int i=;i<=n;i++)
if(!c[i])
{
t++;
dfs(t,i);
}
tuopu();
for(int i=;i<=n;i++)
if(du[i]>&&!v[c[i]])
{
v[c[i]]=;
dp(c[i],i);
ans+=d[c[i]];
}
printf("%lld\n",ans);
return ;
}
这个题建出图来之后，是一个基环树森林，先把非环部分的最长链用DP求出来，在把环拆开，变为两倍，找环上两点之间的距离加上在这两个点的子树中，以这两个点为端点的最长链的
长度，注意如果是两个点的环，需要特判，因为不一定能找到那条最长的边。