「codevs2370」LCA-倍增

发表于 | 分类于

题目链接

小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力

输入描述 Input Description

第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点
输出描述 Output Description
一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。

样例输入 Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
3
1 0 1
2 0 1
3
1 0
2 0
1 2

样例输出 Sample Output

1
2
3
4
5
1
1
2

数据范围及提示 Data Size & Hint

1
1<=n<=50000， 1<=m<=75000， 0<=c<=1000

这是一道lca（最近公共祖先）的裸题， 我们只需要求出两点到根节点的距离和， 再用 距离和 减去 两次 lca到根节点的距离，即为两点间的最短路径长度；

那么lca要怎么求呢？ 我们一起来看一看！ 首先我们需要定义一个数组depth[i]记录i点的深度（通过函数dfs求出）；一个二维数组father[x][i]记录点x向上2的i次方的祖先（通过函数pow_init求出）；已知x，y求lca的方法：看x,y两点是否为同一深度，我们移动较深的点直至两点位于同一深度，然后从2的i次方开始跳（i为 上跳2的i次方 最大不超过根节点 时i的值），i递减，如果跳到同一点，则不跳（防止跳过lca到了别的点），最后我们肯定会走到离lca深度为1的点，再跳一个深度即可！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cstdio>
#include <algorithm>
#include <cmath>
#define max(x, y) ((x) > (y) ? (x) : (y))
const int MAXN = 50000 + 2;
struct Edge{
	int to, w, next;
} edge[MAXN * 2];
int n, m, num, logn, deep;
int head[MAXN], depth[MAXN], dis[MAXN];
int father[MAXN][20];
inline void add_edge(int from, int to, int w) {
	edge[++num].to = to;
	edge[num].w = w;
	edge[num].next = head[from];
	head[from] = num;
}
inline void dfs(int x, int cur) { // x是点， cur是点的深度；
	depth[x] = cur;
	for(int i = head[x]; i; i = edge[i].next) { // 遍历；
		if(depth[edge[i].to]) continue; // 如果这个点是父亲；
		father[edge[i].to][0] = x;
		dis[edge[i].to] = edge[i].w + dis[x];//预处理树的前缀和；
		deep = max(deep, depth[x]); // 求树的深度；
		dfs(edge[i].to, depth[x] + 1);
	}
}
void pow_init(int n) {
	for(int j = 1;(1 << j) <= deep;j ++) {
		for(int i = 1;i <= n;i ++) {
			father[i][j] = father[father[i][j - 1]][j - 1];
            //倍增的运用，dalao自行脑补或者画张图，一张图很明了的， 倍增：这样可以借助之前的点做跳板，如果想暴力一个一个地枚举也可以，但是就比较慢了；
		}
	}
}
//遍历出父亲；
int LCA(int x, int y) {
	if(depth[x] < depth[y]) std::swap(x, y);
	if(depth[x] != depth[y]) {
		for(int i = logn; i >= 0; i--) {
			if(depth[x] - (1 << i) >= depth[y]) {
            //如果没有跳多； 就跳！；
				x = father[x][i];
			}
		}
	}
	if(x == y) return x;
   //如果跳到同一深度就是同一个点，说明两点在同一路径上面，找到了！；
	for(int i = logn; i >= 0; i--) {
		if(father[x][i] == father[y][i]) continue;
		x = father[x][i]; y = father[y][i];
	}
	return father[x][0];//再向上一部
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i < n; i++) {
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		add_edge(u, v, c);
		add_edge(v, u, c);
	}
	dfs(0, 1);
	pow_init(n);
	for(int i = 0; (1 << i) <= deep; i++) logn = i;logn++;
	scanf("%d", &m);
	for(int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		int r = LCA(x, y);
		printf("%d\n", dis[x] + dis[y] - dis[r] * 2);
	}
	return 0;
}