CF835F Roads in the Kingdom解题报告

解题报告

题意

• 给定一个$n$个点的基环树，割断其中一条边使得剩下的树直径最小，并且图要仍然联通。
• 数据范围：$3\leqslant n\leqslant 2\times 10^5$。

分析

首先，为了使图仍然联通，我们只能隔环上的边。

代码

#include<stdio.h>
#define inf 10000000000000000
#define int long long
const int maxn=200005,maxm=400005;
int n,e,cnt,ans1,ans2,tot;
int start[maxn],to[maxm],then[maxm],worth[maxm],vis[maxn],sum[maxn],c[maxn],w[maxn],f[maxn],pre1[maxn],pre2[maxn],pre3[maxn],suf1[maxn],suf2[maxn],suf3[maxn];
inline int max(int a,int b){
    return a>b? a:b;
}
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y,int z){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z;
}
int find(int x,int last){
    if(vis[x])
        return x;
    vis[x]=-1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i],tmp;
        if(y==last)
            continue;
        tmp=find(y,x);
        if(tmp){
            c[++cnt]=x,w[cnt]=worth[i],sum[cnt]=sum[cnt-1]+w[cnt],vis[x]=1;
            return x==tmp? 0:tmp;
        }
    }
    return 0;
}
void dfs(int x,int last){
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(vis[y]==1||y==last)
            continue;
        dfs(y,x);
        ans1=max(ans1,f[x]+f[y]+worth[i]);
        f[x]=max(f[x],f[y]+worth[i]);
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    find(1,0);
    for(int i=1;i<=cnt;i++)
        dfs(c[i],0);
    tot=sum[cnt];
    pre1[0]=pre2[0]=pre3[0]=-inf;
    for(int i=1;i<=cnt;i++){
        pre1[i]=max(pre1[i-1],f[c[i]]+sum[i]);
        pre2[i]=max(pre2[i-1],f[c[i]]-sum[i]);
        pre3[i]=max(pre3[i-1],f[c[i]]+sum[i]+pre2[i-1]);
    }
    suf1[cnt+1]=suf2[cnt+1]=suf3[cnt+1]=-inf;
    for(int i=cnt;i>=1;i--){
        suf1[i]=max(suf1[i+1],f[c[i]]+sum[i]);
        suf2[i]=max(suf2[i+1],f[c[i]]-sum[i]);
        suf3[i]=max(suf3[i+1],f[c[i]]-sum[i]+suf1[i+1]);
    }
    ans2=inf;
    for(int i=1;i<=cnt;i++)
        ans2=min(ans2,max(max(pre3[i-1],suf3[i]),tot+pre1[i-1]+suf2[i]));
    printf("%lld\n",max(ans1,ans2));
    return 0;
}