BZOJ1787【AHOI2008】Meet紧急集合

Problem

【AHOI2008】Meet 紧急集合

Description

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有$N$个等待点，有$N-1$条道路连接着它们，每条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一点到另一点要花费一个游戏币。参加游戏的三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对讲机（用于和同组的成员联系）。当集合号吹响后，每个成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在$N$个等待点中确定一个集合点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。
小可可和他的朋友邀请你一起参加这个游戏，有你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

Input

第一行两个正整数$N$和$M$（$N\le 5\times 10^5$，$M\le 5\times 10^5$），之间用一个空格隔开。分别表示等待点的个数（等待点也从$1$到$N$进行编号）和获奖所需完成的集合次数。
随后有$N-1$行，每行两个正整数$A$和$B$，之间用空格隔开，表示编号为$A$和编号为$B$的等待点之间有一条路。
接着还有$M$行，每行用三个正整数表示某次集合前小可可、小可可的朋友以及你所在的等待点的编号。

Output

一共有$M$行，每行两个数$P$和$C$，用一个空格隔开。其中第$i$行表示第$i$次集合点选择在编号为$P$的等待点，集合总共的花费是$C$个游戏币。

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

$40\%$的数据中，$N\le 2000$，$M\le 2000$
$100\%$的数据中，$N\le 500000$，$M\le 500000$

标签：LCA

Solution

对于每组询问，找出三个点中两两的$lca$，这三个$lca$中必然至少有两个相同。找出那个不同的$lca$，以它为集合点，算出距离，一定最小。
原理可见$zhber$博客。

Code

#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 500000
using namespace std;
int n, m, fa[MAX_N+5][35], dep[MAX_N+5];
vector <int> G[MAX_N+5];
void DFS(int u) {
    for (int i = 1; i <= 30; i++)	if (dep[u] >= (1<<i))	fa[u][i] = fa[fa[u][i-1]][i-1];
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];	if (v == fa[u][0])	continue;
        fa[v][0] = u, dep[v] = dep[u]+1, DFS(v);
    }
}
int LCA(int a, int b) {
    if (dep[a] < dep[b])	swap(a, b);
    for (int i = 30; i >= 0; i--)	if (dep[a]-(1<<i) >= dep[b])	a = fa[a][i];
    if (a == b)	return a;
    for (int i = 30; i >= 0; i--)	if (fa[a][i] != fa[b][i])	a = fa[a][i], b = fa[b][i];
    return fa[a][0];
}
int calc(int a, int b) {int c = LCA(a, b);    return dep[a]+dep[b]-2*dep[c];}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i < n; i++)	scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);	DFS(1);
    while (m--) {
        int a, b, c;	scanf("%d%d%d", &a, &b, &c);
        int lca = LCA(a, b)^LCA(a, c)^LCA(b, c);
        int dis = calc(a, lca)+calc(b, lca)+calc(c, lca);
        printf("%d %d\n", lca, dis);
    }
    return 0;
}