[数据结构与算法][CTSC2017]网络

网络

题解

首先需要我们观察出一个结论，我们先连接的边的两个端点必然都在原树的直径上。
我们将直径这条链当作原树的"根"来看看，即所有点的子树都是相对直径的子树。
如果我们连接的两个点在直径上同一个点的子树内，那么显然我们原来最长的直径长度必然不会减小，也就是说我们的最大值不变。
如果它连接的两个点在直径的不同子树中，这是原本直径两端点的距离虽然减小了，却没有减到最小。
我们考虑将条边的端点移动到子树的根，也就是直径上的节点上，直径两端点的距离会继续减小，增大的是这两子树内节点的距离，但这个距离增大后仍然不会超过直径现在的距离，否则它就是直径了。
所以必然存在一组最优解是两个点都在原树的直径上。

考虑在这个结论的基础上怎么求答案。
显然，对于最远距离距离最短这个问题，我们可以考虑二分求解，那么我们现在就相当于需要判断我们二分出的$mid$是否合法。
判断$mid$是否合法，不就是看我们当前的最大值是否小于$mid$嘛。
由于我们选择节点只会在直径上，所以每个直径上的点我们只需要记录下来它子树内最长链的长度。
我们记点$i$内的最长链长度为$d_i$，它在直径上的位置为$L_i$。
对于直径上两个最长链距离大于$mid$的点，它们之间就只能走我们新连的边，我们记我们新连的边为$(a,b)(a<b)$，这里的$a,b$大小是直径上的顺序，转化成数学表达式：
$$?i,j(i<j\wedge L_j?L_i+d_i+d_j>mid),|L_i?L_a|+|L_j?L_b|+L+d_i+d_j?mid$$我们不妨将后面的绝对值拆开一下，相当于满足$4$个式子。
$$\begin{gathered} L_i+L_j+L?mid+d_i+d_j?L_a+L_b \\ {L}_i?L_j+L?mid+d_i+d_j?L_a?L_b \\ ?L_i+L_j+L?mid+d_i+d_j??L_a+L_b \\ ?L_i?L_j+L?mid+d_i+d_j??L_a?L_b \end{gathered}$$我们可以用线段树维护出对于$i$满足条件的$j$，计算它们出每个$i$，这四个式子左半边得到的最大值。
事实上我们需要在线段树上维护的就只有$d_i+L_i$与$d_i?L_i$的最大值。
我们得到了$L_a+L_b,L_a?L_b,?L_a+L_b,?L_a?L_b$这四个式子的限制后，我们可以尝试枚举每个$a$，看有没有能让满足条件的$b$，如果有的话就说明对于我们这个$mid$有解。
这个排序后用指针就可以维护了，相当于看$4$个集合有没有交集。

时间复杂度$O\left(n{\log }^{2}n\right)$。

源码

也比较好写。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double Ld;
typedef pair<LL,LL> pii;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mo=1e9+7;
const int mod=1e6+7;
const int inv2=499122177;
const int inv3=332748118;
const int jzm=2333;
const int zero=2000;
const int n1=100;
const int orG=3,ivG=332748118;
const double Pi=acos(-1.0);
const double feps=1e-11;
const double eps=1e-9;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}
int n,L,head[MAXN],tot,pre[MAXN],father[MAXN],U,V;
int ord[MAXN],m,dep[MAXN],tmpa[MAXN],tmpb[MAXN],tota,totb;
LL f[MAXN],dis[MAXN],mx,b[MAXN];
bool key[MAXN];
struct edge{int to,nxt,paid;}e[MAXN<<1];
void addEdge(int u,int v,int w){e[++tot]=(edge){v,head[u],w};head[u]=tot;}
void dosaka(int u,int fa){
	f[u]=0;pre[u]=u;father[u]=fa;dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to,w=e[i].paid;
		if(v==fa)continue;dosaka(v,u);
		if(f[u]+f[v]+w>mx)mx=f[u]+f[v]+w,U=pre[u],V=pre[v];
		if(f[v]+w>f[u])f[u]=f[v]+w,pre[u]=pre[v];
	}
}
void dosaka2(int u,int fa){
	f[u]=0;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;if(v==fa||key[v])continue;
		dosaka2(v,u);f[u]=max(f[u],f[v]+e[i].paid);
	}
}
class SegmentTree{
	private:
		LL tr1[MAXN<<2],tr2[MAXN<<2];
		void pushup(int rt){
			tr1[rt]=max(tr1[lson],tr1[rson]);
			tr2[rt]=max(tr2[lson],tr2[rson]);
		}
	public:
		void build(int rt,int l,int r){
			if(l==r){tr1[rt]=tr2[rt]=-INF;return ;}int mid=l+r>>1;
			build(lson,l,mid);build(rson,mid+1,r);pushup(rt); 
		}
		void insert(int rt,int l,int r,int ai,pii aw){
			if(l>r||l>ai||r<ai)return ;int mid=l+r>>1;
			if(l==r){tr1[rt]=aw.fir;tr2[rt]=aw.sec;return ;}
			if(ai<=mid)insert(lson,l,mid,ai,aw);
			if(ai>mid)insert(rson,mid+1,r,ai,aw);
			pushup(rt);
		} 
		LL query1(int rt,int l,int r,int al,int ar){
			if(l>r||l>ar||r<al||al>ar)return -INF;
			if(al<=l&&r<=ar)return tr1[rt];
			int mid=l+r>>1;LL res=-INF;
			if(al<=mid)res=max(res,query1(lson,l,mid,al,ar));
			if(ar>mid)res=max(res,query1(rson,mid+1,r,al,ar));
			return res;
		}
		LL query2(int rt,int l,int r,int al,int ar){
			if(l>r||l>ar||r<al||al>ar)return -INF;
			if(al<=l&&r<=ar)return tr2[rt];
			int mid=l+r>>1;LL res=-INF;
			if(al<=mid)res=max(res,query2(lson,l,mid,al,ar));
			if(ar>mid)res=max(res,query2(rson,mid+1,r,al,ar));
			return res;
		}
}T;
bool check(LL mid){
	T.build(1,1,totb);LL tp1=-INF,tp2=-INF,tp3=-INF,tp4=-INF;
	for(int i=m;i>0;i--){
		int t=upper_bound(b+1,b+totb+1,mid+dis[i]-f[ord[i]])-b;
		LL tmp1=T.query1(1,1,totb,t,totb),tmp2=T.query2(1,1,totb,t,totb);
		tp1=max(tp1,f[ord[i]]+dis[i]+tmp1+L-mid);
		tp2=max(tp2,f[ord[i]]-dis[i]+tmp1+L-mid);
		tp3=max(tp3,f[ord[i]]+dis[i]+tmp2+L-mid);
		tp4=max(tp4,f[ord[i]]-dis[i]+tmp2+L-mid);
		t=lower_bound(b+1,b+totb+1,dis[i]+f[ord[i]])-b;
		T.insert(1,1,totb,t,mkpr(f[ord[i]]+dis[i],f[ord[i]]-dis[i]));
	}
	int r1=m+1,r2=1,l3=0,l4=m;
	for(int i=1;i<=m;i++){
		while(r1>1&&dis[r1-1]+dis[i]>=tp1)r1--;
		while(r2<=m&&dis[r2]-dis[i]<tp2)r2++;
		while(l3<m&&-dis[l3+1]+dis[i]>=tp3)l3++;
		while(l4>0&&-dis[l4]-dis[i]<tp4)l4--;
		if(min(l3,l4)>=max(r1,r2))return 1;
	}
	return 0;
}
int main(){
	while(scanf("%d %d",&n,&L)!=EOF&&n+L){
		for(int i=1;i<n;i++){
			int u,v,w;read(u);read(v);read(w);
			addEdge(u,v,w);addEdge(v,u,w);
		}
		dosaka(1,0);
		int nowu=U,nowv=V;
		if(dep[nowu]>dep[nowv])swap(nowu,nowv);
		while(dep[nowv]>dep[nowu])tmpb[++totb]=nowv,nowv=father[nowv];
		while(nowu^nowv)tmpa[++tota]=nowu,tmpb[++totb]=nowv,
			nowu=father[nowu],nowv=father[nowv];
		for(int i=1;i<=totb;i++)ord[++m]=tmpb[i];ord[++m]=nowu;
		for(int i=tota;i>0;i--)ord[++m]=tmpa[i];
		for(int i=1;i<=m;i++)key[ord[i]]=1;
		for(int i=1;i<=m;i++)dosaka2(ord[i],0);dis[1]=0;
		for(int i=1;i<m;i++)
			for(int j=head[ord[i]];j;j=e[j].nxt)
				if(e[j].to==ord[i+1])dis[i+1]=dis[i]+e[j].paid;
		totb=0;for(int i=1;i<=m;i++)b[++totb]=dis[i]+f[ord[i]];
		sort(b+1,b+totb+1);totb=unique(b+1,b+totb+1)-b-1;
		LL l=0,r=dis[m];
		while(l<r){LL mid=l+r>>1;if(check(mid))r=mid;else l=mid+1;}
		printf("%lld\n",l);
		for(int i=1;i<=n;i++)head[i]=key[i]=dis[i]=f[i]=pre[i]=dep[i]=0;
		mx=U=V=tot=tota=totb=m=0;
	}
	return 0;
}

谢谢！！！