自动搬运

查看原文

来自洛谷，原作者为

	木xx木大 已经 AFO 的菜鸡 OIer

搬运于2025-08-24 21:52:32，当前版本为作者最后更新于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=-L_i-L_j+d_i+d_j+c-D\le -L_a-L_b\\ PN=L_i-L_j+d_i+d_j+c-D\le L_a-L_b\\ NP=-L_i+L_j+d_i+d_j+c-D\le -L_a+L_b\\ PP=L_i+L_j+d_i+d_j+c-D\le L_a+L_b\\ $$

则我们需要分别求出 $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;
}