只看了题解的大致思路，然后自己就开始乱搞了，救命 3个A 3个W 1个T 13个RE （0.0）

其中，edge、head 都懂吧

vis 是用于dfs判断是否找到环，pre 记录了递归方向，$ring_i$ 表示环上第 i 个节点，$exist_i=1$ 表明节点 i 在环上，q 是单调队列

d 为求树的直径的 DP 数组， $D_i$ 是环上第 i 个节点子树内直径，S 记录环之间路径前缀和

救命，可能码风会有点毒瘤。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6+6;

struct Edge{
    int nex,to;
    ll dis;
}edge[N<<1];
int head[N],vis[N],pre[N];
int ring[N],exist[N],q[N];
int n,elen=1,cnt,fg,l,r;
ll d[N],D[N],S[N],tmp[N],sum,ans;

void add(int from,int to,ll dis){
    edge[++elen]={head[from],to,dis};
    head[from]=elen;
}
void dfs(int u,int in_edge){
    if(vis[u]){
        int now=pre[ring[++cnt]=u];exist[u]=1;
        while(now!=u)exist[ring[++cnt]=now]=1,now=pre[now];
        return fg=1,void();
    }
    vis[u]=1;
    for(int e=head[u];e;e=edge[e].nex){
        if(e==(in_edge^1))continue;
        int v=edge[e].to;
        pre[v]=u,tmp[v]=edge[e].dis;
		dfs(v,e);
        if(fg)return;
    }
}
void dp(int u,int fath){
    for(int e=head[u];e;e=edge[e].nex){
        int v=edge[e].to;
        if(v==fath||exist[v])continue;
        dp(v,u);
        sum=max(sum,d[u]+d[v]+edge[e].dis);
        d[u]=max(d[u],d[v]+edge[e].dis);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int v;ll w;
        scanf("%d%lld",&v,&w);
        add(i,v,w);add(v,i,w);
    }
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        memset(d,0,sizeof(d));
        memset(ring,0,sizeof(ring));
        memset(exist,0,sizeof(exist));
        l=1;pre[i]=fg=r=cnt=0;dfs(i,0);
        //puts("");
        for(int j=1;j<=cnt;j++){
            //printf("%d %lld\n",ring[j],tmp[ring[j]]);
            S[j]=S[j-1]+tmp[ring[j]];
            dp(ring[j],sum=0);
            D[j]=D[j+cnt]=sum;
            //printf("%lld %lld\n",S[j],D[j]);
        }//puts("");
        for(int j=cnt+1;j<=cnt<<1;j++)
        	S[j]=S[j-1]+tmp[ring[j-cnt]];
        sum=0;
        for(int j=1;j<=cnt<<1;j++){
            while(l<=r&&j-q[l]>=cnt)l++;
            sum=max(sum,D[j]+S[j-1]+D[q[l]]-S[q[l]-1]);
            while(l<=r&&D[j]-S[j-1]>=D[q[r]]-S[q[r]-1])r--;
            q[++r]=j;
            //for(int k=l;k<=r;k++)cout<<q[k]<<" ";
            //puts("");printf("%d\n",sum);
        }
        ans+=sum;
    }
    printf("%lld",ans);
    return 0;
}