自动搬运

查看原文

来自洛谷，原作者为

	徐致远 **

搬运于2025-08-24 22:04:56，当前版本为作者最后更新于2019-03-05 17:13:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

完了...没高中读了QwQ，我要去打工送快递！！！QwQ

题解

这题其实还是挺好玩的。

首先随便钦定一个点，临时作为快递中心 。

然后可以$O(n)$计算出每一组点对到快递中心的距离和。设点对到快递中心最大距离和为$Max$，可能有多个点对到快递中心的距离和都是$Max$那么就把它们都存下来。

如果当前的快递中心在任意一组距离最大的点对之间最短路径上，那么答案就是$Max$不可能再小了。

如果有任意两组距离最大的点对，一组在当前快递中心的一棵子树里，另一组在另一棵子树里，那么答案同样也无法更小。

否则答案最优时的快递中心就有可能在当前唯一一棵有点对的子树中，那么就取这棵子树的重心作为临时快递中心，然后递归。由于每次取的都是重心，所以只会递归$\log n$层，总时间复杂度为$O(n\log n)$。

代码

#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100005;
int n,m,u[maxn],v[maxn],tot,lnk[maxn],son[maxn*2],w[maxn*2],nxt[maxn*2],sum,siz[maxn],maxp[maxn],rt,sub[maxn],dist[maxn],que[maxn],ans=1000000000;bool vis[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void add_e(int x,int y,int z){tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
void GetRoot(int now,int fa)     //找重心
{
	siz[now]=1;maxp[now]=0;
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(vis[son[i]]||son[i]==fa) continue;
		GetRoot(son[i],now);siz[now]+=siz[son[i]];
		if(siz[son[i]]>maxp[now]) maxp[now]=siz[son[i]];
	}
	if(sum-siz[now]>maxp[now]) maxp[now]=sum-siz[now];
	if(maxp[now]<maxp[rt]) rt=now;
}
void GetDist(int now,int fa,int st)
{
	sub[now]=st;
	for(int i=lnk[now];i;i=nxt[i])
		if(son[i]!=fa)
			{dist[son[i]]=dist[now]+w[i];GetDist(son[i],now,st);}
}
inline void Print(){printf("%d\n",ans);exit(0);}   //输出答案
void Solve(int now)
{
	if(vis[now]) Print();
	vis[now]=true;dist[now]=0;
	for(int i=lnk[now];i;i=nxt[i])
		{dist[son[i]]=w[i];GetDist(son[i],now,son[i]);} //先暴力计算距离
	int Max=0,len=0,las=0;
	for(int i=1;i<=m;i++)
	{
		if(dist[u[i]]+dist[v[i]]>Max){len=1;que[len]=i;Max=dist[u[i]]+dist[v[i]];}
		else if(dist[u[i]]+dist[v[i]]==Max) que[++len]=i; //刷最大距离和
	}
	if(Max<ans) ans=Max;
	for(int i=1;i<=len;i++)
	{
		if(sub[u[que[i]]]!=sub[v[que[i]]]) Print();   //分情况考虑答案
		if(!las) las=sub[u[que[i]]];
		if(sub[u[que[i]]]!=las) Print(); 
	}
	rt=0;sum=siz[las];GetRoot(las,0);Solve(rt);    //递归解决
}
int main()
{
	n=read();m=read();
	for(int i=1;i<n;i++)
	{
		int a=read(),b=read(),c=read();
		add_e(a,b,c);add_e(b,a,c);
	}
	for(int i=1;i<=m;i++){u[i]=read();v[i]=read();}
	sum=maxp[0]=n;GetRoot(1,0);Solve(rt);
	Print();
	return 0;
}