HDU-6115

我们将A省简化为由N个城市组成，某些城市之间存在双向道路，而且A省的交通有一个特点就是任意两个城市之间都能通过道路相互到达，且在不重复经过城市的情况下任意两个城市之间的到达方案都是唯一的。聪明的你一定已经发现，这些城市构成了树这样一个结构。

现在百度陆续开了许许多多的子公司。每家子公司又会在各城市中不断兴建属于该子公司的办公室。

由于各个子公司之间经常有资源的流动，所以公司员工常常想知道，两家子公司间的最小距离。
我们可以把子公司看成一个由办公室组成的集合。那么两个子公司A和B的最小距离定义为min(dist(x，y))（x∈A，y∈B）。其中dist(x，y)表示两个办公室之间的最短路径长度。

现在共有Q个询问，每次询问分别在两个子公司间的最小距离。

Input第一行一个正整数T，表示数据组数。

对于每组数据：

第一行两个正整数N和M。城市编号为1至N，子公司编号为1至M。

接下来N-1行给定所有道路的两端城市编号和道路长度。

接下来M行，依次按编号顺序给出各子公司办公室所在位置，每行第一个整数G，表示办公室数，接下来G个数为办公室所在位置。

接下来一个整数Q，表示询问数。

接下来Q行，每行两个正整数a,b(a不等于b），表示询问的两个子公司。

【数据范围】

0<=边权<=100

1<=N,M,Q,工厂总数<=100000Output对于每个询问，输出一行，表示答案。Sample Input

Sample Output

1
0
0

题解：这是一道求最近公共祖先的题；我们可以随意选取一个为树根；然后可以利用邻接表将父亲和孩子联系在一起；

然后用DFS搜索记录每一节的权值和其深度；然后输入两个数，先将其深度提到相同，判断是否相等，如果不等，则继续提取

直到相同（这里用a=father[a]）；

AC代码为：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = 0x3fff3fff;
const int MAXN = 100010;
struct node {
int to, wt, next;
} tree[MAXN * 2];

int head[MAXN], cnt;
int n, m, q;
vector<int> office[MAXN];

void add(int from, int to, int wt) {
tree[cnt].to = to;
tree[cnt].wt = wt;
tree[cnt].next = head[from];
head[from] = cnt++;
}

void init() {
memset(head, -1, sizeof(head));
cnt = 0;
for (int i = 0; i < MAXN; ++i)office[i].clear();
}

int deep[MAXN], f[MAXN], len2f[MAXN];

void dfsDep(int root, int par, int d) {
deep[root] = d;
f[root] = par;
for (int i = head[root], to = -1; i != -1; i = tree[i].next) {
to = tree[i].to;
if (to != par) {
len2f[to] = tree[i].wt;
dfsDep(to, root, d + 1);
}
}
}

int getDis(int a, int b) {
int res = 0;
while (deep[a] < deep[b]) {
res += len2f[b];
b = f[b];
}
while (deep[a] > deep[b]) {
res += len2f[a];
a = f[a];
}
while (a != b) {
res += len2f[a] + len2f[b];
a = f[a];
b = f[b];
}
return res;
}

int main() {

int t, a, b, c;
scanf("%d", &t);
while (t--) {
init();
scanf("%d%d", &n, &m);
for (int i = 1; i < n; ++i) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
for (int i = 1; i <= m; ++i) {
scanf("%d", &a);
for (int k = 0; k < a; ++k) {
scanf("%d", &b);
office[i].push_back(b);
}
}

dfsDep(1, -1, 0);

scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
scanf("%d%d", &a, &b);
c = INF;
for (int j = 0, asz = office[a].size(); j < asz; ++j) {
for (int k = 0, bsz = office[b].size(); k < bsz; ++k) {
c = min(c, getDis(office[a][j], office[b][k]));
if (c == 0) { j = asz; break; }
}
}
printf("%d ", c);
}
}
return 0;
}