洛谷4886 快递员 点分治

题目链接

题意：
给你一棵n个点的树，有m个点对，你要在树上找一个点x，使得对于所有的点对(u,v)，dis(x,u)+dis(x,v)最小，输出这个最小值。n,m<=100000

题解：

感觉之前点分治学得不好，所以最近想补一下。

这个题其实那道题想过点分治，但是好像并不满足分治常见的子问题结构，就没想好怎么处理。看了题解之后觉得还是挺妙的。

首先我们考虑暴力的话是枚举每一个点，然后以这个点为根dfs一遍，就可以求出这个点到所有点的距离，然后再枚举点对算答案，复杂度是O(n2+n∗m)。我们其实不难感觉到，如果我们现在知道了在某个位置的答案，只有很少的位置可能使答案继续变小，我们考虑只去在这些可能让答案变优的点dfs和对于点对算答案。

首先说一下什么情况下可以确实当前点就是最优点。首先，以这个点为根，如果当前这个点在距离最长的点对的路径上，也就是距离最长的点对位于这个点的不同子树内，那么答案一定不会比当前答案更优，原因是答案不管怎么变，都不会比当前两点之间的简单路径更短的情况了。然后如果有两个及以上的最长路径点对，并且这些点对中存在两个点对在这个点的不同子树里，那么答案也一定不会变小了，因为你再往别的地方走顶多是一个变小一个变大，在不同子树是没办法同时变小的，而变大的那个将是你的结果，所有不会变优了。唯一需要继续求的就是所有离当前点距离和最长的点对都在这个点的同一个子树里，那么我们需要到这个子树里去求。

但是我们发现一个问题，如果树是一条链，你直接这样走到子节点再求一遍，复杂度还是不对的。我们考虑在这时候点分治，每次先确定该往当前点的哪个子树走，再在这个子树内找重心，在重心处重新dfs一遍并统计与所有点对的答案。根据点分治的性质，我们最多需要分治的层数是logn级别，所以我们只需要dfs并算m个点对的答案的点只有logn个，于是复杂度是O(nlogn)。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,m,u[100010],v[100010],hed[100010],fa[100010],dep[100010];
int rt,sz[100010],mx[100010],vis[100010],ans,q[100010],cnt;
struct node
{
	int to,dis,next;
}a[200010];
inline int read()
{
	int x=0;
	char s=getchar();
	while(s>\'9\'||s<\'0\')
	s=getchar();
	while(s>=\'0\'&&s<=\'9\')
	{
		x=x*10+s-\'0\';
		s=getchar();
	}
	return x;
}
inline void add(int from,int to,int dis)
{
	a[++cnt].to=to;
	a[cnt].dis=dis;
	a[cnt].next=hed[from];
	hed[from]=cnt;
}
inline void getrt(int x,int f,int size)
{
	sz[x]=1;
	mx[x]=0;
	for(int i=hed[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==f||vis[y])
		continue;
		getrt(y,x,size);
		sz[x]+=sz[y];
		mx[x]=max(mx[x],sz[y]);
	}
	mx[x]=max(mx[x],size-sz[x]);
	if(mx[x]<mx[rt])
	rt=x;
}
inline void dfs(int x,int f,int dis,int g)
{
	dep[x]=dis;
	fa[x]=g;
	for(int i=hed[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==f)
		continue;
		dfs(y,x,dep[x]+a[i].dis,g);
	}
}
inline void solve(int x)
{
	if(vis[x])
	return;
	dep[x]=0;
	vis[x]=1;
	for(int i=hed[x];i;i=a[i].next)
	{
		int y=a[i].to;
		dfs(y,x,a[i].dis,y);
	}
	cnt=0;
	int ji=0;
	for(int i=1;i<=m;++i)
	{
		if(dep[u[i]]+dep[v[i]]>ji)
		{
			ji=dep[u[i]]+dep[v[i]];
			cnt=1;
			q[cnt]=i;
		}
		else if(dep[u[i]]+dep[v[i]]==ji)
		q[++cnt]=i;
	}
	ans=min(ans,ji);
	ji=0;
	for(int i=1;i<=cnt;++i)
	{
		if(fa[u[q[i]]]!=fa[v[q[i]]])
		return;
		else
		{
			if(!ji)
			ji=fa[u[q[i]]];
			else if(ji!=fa[u[q[i]]])
			return;
		}
	}
	rt=0;
	getrt(ji,x,sz[ji]);
	solve(rt);
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n-1;++i)
	{
		int x=read(),y=read(),z=read();
		add(x,y,z);
		add(y,x,z);
	}
	for(int i=1;i<=m;++i)
	{
		u[i]=read();
		v[i]=read();
	}
	mx[0]=2e9;
	ans=2e9;
	getrt(1,0,n);
	solve(rt);
	printf(\"%d\\n\",ans);
	return 0;
}