dfs找环 dfs1求直径 应该都没错

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,dfn[N],stamp,f[N],d1[N],d2[N],ring[N],sum[N];
map<int,map<int,int>>mp;
vector<int>vec;
struct graph{
    int v,w,id;
};
vector<graph>g[N];
void dfs(int u,int last){
    dfn[u]=++stamp;
    for(auto [v,w,id]:g[u]){
        if(id!=last){
            if(dfn[v]){
                if(dfn[v]>dfn[u]){
                    vec.push_back(v),ring[v]=1;
                    while(v!=u){
                        v=f[v],vec.push_back(v),ring[v]=1;
                    }
                }
            }
            else{
                f[v]=u,dfs(v,id);
            }
        }
    }
}
void dfs1(int u,int last){
    for(auto [v,w,id]:g[u]){
        if(id!=last&&!ring[v]){
            dfs1(v,id);
            if(d1[v]+w>=d1[u]){
                d2[u]=d1[u],d1[u]=d1[v]+w;
            }
            else if(d1[v]+w>=d2[u]){
                d2[u]=d1[v]+w;
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int u=1,v,w;u<=n;u++){
        cin>>v>>w,g[u].push_back({v,w,u}),g[v].push_back({u,w,u}),mp[u][v]=w;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            int num=0;
            vec.clear(),dfs(i,0),reverse(vec.begin(),vec.end());
            for(int i:vec){
                dfs1(i,0),num=max(num,d1[i]+d2[i]);
            }
            int len=vec.size();
            for(int i=0;i<len;i++){
                vec.push_back(vec[i]);
            }
            for(int i=1;i<vec.size();i++){
                sum[i]=sum[i-1]+mp[vec[i-1]][vec[i]];
            }
            for(int i=0;i<len;i++){
                for(int j=i+1;j<len;j++){
                    num=max(num,d1[vec[i]]+d1[vec[j]]+max(sum[j]-sum[i],sum[i+len]-sum[j]));
                }
            }
            ans+=num;
        }
    }
    cout<<ans;
}