• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

CF835F Roads in the Kingdom

admin

11月 28, 2021

Description

给定一棵基环树,现在可以删去环上的一条边,最小化删变后树的直径。求直径大小。

Solution

把环上的边删完后,就得到一个森林。删去环上的边对森林里树的直径是无影响的,这是直径的第一种情况。

第二种情况就是两段非环路径加上一段环上路径,记 (c_i) 表示 (i) 到子树内的最长链,最大直径就可以表示为 (c_i+c_j+dis_{i,j})。删去一条环上的边,断成链。假设删的是 ([i-1,i]) 这条边,记 (s_i) 表示边权的前缀和 ((a_0=a_m)),有三种情况 ((u<v))

  1. (u,vin[1,i-1]),就用 (c_v+c_u+s_v-s_u) 更新答案,只需要维护 (c_u-s_u) 的前缀最大,然后再对 (v) 做前缀。
  2. (u,vin[i,m]),和 1 类似,答案一样,维护 (c_v+s_v) 后缀最大,再对 (u) 做后缀。
  3. (uin[i,m],vin[1,i-1]) ,答案是 (s_u+c_u+c_v+s_m-s_v),分别维护前缀后缀最大。
#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;

typedef long long ll;

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
    return flag? x:-x; 
}

const int N=2e5+7;

map<int,int> mp[N];

struct E{
    int next,to,dis;
}e[N<<1];

int head[N],cnt=0,fa[N];

inline void add(int id,int to,int d){
    e[++cnt]=(E){head[id],to,d};
    head[id]=cnt;
}

bool ins[N],imp[N];
int sta[N],top=0,a[N],m=0;

void dfs(int u){
    static bool tag=0;
    sta[++top]=u;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa[u]) continue;
        if(ins[v]){
            tag=1; int y;
            do{
                imp[y=sta[top--]]=1;
                a[++m]=y;
            }while(y!=v);
            return ;
        }
        ins[u]=1,fa[v]=u,dfs(v),ins[u]=0;
        if(tag) return ;
    }
    top--;
}

int rt;
ll c[N],mx=0;
ll dfs1(int u,ll ret,int fa){
    if(ret>mx) mx=ret,rt=u;
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=fa&&!imp[e[i].to]) dfs1(e[i].to,e[i].dis+ret,u);
}

ll G,F[2][N],s[N],H[2][N];

int main(){
    freopen("roads.in","r",stdin);
    freopen("roads.out","w",stdout);
    int n=read();
    for(int i=1;i<=n;i++){
        int u=read(),v=read(),d=read();
        mp[u][v]=mp[v][u]=d;
        add(u,v,d),add(v,u,d);
    }
    dfs(1); ll ans=1ll<<60,ans1=0;
    for(int i=1;i<=n;i++) fa[i]=0; a[0]=a[m];
    for(int i=1;i<=m;i++){
        imp[a[i]]=0;
         mx=rt=0,dfs1(a[i],0,0),c[i]=mx;
        mx=0,dfs1(rt,0,0),ans1=max(ans1,mx);
        s[i]=s[i-1]+mp[a[i-1]][a[i]];
        imp[a[i]]=1;
    }    
    G=F[0][0]=F[1][0]=-(1ll<<60);
    for(int i=1;i<=m;i++){
        F[0][i]=max(F[0][i-1],G+s[i]+c[i]);
        F[1][i]=max(F[1][i-1],s[i]+c[i]);
        G=max(G,c[i]-s[i]);
    }
    G=H[0][m+1]=H[1][m+1]=-(1ll<<60);
    for(int i=m;i;i--){
        H[0][i]=max(H[0][i+1],G-s[i]+c[i]);
        H[1][i]=max(H[1][i+1],c[i]-s[i]+s[m]);
        G=max(G,c[i]+s[i]);
    }
    for(int i=1;i<=m;i++)
        ans=min(ans,max(max(F[0][i-1],H[0][i]),F[1][i-1]+H[1][i]));
    printf("%lld",max(ans,ans1));
}

发表回复

您的电子邮箱地址不会被公开。