题目大意

求各个基环树的直径和

先用dfs或拓扑排序找到基环树的环，把环上的点标记，再对每个点进行dfs，就可以访问以该点为根的子树。
在每棵子树中求出直径。设$f[x]$表示以$x$为根的子树的直径。设$i,j$为环上两点,$d[i]$表示环上边权的前缀和。
那么基环树的直径就是$f[i]+f[j]+d[j]-d[i]$,其中$d[j]-d[i]$是$i,j$两点的在环上的距离。对于d数组，可以把环断开复制一遍，枚举j,用单调队列维护$f[i]-d[i]$的最大值.
时间复杂度：$O(n)$

#include <iostream> 
#include <queue>
using namespace std;
int n;
int nx[2000006],he[1000006],vr[2000006],eg[2000006],tot;
inline void add(int x,int y,int z){
    vr[++tot]=y;
    eg[tot]=z;
    nx[tot]=he[x];
    he[x]=tot;
}
int in[1000006],ku[1000006],v[1000006],t,q[2000006];
long long ans,d[1000006],f[1000006],a[1000006],b[1000006];
// 一定要开long long !!!
void topsort(){
    queue<int> q;
    for(int i=1;i<=n;++i) if(in[i]==1) q.push(i);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=he[x];i;i=nx[i]){
            if(in[vr[i]]>1){
                d[ku[x]]=max(d[ku[x]],f[x]+f[vr[i]]+eg[i]);
                f[vr[i]]=max(f[vr[i]],f[x]+eg[i]);// 树的直径
                if(--in[vr[i]]==1) {
                    q.push(vr[i]);
                }
            }
        }
    }
}
void dp(int k,int x){
    int m=0;// 环上点的数量
    int y=x,z=0,len=0;
    do{
        a[++m]=f[y];// 记录以环上各点为根的子树的直径
        in[y]=1;
        for(z=he[y];z;z=nx[z]){
            if(in[vr[z]]>1){
                y=vr[z];
                b[m+1]=b[m]+eg[z];// 标记环上的点
                break;
            }
        }
    }while(z);
    if(m==2){
        for(int i=he[y];i;i=nx[i]){
            if(vr[i]==x){
                len=max(len,eg[i]);
            }
        }
        d[k]=max(d[k],f[x]+f[y]+len);
        return;
    }
    for(int i=he[y];i;i=nx[i]){
        if(vr[i]==x){
            b[m+1]=b[m]+eg[i];
            break;
        }
    }
    for(int i=1;i<m;++i){
        a[i+m]=a[i];b[i+m]=b[m+1]+b[i]; // 复制
    }
    int l,r;
    q[l=r=1]=1;// 单调队列
    for(int i=2;i<(m<<1);++i){
        while(l<=r && i-q[l]>=m) ++l;
        d[k]=max(d[k],a[q[l]]+a[i]+b[i]-b[q[l]]);
        while(l<=r && a[q[r]]-b[q[r]]<=a[i]-b[i]) --r;
        q[++r]=i;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int x,z;
    for(int i=1;i<=n;++i){
        cin>>x>>z;
        add(x,i,z);
        add(i,x,z);
        ++in[x];++in[i];
    }
    queue<int> q;
    for(int i=1;i<=n;++i){ // 遍历每个连通块
        if(ku[i]) continue;
        while(q.size()) q.pop();
        q.push(i);
        ku[i]=++t;
        while(q.size()){
            x=q.front();
            q.pop();
            for(int i=he[x];i;i=nx[i]){
                if(ku[vr[i]]) continue;
                q.push(vr[i]);
                ku[vr[i]]=t;
            }
        }
    }
    topsort();// 拓扑排序
    for(int i=1;i<=n;++i){
        if(in[i]>1 && !v[ku[i]]) { // 如果该点入度大于1，那么就是环上的点
            v[ku[i]]=1;// 标记
            dp(ku[i],i);
            ans+=d[ku[i]];// 统计每个基环树最长简单路径
        }
    }
    cout<<ans;
    return 0;
}