[CTSC2017]网络

清疚 2021-12-23 15:09 167阅读 0赞

[\[CTSC2017\]网络][CTSC2017]

连一条长度为len的边，使得基环树的直径最小

结论：一定连在某条直径两个点上（否则更靠近不劣）

然后二分答案判定。

![1399631-20190427190518213-1988611446.png][]

dp\[i\]：链上一个点往下延伸的最大深度

考虑对于任意两个点对最短路径都不能大于mid

就是：任意的(i<j)，min(sum\[j\]-sum\[i\]+dp\[i\]+dp\[j\],len+|sumb-sumj|+|sumi-suma|+dp\[i\]+dp\[j\])<mid

前面的min比较好处理，直接按照sum+dp,dp-sum排序，双指针搞一下

不能满足前面的min的点对i，j，必然要满足后面的。

把绝对值拆开成4个，对于任意的i，j，选择的a，b都要使得这些4\*k个不等式成立。

suma,sumb移项，所以4个不等式右边都要取最大的（任意转化为最值）

所以双指针的时候可以再用树状数组（为了i<j）找到4个lim

然后移项。

枚举b，sum升序降序排序，四指针维护。

每次看区间的交是否为空。

![1399631-20190427191955041-599449692.png][]

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    
    namespace Miracle{
    const int N=1e5+5;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    int n;
    struct node{
        int nxt,to;
        int val;
    }e[2*N];
    int hd[N],cnt;
    void add(int x,int y,int z){
        e[++cnt].nxt=hd[x];
        e[cnt].to=y;
        e[cnt].val=z;
        hd[x]=cnt;
    }
    ll ans,len;
    ll L,R;
    int mem[N],fa[N],vf[N];
    int on[N];
    ll sum[N];
    struct po{
        ll v;
        int id;
        po(){}
        po(ll vv,int dd){
            v=vv;id=dd;
        }
    };
    struct qs{
        po p[N];
        int sz;
        void push(ll v,int d){
            p[++sz]=po(v,d);
        }
        void clear(){
            sz=0;
        }
        il po &operator[](const int &x){
        return p[x];}
        il const po &operator[](const int &x) const {
        return p[x];}
    }su,sd,up,dw;//member's number is num
    
    bool cmpu(po a,po b){
        //sheng
        return a.v<b.v;
    }
    bool cmpd(po a,po b){
        //jiang
        return a.v>b.v;
    }
    int st,nd,num;
    ll mx;
    struct tr{
        ll f[N];
        void clear(){
            memset(f,-0x3f,sizeof f);
        }
        void ins(int x,ll v){
            for(;x<=n;x+=x&(-x)) f[x]=max(f[x],v);
        }
        ll query(int x){
            ll ret=-inf;
            for(;x;x-=x&(-x)) ret=max(ret,f[x]);
            return ret;
        }
    }t[2];
    //t[0]:dp-sum
    //t[1]:dp+sum
    void dfs1(int x,ll dis){
        if(dis>mx) {
            mx=dis;st=x;
        }
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa[x]) continue;
            fa[y]=x;
            dfs1(y,dis+e[i].val);
        }
    }
    void dfs2(int x,ll dis){
        if(dis>mx){
            mx=dis;nd=x;
        }
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa[x]) continue;
            fa[y]=x;
            vf[y]=e[i].val;
            dfs2(y,dis+e[i].val);
        }
    }
    ll dp[N];
    void fin(int x){
        dp[x]=0;
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa[x]||on[y]) continue;
            fa[y]=x;
            fin(y);
            L=max(L,dp[x]+dp[y]+e[i].val);
            dp[x]=max(dp[x],dp[y]+e[i].val);
        }
    }
    struct pointer{
        int ptr;
        ll lim;
        void clear(){
            ptr=0;lim=-inf;
        }
        void upda(ll v){
            lim=max(lim,v);
        }
    }p[5];
    pair<int,int>tp;
    void con(int l,int r){
        tp.fi=max(tp.fi,l);
        tp.se=min(tp.se,r);
    }
    bool che(ll mid){
        ///warning!!!! dp[mem[...[].id]]
        t[0].clear();t[1].clear();
        for(reg i=1;i<=4;++i) p[i].clear();
        int ptr=0;
        for(reg j=1;j<=num;++j){
            while(ptr<num&&dw[ptr+1].v+up[j].v>mid) {
                ++ptr;
                t[0].ins(dw[ptr].id,dw[ptr].v);
                t[1].ins(dw[ptr].id,sum[dw[ptr].id]+dp[mem[dw[ptr].id]]);
            }
            if(ptr){
                ll djss=dp[mem[up[j].id]]-sum[up[j].id],djas=up[j].v;
                ll diss=t[0].query(up[j].id-1),dias=t[1].query(up[j].id-1);
                p[1].upda(len-mid+djss+dias);
                p[2].upda(len-mid+diss+djas);
                p[3].upda(len-mid+dias+djas);
                p[4].upda(len-mid+diss+djss);
            }
        }
        p[1].ptr=p[4].ptr=1;
        for(reg b=1;b<=num;++b){
            while(p[1].ptr<=num&&su[p[1].ptr].v-p[1].lim<su[b].v) ++p[1].ptr;
            while(p[2].ptr<num&&su[p[2].ptr+1].v+p[2].lim<=su[b].v) ++p[2].ptr;
            while(p[3].ptr<num&&-sd[p[3].ptr+1].v+p[3].lim<=su[b].v) ++p[3].ptr;
            while(p[4].ptr<=num&&-sd[p[4].ptr].v-p[4].lim<su[b].v) ++p[4].ptr;
            tp.fi=1;tp.se=num;
            con(p[1].ptr,num);
            con(1,p[2].ptr);
            con(num-p[3].ptr+1,num);
            con(1,num-p[4].ptr+1);
            if(tp.fi<=tp.se) return true;
        }
        return false;
        ///warning!!!! dp[mem[...[].id]]
    }
    void clear(){
        ans=inf;num=0;st=nd=0;
        memset(sum,0,sizeof sum);
        memset(fa,0,sizeof fa);
        memset(vf,0,sizeof vf);
        memset(on,0,sizeof on);
        memset(hd,0,sizeof hd);
        su.clear();sd.clear();up.clear();dw.clear();
        cnt=0;
        L=0,R=0;
    }
    int main(){
        while(1){
            clear();
            rd(n);rd(len);
            if(n==0&&len==0) break;
            mx=-1;
            int x,y,z;
            for(reg i=1;i<n;++i){
                rd(x);rd(y);rd(z);
                add(x,y,z);add(y,x,z);
            }
            if(n==1){
                puts("0");continue;
            }
            dfs1(1,0);
            fa[st]=0;
            mx=-1;
            dfs2(st,0);
    /*RRR*/ R=mx;
            num=0;
            x=nd;
            while(x){
                mem[++num]=x;
                on[x]=1;
                sum[num]=sum[num-1]+vf[mem[num-1]];
                x=fa[x];
            }
            memset(fa,0,sizeof fa);
    /*LLL*/ for(reg i=1;i<=num;++i){
                fin(mem[i]);
            }
    
            for(reg i=1;i<=num;++i){
                su.push(sum[i],i);
                sd.push(sum[i],i);
                up.push(dp[mem[i]]+sum[i],i);
                dw.push(dp[mem[i]]-sum[i],i);
            }
            sort(su.p+1,su.p+num+1,cmpu);
            sort(sd.p+1,sd.p+num+1,cmpd);
            sort(up.p+1,up.p+num+1,cmpu);
            sort(dw.p+1,dw.p+num+1,cmpd);
    
            while(L<=R){
                ll mid=(L+R)/2;
                if(che(mid)){
                    ans=mid;R=mid-1;
                }else L=mid+1;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

二分判定突破口

判定min的或关系。不涉及a,b的先去掉，对于剩下的任意变成最值，纯粹解不等式了。

大量运用排序+双指针。

转载于:https://www.cnblogs.com/Miracevin/p/10779859.html

[CTSC2017]: https://www.luogu.org/problemnew/show/P3771
[1399631-20190427190518213-1988611446.png]: /images/20211223/be1f4922f1d449e485b2f241c47ff5b3.png
[1399631-20190427191955041-599449692.png]: /images/20211223/70360c06f2bc4ce3bfac7fb81270ab78.png