[BZOJ] 聚会

问题描述

Y 岛风景美丽宜人,气候温和,物产丰富。Y 岛上有 N 个城市,有 N-1 条城市间的道路连接着它们。每一条道路都连接某两个城市。幸运的是,小可可通过这些道路可以走遍 Y岛的所有城市。

神奇的是,乘车经过每条道路所需要的费用都是一样的。小可可,小卡卡和小 YY 经常想聚会,每次聚会,他们都会选择一个城市,使得 3 个人到达这个城市的总费用最小。由于他们计划中还会有很多次聚会,每次都选择一个地点是很烦人的事情,所以他们决定把这件事情交给你来完成。他们会提供给你地图以及若干次聚会前他们所处的位置,希望你为他们的每一次聚会选择一个合适的地点。

输入格式

第一行两个正整数,N 和 M。分别表示城市个数和聚会次数。

后面有 N-1 行,每行用两个正整数 A 和 B 表示编号为 A 和编号为 B 的城市之间有一条路。城市的编号是从 1 到 N 的。

再后面有 M 行,每行用三个正整数表示一次聚会的情况:小可可所在的城市编号,小卡卡所在的城市编号以及小 YY 所在的城市编号。

输出格式

一共有 M 行,每行两个数 Pos 和 Cost,用一个空格隔开。表示第 i 次聚会的地点选择在编号为 Pos 的城市,总共的费用是经过 Cost 条道路所花费的费用。

样例输入输出

Input

6 4

1 2

2 3

2 4

4 5

5 6

4 5 6

6 3 1

2 4 4

6 6 6

Output

5 2

2 5

4 1

6 0

数据范围

40%的数据中 N<=2000,M<=2000。

100%的数据中,N<=500000,M<=500000。

解析

假设只有两个点，那么集合点显然是两点的路径上的任一点，长度都为路径长。接下来拓展到三个点，假设我们取定了集合点在x和y的路径上，那么下一个点z一定要到这条路径上。具体是哪一个点呢？经过思考，这个点只有可能是LCA(x,z)或LCA(y,z)才可能是更优。而不管是哪一个，到x和y的路径长度和都是dis(x,y)。因此，我们有如下算法：

对于每三个点x,y,z，枚举两两公共祖先，算出到三个点的距离之和，取最小值作为答案。注意，该题卡常。

代码

#include <iostream>

#include <cstdio>

#define N 500002

using namespace std;

int head[N],ver[N*2],nxt[N*2],l;

int n,m,i,size[N],son[N],dep[N],fa[N],top[N],minx,p;

int read()

{

	char c=getchar();

	int w=0;

	while(c>'9'||c<'0') c=getchar();

	while(c<='9'&&c>='0'){

		w=w*10+c-'0';

		c=getchar();

	}

	return w;

}

void insert(int x,int y)

{

	l++;

	ver[l]=y;

	nxt[l]=head[x];

	head[x]=l;

}

void dfs1(int x,int pre)

{

	size[x]=1;

	fa[x]=pre;

	dep[x]=dep[pre]+1;

	for(int i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(y!=pre){

			dfs1(y,x);

			size[x]+=size[y];

			if(size[y]>size[son[x]]) son[x]=y;

		}

	}

}

void dfs2(int x,int t)

{

	top[x]=t;

	if(son[x]) dfs2(son[x],t);

	for(int i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(y!=fa[x]&&y!=son[x]) dfs2(y,y);

	}

}

int LCA(int u,int v)

{

	while(top[u]!=top[v]){

		if(dep[top[u]]<dep[top[v]]) swap(u,v);

		u=fa[top[u]];

	}

	if(dep[u]>dep[v]) swap(u,v);

	return u;

}

int dis(int x,int y)

{

	return dep[x]+dep[y]-2*dep[LCA(x,y)];

}

int main()

{

	n=read();m=read();

	for(i=1;i<n;i++){

		int u,v;

		u=read();v=read();

		insert(u,v);

		insert(v,u);

	}

	dfs1(1,0);

	dfs2(1,1);

	for(i=1;i<=m;i++){

		int x,y,z,p1,p2,p3;

		x=read();y=read();z=read();

		p1=LCA(x,y);p2=LCA(x,z);p3=LCA(y,z);

		int dis1=dis(x,p1)+dis(y,p1)+dis(z,p1);

		int dis2=dis(x,p2)+dis(y,p2)+dis(z,p2);

		int dis3=dis(x,p3)+dis(y,p3)+dis(z,p3);

		int minx=min(dis1,min(dis2,dis3));

		if(minx==dis1) printf("%d ",p1);

		else if(minx==dis2) printf("%d ",p2);

		else printf("%d ",p3);

		printf("%d\n",minx);

	}

	return 0;

}

巴特西