BZOJ1787 [Ahoi2008]Meet 紧急集合 【LCA】

1787: [Ahoi2008]Meet 紧急集合

Time Limit: 20 Sec  Memory Limit: 162 MB

Submit: 3578  Solved: 1635

[Submit][Status][Discuss]

Description

Input

Output

Sample 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

Sample Output

5 2

2 5

4 1

6 0

HINT

点很少，只有三个，画一下图，手动模拟一下就会发现：我们要求的就是画一条线将三个点连起来，使线最短

由于树路径的唯一性，连接三个点的路径是唯一的，但是由于走法的不同会导致因为重复部分路径而使路径增长

未使路径最短，我们就不能走复路，所以我们只需求出三者最大的LCA，再将另外一个点走上LCA所在路径就好了

如图：

具体LCA用倍增实现，复杂度O(mlogn + nlogn)，一个是预处理，一个是询问

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)

using namespace std;

const int maxn = 500005,maxm = 1000005,INF = 1000000000;

inline int RD(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

	return out * flag;

}

int dep[maxn],fa[maxn][20];

int N,M,head[maxn],nedge = 0,p[4];

struct node{int lca,u,v;}e[4];

struct EDGE{int to,next;}edge[maxm];

inline void build(int u,int v){

	edge[nedge] = (EDGE){v,head[u]}; head[u] = nedge++;

	edge[nedge] = (EDGE){u,head[v]}; head[v] = nedge++;

}

void dfs(int u,int f,int d){

	dep[u] = ++d; fa[u][0] = f;

	Redge(u) if (edge[k].to != f) dfs(edge[k].to,u,d);

}

void init(){REP(j,19) REP(i,N) fa[i][j] = fa[fa[i][j - 1]][j - 1];}

int LCA(int u,int v){

	if (dep[u] < dep[v]) u ^= v ^= u ^= v;

	int d = dep[u] - dep[v];

	for (int i = 0; (1 << i) <= d; i++)

		if ((1 << i) & d) u = fa[u][i];

	if (u == v) return u;

	for (int i = 19; i >= 0; i--)

		if (fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];

	return fa[u][0];

}

void B_Sort(){

	for (int i = 1; i <= 3; i++)

		for (int j = i + 1; j <= 3; j++)

			if (dep[e[i].lca] > dep[e[j].lca]) swap(e[i],e[j]);

}

void solve(){

	int ans,u;

	while (M--){

		REP(i,3) p[i] = RD();

		for (int i = 1,k = 0; i < 3; i++)

			for (int j = i + 1; j <= 3; j++)

				e[++k].u = i,e[k].v = j,e[k].lca = LCA(p[i],p[j]);

		B_Sort();

		//REP(i,3) printf("%d and %d  lca: %d\n",e[i].u,e[i].v,e[i].lca);

		REP(i,3) if (i != e[1].u && i != e[1].v) {u = p[i];break;}

		ans = dep[p[e[1].u]] + dep[p[e[1].v]] + dep[u] - 2 * dep[e[1].lca] - dep[e[3].lca];

		printf("%d %d\n",e[3].lca,ans);

	}

}

int main(){

	memset(head,-1,sizeof(head));

	N = RD(); M = RD();

	REP(i,N - 1) build(RD(),RD());

	dfs(1,0,0); init();

	solve();

	return 0;

}