P4381 [IOI2008]Island

P4381 [IOI2008]Island

题意：

给你一棵基环树森林，求出基环树的直径之和.

题解：

对于基环树,我们将环看作根,那么直径有两种情况::

1.不经过环,也就是环上某个点的子树内部,对于这种情况,直接在子树内部处理直径,更新答案即可;

2.经过环,答案就是i的子树内长度+j的子树内长度+i和j之间的距离，我们预处理出环上每个点到其子树上的最长距离,在预处理一个环上前缀和,ans=max{sondis[i]+sondis[j]+sumcircle[i]-sumcircle[j]},更新答案即可.
sondis[i]记录环上的第i个点到其子树的最远距离;
sumcircle[]记录环上距离前缀和;
sumcircle[i]-sumcircle[j]即为i和j的距离

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e6+3;
int to[N<<1],nex[N<<1],head[N],w[N<<1],tt;
int c[N];//记录当前节点属于第几棵基环树;
int dg[N];//记录度数;
int q[N<<1];//数组模拟队列;
ll d[N];//d[i]记录第i棵树上的直径;
ll f[N];//f[i]记录从i点向儿子方向上所可以走的最长距离;
ll sumcircle[N<<1];//环上距离前缀和;
ll sondis[N<<1];//sondis[i]记录环上的第i个点到其子树的最远距离;
int cnt,n;
bool vis[N];//标记当前基环树是否已解决过;
inline void add(int x,int y,int W){
    to[++tt]=y,w[tt]=W,nex[tt]=head[x],head[x]=tt;
    return ;
}
inline void bfs(int p,int t){
    int l=0,r=1;
    q[1]=p,c[p]=t;//广搜预处理每一个点所属基环树的编号;
    while(l<r){
        ++l;
        int x=q[l];
        for(int i=head[x],v;i;i=nex[i]){
            v=to[i];
            if(!c[v]){
                q[++r]=v;
                c[v]=t;
            }
        }
    }
    return ;
}
inline void top_sort(){//拓扑排序求不经过环的直径,从叶子节点向根(环)遍历;
    int l=0,r=0;
    for(int i=1;i<=n;++i)if(dg[i]==1)q[++r]=i;//将所有度数为1的点先加入队列中(即叶子结点);
    while(l<r){
        ++l;
        int x=q[l];
        for(int i=head[x],v;i;i=nex[i]){
            v=to[i];
            if(dg[v]>1){//此时v在以环为根的树上是其实是x的父亲;
                d[c[x]]=max(d[c[x]],f[x]+f[v]+w[i]);//更新当前基环树上的答案;
                f[v]=max(f[v],f[x]+w[i]);//更新父节点可以到达的最远节点;
                if(--dg[v]==1)q[++r]=v;//若当前度数现在变为1,入队;
            }
        }
    }
    return ;
}
inline void work(int t,int x){
    int tot=0,l,r,v=x,u,i;//在拓扑排序后已经将非环上的边遍历完了,环上的边和点均还未遍历,且度数为2,将x看做环上的起点,v看做终点;
    do{
        dg[v]=1;
        sondis[++tot]=f[v];//将当前点度数记为1,防止反向遍历,同时记录第tot号环上节点到子树上的最短距离;
        for(i=head[v];i;i=nex[i]){
            u=to[i];
            if(dg[u]>1){//环上的点度数均大于1,所以度数大于1的点即是环上的点;
                v=u;//更新终点;
                sumcircle[tot+1]=sumcircle[tot]+w[i];//处理环上距离前缀和;
                break;//保证向一边枚举,所以找到一个点就break;
            }
        }
    }while(i);
    if(tot==2){//特殊处理二元环;
        int len=0;
        for(i=head[v];i;i=nex[i]){
            u=to[i];
            if(u==x){
                len=max(len,w[i]);//找出两个点之间较大的边; 
            }
        }
        d[t]=max(d[t],(ll)len+f[x]+f[v]);//更新答案;
        return ;
    }
    for(int i=head[v],u;i;i=nex[i]){
        u=to[i];
        if(u==x){
            sumcircle[tot+1]=sumcircle[tot]+w[i];//将起点和终点的距离处理出来;
            break;
        }
    }
    for(i=1;i<tot;i++)//断环为链,再复制一遍数组;
    {
        sondis[tot+i]=sondis[i];
        sumcircle[tot+i]=sumcircle[tot+1]+sumcircle[i];
    }
    q[1]=1;
    l=r=1;
    for(int i=2;i<tot<<1;++i){
        while(l<=r&&i-q[l]>=tot)++l;//将超出环长度的部分弹出;
        d[t]=max(d[t],sondis[q[l]]+sondis[i]+sumcircle[i]-sumcircle[q[l]]);
        while(l<=r&&sondis[q[r]]+sumcircle[i]-sumcircle[q[r]]<=sondis[i])--r;//将队尾答案不够优秀的部分弹出;
        q[++r]=i;//入队;
    }
    return ;
}
int main(){

    cin>>n;
    int x,W;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&W);
        add(x,i,W);
        add(i,x,W);
        ++dg[x];
        ++dg[i];
    }
    for(int i=1;i<=n;++i)if(!c[i])bfs(i,++cnt);//预处理;
    top_sort();//拓扑排序求直径;
    ll ans=0;
    for(int i=1;i<=n;++i)
        if(dg[i]>1&&!vis[c[i]]){//如果当前基环树未被处理,并且当前点是环上点,就处理;
            vis[c[i]]=true;
            work(c[i],i);
            ans+=d[c[i]];//累加答案;
        }
    cout<<ans<<'\n';
    return 0;
}