修掉了过环的直径bug的新代码（还是不行）：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn =1e6+10;
int n;
struct edge{
int to,val;
};
vector <edge> a[maxn];
int sta[maxn],stais[maxn],cnt=0,vis[maxn];//DFS1中所需的
bool ring[maxn],root[maxn];//环和子树根
int in1[maxn],in2[maxn];
int dep[maxn],dt[maxn];//子树深度（从下往上） 和经过当前点子树直径
int dmax[maxn];//子树最大直径
long long ans=0; //总答案
void build (int from,int to,int val)
{
edge x;
x.to=to; x.val=val;
a[from].push_back(x);
return ;
}
void dfs1 (int u,int fa)
{
// cout<<u<<' ';
vis[u]=1,sta[++cnt]=u;
stais[u]=1;
for (int i=0;i<a[u].size();i++)
{
int v=a[u][i].to;
if (v==fa) continue;
if (!vis[v]) dfs1 (v,u);
else if (stais[v])
{
for (int i=cnt;i>=1;i--)
{
ring[sta[i]]=1;
if (sta[i]==v) break;
}
}
}
stais[u]=0;
cnt-=1;
}
void dfs2 (int u,int fa)
{
if (a[u].size()==1) {
if (ring[a[u][0].to]){
dmax[a[u][0].to]=dep[a[u][0].to]=a[u][0].val;
}
return ;
}
int dn=0;//子树深度当前最深的点的编号
for (int i=0;i<a[u].size();i++)
{
int v=a[u][i].to;
if (v==fa||ring[v]) continue;
dfs2 (v,u);
if (dt[u]<dep[v]+a[u][i].val+dt[u]) dt[u]=dep[v]+a[u][i].val+dt[u];
if (dep[v]+a[u][i].val>dep[u])
{
dep[u]=dep[v]+a[u][i].val;
dn=i;
}
if (dmax[v]>dmax[u]) dmax[u]=dmax[v];
if (dt[v]>dmax[u]) dmax[u]=dt[v];
}
if (dmax[u]>dmax[u]) dmax[u]=dmax[u];
if (dt[u]>dmax[u]) dmax[u]=dt[u];
return ;
}
int mtdt=0,max1=0,max2=0;
int has[maxn];
void dfs (int u,int fa,int deep)
{
vis[u]=has[u]=1;
mtdt=max(mtdt,dmax[u]);
if ((dep[u]+deep>max1)&&(dep[u]-deep>max2)) {
if (dep[u]+deep-max1>dep[u]-deep-max2){
max1=dep[u]+deep;
}
else{
max2=dep[u]-deep;
}
}
else
{
if (dep[u]+deep>max1) max1=dep[u]+deep;
if (dep[u]-deep>max2) max2=dep[u]-deep;
}
//cout<<u<<"! "<<dep[u]<<" "<<deep<<" "<<max1<<" "<<max2<<endl;
for (int i=0;i<a[u].size();i++)
{
int v=a[u][i].to;
if (!ring[v]||vis[v]) continue;
dfs(v,u,deep+a[u][i].val);
}
return ;
}
void clearv (){
for (int i=0;i<=n+1;i++) vis[i]=0;
}
int main ()
{
// freopen ("all.in","r",stdin);
scanf ("%d",&n);
for (int i=1;i<=n;i++)
{
int x,y;
scanf ("%d%d",&x,&y);
in1[i]=x,in2[i]=y;
if (in1[i]<i&&in1[x]==i)//处理二元环
{
ans+=max(y,in2[x]);
continue;
}
build (i,x,y);
build (x,i,y);
}
for (int i=1;i<=n;i++)
{
if (vis[i]==0) dfs1 (i,0);
}
//cout<<endl; for (int i=1;i<=n;i++) cout<<ring[i]<<" ";
for (int u=1;u<=n;u++)
{
if (ring[u])
{
for (int i=0;i<a[u].size();i++)
{
int v=a[u][i].to;
if (ring[v]==0) //标记子树根节点
{
root[u]=1;
//break;
}
}
}
}
for (int t=1;t<=n;t++)
{
if (root[t]) dfs2(t,0);
}
//for (int i=1;i<=n;i++) cout<<dep[i]<<" "<<dmax[i]<<endl;
for (int t=1;t<=n;t++)
{
if (ring[t]&&!has[t])
{
int u=t;
int t1=0,t2=0;
for (int i=0;i<a[u].size();i++) {
if (ring[a[u][i].to])
{
if (t1==0) t1=a[u][i].to;
else{
t2=a[u][i].to;
break;
}
}
}
clearv();
mtdt=0,max1=max2=0;
dfs (u,t1,0);
int c=max(mtdt,max1+max2);
clearv();
mtdt=0,max1=max2=0;
dfs (u,t2,0);
c=max(c,max1+max2);
ans+=c;
}
}
cout<<ans;
return 0;
}
```
by phelixzhen @ 2023-04-22 21:12:33