转载注明来源:https://www.cnblogs.com/syc233/p/13693027.html


树的直径+尺取法。


题意

给定一棵带边权无根树,在其直径上求出一段长度不超过 \(s\) 的路径 \(F\) ,使得离路径距离最远的点到路径的距离最短。


题解

首先,在 \(s\) 的限制下,\(F\) 应尽量长。这个画下图就不难明白。

先求出直径,令直径的两端点分别为 \(x,y\)

定义一个关于直径上点 \(u\) 的函数 \(dis(u)\) ,表示除直径上的点到 \(u\) 的最远距离。那么就有一个结论:

对于任意一个直径上的点 \(u\) ,有 \(dis(u)\leq d(u,x),dis(u)\leq d(u,y)\)

证明:

若存在一个直径上的点满足 \(dis(u)>d(u,x)\) ,那么有 \(dis(u)+d(u,y)>d(u,x)+d(u,y)\) 。显而易见, 此时 \(x,y\) 不可能是直径的两个端点。

同理,\(dis(u)>d(u,y)\) 同样不合法。

证毕。

考虑一条路径,如何计算它的偏心距。设路径 \(F\) 的两端点分别为 \(a,b\) ,根据偏心距的定义,可以重写一下题目中给出的式子:

\[{\rm{ECC}}(F)=\max\{\max\{dis(u),u\in F\},d(x,a),d(b,y)\} \]

设直径为 \(L\) 。对于点 \(v\) ,满足 \(v\in L,v \not \in F\) ,有(假如 \(v\)\(x\)\(a\) 之间,在另一边同理):

\[dis(v)\leq d(x,v)\leq d(x,a) \]

那么可以重写一下上面的式子:

\[{\rm{ECC}}(F)=\max\{\max\{dis(u),u\in L\},d(x,a),d(b,y)\} \]

发现 \(\max\{dis(u),u\in L\}\)\(F\) 无关,那么我们可以在直径上尺取求出所有 \(F\)\(\max\{d(x,a),d(b,y)\}\) 的最小值,再与 \(\max\{dis(u),u\in L\}\) 取max即可。


\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 305
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;

template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

struct edge
{
	int u,v,w,next;
	edge(int u,int v,int w,int next):u(u),v(v),w(w),next(next){}
	edge(){}
}e[maxn<<1];

int head[maxn],k;

inline void add(int u,int v,int w)
{
	e[k]=edge(u,v,w,head[u]);
	head[u]=k++;
}

int n,s;
int dis[maxn],fro[maxn];
bool vis[maxn];

inline int dfs(int u,int fa)
{
	int res=u;
	for(int i=head[u];~i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa||vis[v]) continue;
		fro[v]=u;
		dis[v]=dis[u]+e[i].w;
		int x=dfs(v,u);
		if(dis[x]>dis[res]) res=x;
	}
	return res;
}

int main()
{
	// freopen("P1099.in","r",stdin);
	read(n),read(s);
	memset(head,-1,sizeof(head));
	for(int i=1,u,v,w;i<n;++i)
	{
		read(u),read(v),read(w);
		add(u,v,w);
		add(v,u,w);
	}
	int x=dfs(1,0);dis[x]=fro[x]=0;
	int y=dfs(x,0),ans=INF;
	for(int i=y,j=y;i;i=fro[i])
	{
		while(fro[j]&&dis[i]-dis[fro[j]]<=s) j=fro[j];
		ans=min(ans,max(dis[j],dis[y]-dis[i]));
		vis[i]=true;
	}
	for(int i=y;i;i=fro[i])
	{
		dis[i]=0;
		int j=dfs(i,0);
		ans=max(ans,dis[j]);
	}
	printf("%d\n",ans);
	return 0;
}