先找出基环。

然后枚举删环上的每条边，那么剩下的就是一棵树。接下来要做的就是求这颗树的最长链。

这样显然是n^2的。所以可以考虑用线段树降到nlogn

对于环上的每个点i的子树，以i为起点的最长链长度为dis[i]。

环上的边权用前缀和sum[]存。

这样最长链就是max{sum[j]-sum[i]+dis[i]+dis[j]}。

于是用两颗线段树分别维护max{sum[j]+dis[j]}和max{dis[i]-sum[i]}。然后更新答案。注意细节i≠j。

还有就是要用每颗子树的最长链更新答案。

还有就是代码超长肿么办=。=

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500100,maxm=500100;
int p[maxm],n1[maxm],h[maxn],iscir[maxn],q[maxn],fa[maxn],cir[maxn],vis[maxn],cc,flag,ee,n;
long long w[maxm],lt[maxn],rt[maxn],sum[maxn],d[maxn],dt[maxn],cirsum=0LL,ans=0LL,Ans=10000000000000000LL;
struct SegmentTree{
    #define ls (x<<1)
    #define rs (x<<1|1)
    #define maxt 500400
    long long seg[maxt],seg2[maxt];
    int mx1[maxt],mx2[maxt];
    void update(int x){
        if(seg[ls]>seg[rs]){
            seg[x]=seg[ls];
            mx1[x]=mx1[ls];
            seg2[x]=seg[rs];
            mx2[x]=mx1[rs];
        }else{
            seg[x]=seg[rs];
            mx1[x]=mx1[rs];
            seg2[x]=seg[ls];
            mx2[x]=mx1[ls];
        }if(seg2[ls]>seg2[x]){
            seg2[x]=seg2[ls];
            mx2[x]=mx2[ls];
        }if(seg2[rs]>seg2[x]){
            seg2[x]=seg2[rs];
            mx2[x]=mx2[rs];
        }
    }void build(int l,int r,int x){
        if(l==r){
            seg[x]=sum[l]+dt[l];
            seg2[x]=0LL;
            mx1[x]=l;
            mx2[x]=0;
            return;
        }int mid=(l+r)>>1;
        build(l,mid,ls);
        build(mid+1,r,rs);
        update(x);
    }void modify(int p,long long v,int l,int r,int x){
        if(l==r && p==l){
            seg[x]=v;
            return;
        }int mid=(l+r)>>1;
        if(p<=mid)  modify(p,v,l,mid,ls);
        else        modify(p,v,mid+1,r,rs);
        update(x);
    }void init(){
        memset(seg,0,sizeof(seg));
        memset(seg2,0,sizeof(seg2));
        memset(mx1,0,sizeof(mx1));
        memset(mx2,0,sizeof(mx2));
    } 
}T;
struct SegmentTree2{
    #define ls (x<<1)
    #define rs (x<<1|1)
    #define maxt 500400
    long long seg[maxt],seg2[maxt];
    int mx1[maxt],mx2[maxt];
    void update(int x){
        if(seg[ls]>seg[rs]){
            seg[x]=seg[ls];
            mx1[x]=mx1[ls];
            seg2[x]=seg[rs];
            mx2[x]=mx1[rs];
        }else{
            seg[x]=seg[rs];
            mx1[x]=mx1[rs];
            seg2[x]=seg[ls];
            mx2[x]=mx1[ls];
        }if(seg2[ls]>seg2[x]){
            seg2[x]=seg2[ls];
            mx2[x]=mx2[ls];
        }if(seg2[rs]>seg2[x]){
            seg2[x]=seg2[rs];
            mx2[x]=mx2[rs];
        }
    }void build(int l,int r,int x){
        if(l==r){
            seg[x]=dt[l]-sum[l];
            mx1[x]=l;
            mx2[x]=0;
            return;
        }int mid=(l+r)>>1;
        build(l,mid,ls);
        build(mid+1,r,rs);
        update(x);
    }void modify(int p,long long v,int l,int r,int x){
        if(l==r && p==l){
            seg[x]=v;
            return;
        }int mid=(l+r)>>1;
        if(p<=mid)  modify(p,v,l,mid,ls);
        else        modify(p,v,mid+1,r,rs);
        update(x);
    }void init(){
        for(int i=0;i<=500000;i++)  seg[i]=seg2[i]=-1000000000000000LL;
        memset(mx1,0,sizeof(mx1));
        memset(mx2,0,sizeof(mx2));
    } 
}Q;
void ae(int x,int y,long long z){
    p[ee]=y;    w[ee]=z;    n1[ee]=h[x];    h[x]=ee++;
    p[ee]=x;    w[ee]=z;    n1[ee]=h[y];    h[y]=ee++;
}void dfs(int u,int f){
    if(flag)    return;
    fa[u]=f;
    vis[u]=1;
    for(int i=h[u];~i;i=n1[i]){
        if(p[i]==f) continue;
        if(vis[p[i]]){
            if(!cir[1]){
                fa[p[i]]=u;
                cir[1]=p[i];
                flag=1;
            }return;
        }else   dfs(p[i],u);
    }
}void findcircle(){
    flag=cir[cc=1]=0;
    dfs(1,0);
    int k=cir[1];
    while(fa[k]!=cir[1]){
        cir[++cc]=fa[k];
        k=fa[k];
    }memset(iscir,0,sizeof(iscir));
    for(int i=1;i<=cc;i++){
        iscir[cir[i]]=1;
        for(int j=h[cir[i]];~j;j=n1[j]){
            if(p[j]==cir[i%cc+1]){
                lt[i]=rt[i%cc+1]=w[j];
                cirsum+=lt[i];
                break;
            }
        }
    }sum[1]=0LL;
    for(int i=2;i<=cc;i++) sum[i]=sum[i-1]+rt[i];
}void init(){
    ee=0;
    memset(h,-1,sizeof(h));
    memset(vis,0,sizeof(vis));
    scanf("%d",&n);
    int x,y;
    long long z;
    for(int i=1;i<=n;i++){
        scanf("%d%d%lld",&x,&y,&z);
        ae(x,y,z);
    }
}void solvetree(int o){
    int s=0,e=1,pos=0,rt=cir[o];
    q[0]=rt;
    d[rt]=0;
    while(s<e){
        int u=q[s++];
        vis[u]=2*o;
        for(int i=h[u];~i;i=n1[i]){
            if(iscir[p[i]]==1 || vis[p[i]]==2*o) continue;
            d[q[e++]=p[i]]=d[u]+w[i];
            if(d[p[i]]>d[pos])  pos=p[i];
        }
    }s=0;e=1;
    dt[o]=d[pos];
    q[0]=pos;
    d[pos]=0;
    iscir[rt]=0;
    long long an=0LL;
    while(s<e){
        int u=q[s++];
        vis[u]=2*o+1;
        for(int i=h[u];~i;i=n1[i]){
            if(iscir[p[i]]==1 || vis[p[i]]==2*o+1) continue;
            d[q[e++]=p[i]]=d[u]+w[i];
            if(d[p[i]]>an)  an=d[p[i]];
        }
    }ans=max(ans,an);
    iscir[rt]=1;
}int main(){
    init();
    findcircle();
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=cc;i++)  solvetree(i);
    T.init();
    T.build(1,cc,1);
    Q.init();
    Q.build(1,cc,1);
    for(int i=1;i<=cc;i++){
        if(T.mx1[1]!=Q.mx1[1]){
            Ans=min(Ans,T.seg[1]+Q.seg[1]);
        }else{
            Ans=min(Ans,max(T.seg[1]+Q.seg2[1],T.seg2[1]+Q.seg[1]));
        }
        sum[i]=rt[i]+sum[(i>1)?(i-1):cc];
        T.modify(i,dt[i]+sum[i],1,cc,1);
        Q.modify(i,dt[i]-sum[i],1,cc,1);
    }printf("%.1lf\n",(double)max(Ans,ans)/(double)2.0);
    return 0;
}

• 相关文章