HDU 2586 How far away ？——树上节点最短距离，LCA， 双亲表示法+暴力从下至上追溯，孩子链表示法+（Tarjan 或 欧拉环游RMQ+（ST 或 SegmentTree））

Posted on | In | Comments:
| 57k | 52 mins.

标题真长。。。

HDU 2586 How far away ？——树上节点最短距离，LCA， 双亲表示法+暴力从下至上追溯，孩子链表示法+（Tarjan 或 欧拉环游RMQ+（ST 或 SegmentTree））

http://acm.hdu.edu.cn/showproblem.php?pid=2586

四种解法：

- 双亲表示法+暴力从下至上追溯
- 孩子链表示法+Tarjan
- 孩子链表示法+欧拉环游RMQ+ST
- 孩子链表示法+欧拉环游RMQ+SegmentTree

对于建树的问题，要解决父节点和子节点的问题：

- 第一种解法中，双亲表示法，用一个一维数组houses来储存所有节点，houses[x].fa表示该节点的父节点，当两个子树被合并造成冲突时，将其中一棵树倒置

如：

1 2
↑ ↑
3 4
↑ ↑
5 6

此时要连接3和4，必定会造成冲突，因为，若将3作为4的父节点（3 → 4），4就会有两个父节点，于是把4 ← 6这一支倒置成 4 → 6
于是：

1 2
↑ ↑
3 → 4
↑ ↓
5 6
（5成为合并以后的根元素）

- 剩下三种解法则利用孩子链表示法，记录所有与目标节点相连接的节点（包括一个父节点和一个子节点），然后随便选取一个节点作为父节点，用dfs遍历这些连接的节点，同时用visited数组来跳过其中的父节点

解法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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>

using namespace std;

//31ms

//双亲表示法

//当建树遇到冲突时，将冲突的一支树倒置

struct Node
{
	int disToFa;
	int fa;
};

Node houses[40005];
int visited[40005];

void add(int x, int y, int z) {
	if (!houses[x].fa) {//若x还没有父元素
		//把x挂在y下
		houses[x].fa = y;
		houses[x].disToFa = z;

	} else {

		if (!houses[y].fa) { //若y还没有父元素
			//把y挂在x下
			houses[y].fa = x;
			houses[y].disToFa = z;
		} else {
			//x和y都有父元素了

			//将x的父元素向上追溯全部变成子元素（将这一支箭头全部倒置）

			//修改前的副本
			Node temp_x = houses[x];
			Node temp_x_fa = houses[temp_x.fa];

			//把x挂在y下
			houses[x].fa = y;
			houses[x].disToFa = z;

			while (temp_x_fa.fa) {

				houses[temp_x.fa].disToFa = temp_x.disToFa;
				houses[temp_x.fa].fa = x;

				x = temp_x.fa;
				temp_x = houses[x];
				temp_x_fa = houses[temp_x.fa];

			}

		}

	}
}

int cal(int x, int y) {
//先从x开始一直追溯到根节点，沿途标记所有经过的节点（visited数组两个作用，一是用来标记是否访问过，二是用来记录从x节点出发以后走过的距离）
	int sum_x = 0;
	visited[x] = -1;

	sum_x += houses[x].disToFa;
	x = houses[x].fa;

	while (houses[x].fa) {//当未到树顶时
		visited[x] = sum_x;
		sum_x += houses[x].disToFa;
		x = houses[x].fa;
	}

	//此时x是树顶
	if (visited[x] != -1) {
		visited[x] = sum_x;
	}

	//接下来从y开始向上追溯
	int sum_y = 0;
	while (!visited[y]) {
		sum_y += houses[y].disToFa;
		y = houses[y].fa;
	}

	//根据之前留下的-1判断原始的x是否为y的父元素
	if (visited[y] == -1) {//这种情况表明y向上追溯的过程中遇到了x
		return sum_y;//直接返回y向上追溯到x的距离
	} else {//这种情况表明y追溯到了x的某一个祖先元素
		return sum_y + visited[y];//返回y向上追溯到x的距离 + 从x到这个祖先元素的距离
	}

}

int main(int argc, char const *argv[])
{
	int T, n, m, cp_n, a1, a2, a3;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);

		cp_n = n;

		memset(houses, 0, sizeof(Node) * (n + 1));

		while (--n) {
			scanf("%d%d%d", &a1, &a2, &a3);

			add(a1, a2, a3);

		}

		while (m--) {
			scanf("%d%d", &a1, &a2);

			memset(visited, 0, sizeof(int) * (cp_n + 1));//每处理一个问题前刷新一次

			printf("%d\n", cal(a1, a2));

		}

	}

	return 0;
}

解法2：

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>

using namespace std;

//31ms
//Tarjan

//孩子链表示法(链表)
//这里的孩子不一定是子节点，可能还有一个父节点，但是可以用visited数组来区别
//随便选取一个hand作为根节点，就可以建成一棵树

int hand[40005];//保存第x号房子的所有孩子节点链表的起始节点编号

struct Node//链表节点
{
	int distance;//权值
	int to;
	int next;//保存下一个Node的位置（并非指房子的编号，是节点的编号），即孩子组成的链表中的下一个节点的位置
};

Node nodes[40005 << 1];//需要两倍空间
int pos;//pos为nodes的当前可用的Node的位置编号
int disToRoot[40005];//代表到根节点的距离
// 结果 = disToRoot[x] + disToRoot[y] - 2 * disToRoot[LCA(x, y)]

//Tarjan
int fa[40005];
int visited[40005];
int qhand[40005];
Node ques[40005 << 1];
int qpos;

void addToTree(int x, int y, int z) {//表示为x号房子添加一个子节点 y ,距离为z
	//为pos号节点写入数据
	nodes[pos].to = y;
	nodes[pos].distance = z;
	nodes[pos].next = hand[x];
	hand[x] = pos;

	pos++;//当前可用的节点编号+1
}

void addToQue(int x, int y) {
	ques[qpos].to = y;
	ques[qpos].distance = 0;
	ques[qpos].next = qhand[x];
	qhand[x] = qpos;

	qpos++;
}

int tarjanFind(int x) {//并查集查找（非递归压缩路径）
	int cp_x = x;
	while (fa[x] != x) {
		x = fa[x];
	}

	while (fa[cp_x] != cp_x) {
		cp_x = fa[cp_x];
		fa[cp_x] = x;
	}

	return x;
}

void tarjan(int which) {

	visited[which] = 1;

	fa[which] = which;

	int childPos = hand[which];

	while (childPos) {

		if (visited[nodes[childPos].to]) {//跳过父元素
			childPos = nodes[childPos].next;
			continue;
		}

		disToRoot[nodes[childPos].to] = disToRoot[which] + nodes[childPos].distance;//写入到根节点的距离
		tarjan(nodes[childPos].to);

		fa[nodes[childPos].to] = which;

		childPos = nodes[childPos].next;

	}

//处理询问
	int quesPos = qhand[which];

	while (quesPos) {

		if (visited[ques[quesPos].to]) {
			ques[quesPos].distance = disToRoot[which] + disToRoot[ques[quesPos].to] - 2 * disToRoot[tarjanFind(ques[quesPos].to)];
		}

		quesPos = ques[quesPos].next;
	}

}

int main(int argc, char const *argv[])
{
	int T, n, m, a1, a2, a3;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);

		memset(hand, 0, sizeof(int) * (n + 1));
		memset(qhand, 0, sizeof(int) * (n + 1));
		memset(visited, 0, sizeof(int) * (n + 1));

		pos = 1;

		while (--n) {
			scanf("%d%d%d", &a1, &a2, &a3);

			addToTree(a1, a2, a3);
			addToTree(a2, a1, a3);

		}

		qpos = 1;

		//离线算法（先收集所有问题，然后统一遍历）
		while (m--) {

			scanf("%d%d", &a1, &a2);

			//建立链表的方法和上面建树的方法类似
			addToQue(a1, a2);
			addToQue(a2, a1);

		}

		disToRoot[1] = 0;
		tarjan(1);

		for (int i = 1; i < qpos; i += 2) {
			printf("%d\n", ques[i].distance ? ques[i].distance : ques[i + 1].distance);
		}

	}

	return 0;
}

解法3：

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>

using namespace std;

//46ms
//转化为RMQ问题_ST
//在线算法

//孩子链表示法(链表)
//这里的孩子不一定是子节点，可能还有一个父节点，但是可以用visited数组来区别
//随便选取一个hand作为根节点，就可以建成一棵树

int hand[40005];//保存第x号房子的所有孩子节点链表的起始节点编号

struct Node//链表节点
{
	int distance;//权值
	int to;
	int next;//保存下一个Node的位置（并非指房子的编号，是节点的编号），即孩子组成的链表中的下一个节点的位置
};

Node nodes[40005 << 1];//需要两倍空间

int pos;//pos为nodes的当前可用的Node的位置编号
int disToRoot[40005];//代表到根节点的距离
// 结果 = disToRoot[x] + disToRoot[y] - 2 * disToRoot[LCA(x, y)]

//RMQ
int rmq_which[40005 << 1];//RMQ数组长度约为节点数的两倍（实际上是2n-1），储存欧拉环游经过的所有节点号
int rmq_deep[40005 << 1];//储存环游中节点的深度
int rmq_first[40005];//储存循环中 x 号节点（房子）第一次出现的位置
int rmq_pos;

int visited[40005];//排除父节点

//ST
int st[40005 << 1][18]; //2的17次方大于 40005
// st[x][y] = 代表rmq_deep数组中从x开始持续长为（2的y次方）长的区间范围内的最小deep 的位置

void addToTree(int x, int y, int z) {//表示为x号房子添加一个子节点 y ,距离为z
	//为pos号节点写入数据
	nodes[pos].to = y;
	nodes[pos].distance = z;
	nodes[pos].next = hand[x];
	hand[x] = pos;

	pos++;//当前可用的节点编号+1
}

/**
* rmq函数用欧拉环游生成了rmq_which 和 rmq_deep 和 rmq_first 和 disToRoot 四个数组
*/
void rmq(int which, int deep) {
	visited[which] = 1;

	rmq_which[rmq_pos] = which;
	rmq_deep[rmq_pos] = deep;
	rmq_first[which] = rmq_pos;
	rmq_pos++;

	int childPos = hand[which];

	while (childPos) {
		if (visited[nodes[childPos].to]) {
			childPos = nodes[childPos].next;
			continue;
		}

		disToRoot[nodes[childPos].to] = disToRoot[which] + nodes[childPos].distance;

		rmq(nodes[childPos].to, deep + 1);

		rmq_which[rmq_pos] = which;
		rmq_deep[rmq_pos] = deep;
		rmq_pos++;

		childPos = nodes[childPos].next;

	}

}

//初始化st数组
void init_st() {
	for (int i = 0; i < rmq_pos; ++i) {//根据st的定义，y为0时，st[i][0] = i;
		st[i][0] = i;
	}

	for (int y = 1 ; y < 18; ++y) {
		for (int i = 0; i + (1 << y) - 1 < rmq_pos; ++i) {
			st[i][y] =	rmq_deep[st[i][y - 1]] < rmq_deep[st[i + (1 << (y - 1))][y - 1]] ? st[i][y - 1] : st[i + (1 << (y - 1))][y - 1];
		}
	}
}

// 返回rmq_deep数组区间[x, y]之间的最小元素的位置
int min_st(int x, int y) {

	if (x > y) {//保证输入的x <= y;若不满足，则反过来
		return min_st(y, x);
	}

	for (int i = 17; i >= 0; --i) {
		if (x + (1 << i) - 1 > y) {
			continue;
		}

		if (x + (1 << i) - 1 == y) {
			return st[x][i];
		} else {
			int temp = min_st(x + (1 << i), y);
			return rmq_deep[st[x][i]] < rmq_deep[temp] ? st[x][i] : temp;
		}
	}

	return 0;
}

int main(int argc, char const *argv[])
{
	int T, n, m, a1, a2, a3, first = 1;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);

		memset(hand, 0, sizeof(int) * (n + 1));
		memset(visited, 0, sizeof(int) * (n + 1));

		pos = 1;

		while (--n) {
			scanf("%d%d%d", &a1, &a2, &a3);

			addToTree(a1, a2, a3);
			addToTree(a2, a1, a3);

		}

		disToRoot[1] = 0;

		//在线算法（逐个回答问题）

		rmq_pos = 0;

		rmq(1, 1);

		init_st();

		if (first) {
			first = 0;
		} else {
			printf("\n");
		}

		// for (int i = 0; i < rmq_pos; i++) {
		// 	printf("%d ", rmq_which[i]);
		// }
		// printf("\n");
		// for (int i = 0; i < rmq_pos; i++) {
		// 	printf("%d ", rmq_deep[i]);
		// }
		// printf("\n");
		// for (int i = 1; i <= 6; i++) {
		// 	printf("%d ", rmq_first[i]);
		// }
		// printf("\n");

		// for (int x = 0; x < 18; x++) {
		// 	for (int i = 0; i < rmq_pos; i++) {
		// 		printf("%d ", st[i][x]);
		// 	}
		// 	printf("\n");
		// }

		while (m--) {

			scanf("%d%d", &a1, &a2);

			printf("%d\n", disToRoot[a1] + disToRoot[a2] - 2 * disToRoot[rmq_which[min_st(rmq_first[a1], rmq_first[a2])]]);

		}

	}

	return 0;
}

解法4：

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>

using namespace std;

//31ms
//转化为RMQ问题_Segment_Tree

/**
*	注意线段树需要4倍空间
*	注意线段树需要4倍空间
*	注意线段树需要4倍空间
*/

//在线算法

//孩子链表示法(链表)
//这里的孩子不一定是子节点，可能还有一个父节点，但是可以用visited数组来区别
//随便选取一个hand作为根节点，就可以建成一棵树

int hand[40005];//保存第x号房子的所有孩子节点链表的起始节点编号

struct Node//链表节点
{
	int distance;//权值
	int to;
	int next;//保存下一个Node的位置（并非指房子的编号，是节点的编号），即孩子组成的链表中的下一个节点的位置
};

Node nodes[40005 << 1];//需要两倍空间

int pos;//pos为nodes的当前可用的Node的位置编号
int disToRoot[40005];//代表到根节点的距离
// 结果 = disToRoot[x] + disToRoot[y] - 2 * disToRoot[LCA(x, y)]

//RMQ
int rmq_which[40005 << 1];//RMQ数组长度约为节点数的两倍（实际上是2n-1），储存欧拉环游经过的所有节点号
int rmq_deep[40005 << 1];//储存环游中节点的深度
int rmq_first[40005];//储存循环中 x 号节点（房子）第一次出现的位置
int rmq_pos;

int visited[40005];//排除父节点

//Segment_Tree
struct SegNode
{
	int left;
	int right;
	int minPos;//储存[left, right]区间内deep最小值所处的位置
};

//线段树需要原基础数组长度四倍的空间
SegNode segs[40005 << 3];//从1开始

void addToTree(int x, int y, int z) {//表示为x号房子添加一个子节点 y ,距离为z
	//为pos号节点写入数据
	nodes[pos].to = y;
	nodes[pos].distance = z;
	nodes[pos].next = hand[x];
	hand[x] = pos;

	pos++;//当前可用的节点编号+1
}

/**
* rmq函数用欧拉环游生成了rmq_which 和 rmq_deep 和 rmq_first 和 disToRoot 四个数组
*/
void rmq(int which, int deep) {
	visited[which] = 1;

	rmq_which[rmq_pos] = which;
	rmq_deep[rmq_pos] = deep;
	rmq_first[which] = rmq_pos;
	rmq_pos++;

	int childPos = hand[which];

	while (childPos) {
		if (visited[nodes[childPos].to]) {
			childPos = nodes[childPos].next;
			continue;
		}

		disToRoot[nodes[childPos].to] = disToRoot[which] + nodes[childPos].distance;

		rmq(nodes[childPos].to, deep + 1);

		rmq_which[rmq_pos] = which;
		rmq_deep[rmq_pos] = deep;
		rmq_pos++;

		childPos = nodes[childPos].next;

	}

}

//初始化segment数组
void build_seg(int spos, int left, int right) {
	// printf("spos -> %d\n", spos);
	segs[spos].left = left;
	segs[spos].right = right;

	if (left == right) {
		segs[spos].minPos = left;
		return;
	}

	build_seg(spos << 1, left, (left + right) / 2);
	build_seg((spos << 1) | 1, ((left + right) / 2) + 1, right);

	segs[spos].minPos = rmq_deep[segs[spos << 1].minPos] < rmq_deep[segs[(spos << 1) | 1].minPos] ? segs[spos << 1].minPos : segs[(spos << 1) | 1].minPos;

}

// 返回rmq_deep数组区间[x, y]之间的最小元素的位置
int min_seg(int pos, int x, int y) {
	if (x == segs[pos].left && y == segs[pos].right) {
		return segs[pos].minPos;
	} else if (y <= ((segs[pos].left + segs[pos].right) / 2)) {
		return min_seg(pos << 1, x, y);
	} else if (x > ((segs[pos].left + segs[pos].right) / 2)) {
		return min_seg((pos << 1) | 1, x, y);
	} else {
		int temp1, temp2;
		temp1 = min_seg(pos << 1, x, (segs[pos].left + segs[pos].right) / 2);
		temp2 = min_seg((pos << 1) | 1, ((segs[pos].left + segs[pos].right) / 2) + 1, y);

		return rmq_deep[temp1] < rmq_deep[temp2] ? temp1 : temp2;
	}
}

int main(int argc, char const *argv[])
{
	int T, n, m, a1, a2, a3, first = 1;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);

		memset(hand, 0, sizeof(int) * (n + 1));
		memset(visited, 0, sizeof(int) * (n + 1));

		pos = 1;

		while (--n) {
			scanf("%d%d%d", &a1, &a2, &a3);

			addToTree(a1, a2, a3);
			addToTree(a2, a1, a3);

		}

		disToRoot[1] = 0;

		//在线算法（逐个回答问题）

		rmq_pos = 0;

		rmq(1, 1);

		// printf("rmq_pos -> %d\n", rmq_pos);

		build_seg(1, 0, rmq_pos - 1);

		if (first) {//好像没有空行也能过
			first = 0;
		} else {
			printf("\n");
		}

		// for (int i = 0; i < rmq_pos; i++) {
		// 	printf("%d ", rmq_which[i]);
		// }
		// printf("\n");
		// for (int i = 0; i < rmq_pos; i++) {
		// 	printf("%d ", rmq_deep[i]);
		// }
		// printf("\n");
		// for (int i = 1; i <= 6; i++) {
		// 	printf("%d ", rmq_first[i]);
		// }
		// printf("\n");

		while (m--) {

			scanf("%d%d", &a1, &a2);

			if (rmq_first[a1] < rmq_first[a2]) {

				printf("%d\n", disToRoot[a1] + disToRoot[a2] - 2 * disToRoot[rmq_which[min_seg(1, rmq_first[a1], rmq_first[a2])]]);
			} else {
				printf("%d\n", disToRoot[a1] + disToRoot[a2] - 2 * disToRoot[rmq_which[min_seg(1, rmq_first[a2], rmq_first[a1])]]);
			}

		}

	}

	return 0;
}