P3771 [CTSC2017]网络（树的直径+二分+双指针）

木xx木大 · 2021-02-03 17:37:00 · 题解

P3771 [CTSC2017]网络

首先有一个结论：存在一组最优解，使得新加入的边所连接的两个节点 a,b 都在原树的直径上。

证明：（参考yhx巨佬的博客）

假设原树的直径为 [s,u_1,u_2\dots t] ，长度为 l 。显然新添一条边后的直径 l'一定 \le l

若 a,b 在同一 u_i 的子树内，则 l'=l，显然不优。所以 a,b 一定在不同 u_i 子树内。

若 a\neq u_i，设 p_a 表示以 u_i 为根的子树内 a 的父亲，考虑连 (a,b) 改为连 (p_a,b) 的答案变化。

若 x,y 两点同在环上或环外，环由 [a\dots u_i\dots u_j\dots b,a] 变为 [p_a\dots u_i\dots u_j\dots b,p_a] ，环长变小，两点间距离不增

若 x 在环上，y 在环外，若 x\to y 的最短路径为 x\to a\to b\to y ，由直径的性质知它的长度不超过 s\to a\to b\to t 的长度。

改为连接 (p_a,b) 后，同理有 len(x\to p_a\to b\to y)\le len(s\to p_a\to b\to t)。而 len(s\to p_a\to b\to t)\le len(s\to a\to b\to t)。所以从 (a,b) 调整为 (p_a,b) 答案不增。若一直这样调整，则 a,b 都在原树的直径上时最优。

对于直径上每个点 u_i ，只有其子树内由 u_i 发出的最长链有可能影响答案。

然后问题就转化为了：一条链上每个点挂了一条边，现在可以添加一条长度为 c 的边连接链上的两点，使得图上两点间最大距离最小。

看到最大距离最小想到二分，设二分距离为 D，接下来考虑如何 check 即可。

为方便表述，设 L_i 表示到直径一端的距离，d_i 表示 i 挂的边的长度。

假设 i<j,a<b ，对于所有 L_j-L_i+d_i+d_j>D 的，必须满足 |L_a-L_i|+|L_b-L_j|+d_i+d_j+c\le D

把绝对值拆开得到

则我们需要分别求出 NN,PN,NP,PP 的最大值，然后判断满足上式的 a,b 是否存在。

求最大值：上式的左半部分可以看作 L_i+d_i,-L_i+d_i 相互加减的形式。若 i1<i2 且 d_{i1}-L_{i1}\le d_{i2}-L_{i2}，则 d_{i1}-L_{i1}+2L_{i1}\le d_{i2}-L_{i2}+2L_{i2}，即d_{i1}+L_{i1}\le d_{i2}+L_{i2}。所以若 i1<i2 且 d_{i1}-L_{i1}\le d_{i2}-L_{i2}，则 i1 不会对最大值产生贡献。枚举 j，用单调队列维护一下满足条件（L_j-L_i+d_i+d_j>D ）的 i ，更新 NN,PN,NP,PP 即可。

判断 a,b 是否存在：枚举 b ，用四个指针维护 a 的范围，判断是否有交集即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
    int n,m,V;
    const int N=1e5+5;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    struct edg{
        int to,nxt,w;
    }e[N<<1];
    int cnt,head[N],pre[N],ro,is[N],q[N];
    ll dis[N],L[N],d[N];
    namespace shortcut
    {
        bool check(ll x)
        {
            ll PN,PP,NN,NP,PX,NX,cur;
            int h=1,t=0;
            PN=PP=NN=NP=PX=NX=-INF;
            for(int i=1;i<=V;i++)
            {
                while(h<=t&&L[i]+d[i]-L[q[h]]+d[q[h]]>x)PX=max(PX,L[q[h]]+d[q[h]]),NX=max(NX,d[q[h]]-L[q[h]]),h++;
                cur=d[i]+m-x;
                PP=max(PP,L[i]+PX+cur),PN=max(PN,cur-L[i]+PX);
                NN=max(NN,cur-L[i]+NX),NP=max(NP,cur+L[i]+NX);
                while(h<=t&&d[q[t]]-L[q[t]]<d[i]-L[i])t--;
                q[++t]=i;
            }
            int pos1=1,pos2=V+1,pos3=0,pos4=V;
            for(int i=1;i<=V;i++)//这一段一定要想清楚再写，不然就会像我一样五行代码写两个小时
            {
                while(pos1<=V&&L[pos1]-L[i]<PN)pos1++;//[pos1,V]
                while(pos2&&L[pos2-1]+L[i]>=PP)pos2--;//[pos2,V]
                while(pos3<=V&&-L[pos3+1]+L[i]>=NP)pos3++;//[1,pos3]
                while(pos4&&-L[pos4]-L[i]<NN)pos4--;//[1,pos4]
                if(max(pos2,pos1)<=min(pos3,pos4))return 1;
            }
            return 0;
        }
        ll work()
        {
            ll l=0,r=INF,mid,ans;
            while(l<=r)
            {
                mid=(l+r)>>1;
                check(mid)?ans=mid,r=mid-1:l=mid+1;
            }
            return ans;
        }
    }
    void add(int u,int v,int w)
    {
        cnt++;
        e[cnt].to=v;
        e[cnt].nxt=head[u];
        head[u]=cnt;
        e[cnt].w=w;
    }
    void dfs(int u,int f)
    {
        if(dis[ro]<dis[u])ro=u;
        for(int i=head[u];i;i=e[i].nxt)
            if(e[i].to!=f&&!is[e[i].to])pre[e[i].to]=i,dis[e[i].to]=dis[u]+e[i].w,dfs(e[i].to,u);
    }
    void work()
    {
        while(scanf("%d%d",&n,&m)&&n&&m)
        {
            memset(head,0,sizeof(head));cnt=1;
            memset(is,0,sizeof(is));
            for(int i=1,u,v,w;i<n;i++)
                scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
            ro=1,dis[ro]=pre[ro]=0;
            dfs(ro,0);
            int rt2;ll mx;
            dis[ro]=pre[ro]=0;
            dfs(ro,0);
            rt2=ro,V=0,mx=dis[rt2];
            for(int u=rt2;u;u=e[pre[u]^1].to)is[u]=1;
            for(int u=rt2;u;u=e[pre[u]^1].to)
            {
                L[++V]=mx-dis[u];
                ro=u,dis[u]=0,dfs(ro,0);
                d[V]=dis[ro];
            }
            printf("%lld\n",shortcut::work());
        } 
    }
}
int main()
{
    FGF::work();
    return 0;
}