hdu 2586 How far away LCA dfs+RMQ

缘起

【1】中已经给出了LCA问题的dfs转RMQ的解法. 可以在 O(nlogn)~O(1)解决问题. 自然要找个板题测一下板子的性能. 于是找到了 hdu 2586

分析

题意很裸

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
村庄里面有n个房子(编号从1到n)，房子之间有双向道路连接. 人们对房子之间的最短距离很感兴趣. 其实这种问题很难回答，但是幸运的是答案对于这个村庄总是唯一的, 这是因为村庄中任何2幢房子之间存在唯一的道路而且不存在环. 你的任务是写一个程序回答这些问题

输入
T个样例(T<=10). 对于每个case，第一行是n和m, n是房子数量(2<=n<=40000)，m是询问数量(1<=m<=200).然后n-1行，每行三个数字i,j,k 表示从i到j的路径长k（1<=k<=40000）. 然后m行，每行两个数字i,j 询问i和j之间的距离.

输出
对每个样例，输出m行，每行表示询问的答案

样例输入
2
3 2
1 2 10
3 1 15
1 2
2 3

2 2
1 2 100
1 2
2 1

样例输出
10
25
100
100

此题”村庄中任何2幢房子之间存在唯一的道路而且不存在环” 就表明这是一棵树. 但是树的根我们不知道, 也没必要知道——任何一个节点都可以做根. 然后在dfs的过程中将树上的各点到根的距离保存下来, 设为 dist数组, 则最后的结果就是

1
u和v的距离=dist[u]+dist[v]-2*dist[LCA(u,v)]

见下图

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
//#include "stdafx.h"
#include <stdio.h>
#include <vector>
//#define LOCAL

using namespace std;

const int MAX_N = 40005;

typedef struct Edge
{
	int end, dis; // 终点和弧长
	Edge(int end, int dis):end(end),dis(dis){}
};

vector<Edge> tree[MAX_N];
int e[MAX_N<<1], d[MAX_N<<1], f[MAX_N], root, indeg[MAX_N],x, st[20][MAX_N<<2],n,m, dis[MAX_N]; // dis[i]表示编号为i的节点距离root的距离
typedef vector<Edge>::iterator it;

void init()
{
	memset(indeg, 0, sizeof(indeg)); // 入度归零
	x = 0; // 时间戳归零
	for (int i = 1; i<=n; i++) tree[i].clear(); // 树归零
	for (int i = 0,j,k,l;i<n-1;i++)
	{
		scanf("%d%d%d", &j,&k, &l);
		tree[j].push_back(Edge(k,l));
		indeg[k]++;
	}
	for (int i = 1; i<=n;i++)
	{
		if (!indeg[i])
		{
			root = i;
			break;
		}
	}
}

void dfs(int i, int depth, int distance)
{
	e[++x] = i,d[x] = depth,f[i] = x;
	dis[i] = distance;
	for (it p = tree[i].begin(); p!=tree[i].end(); p++) 
	{
		dfs(p->end, depth+1, distance+p->dis);
		e[++x] = i;
		d[x] = depth;
	}
}

void build()
{
	for (int i = 1;i<=(n<<1)-1;i++) st[0][i] = i;
	int k = 1;
	while((1<<k)<((n<<1)-1))
	{
		for (int i = 1; i<=(n<<1)-1; i++) st[k][i] =i+(1<<(k-1))>=(n<<1)?st[k-1][i]:(d[st[k-1][i]]<d[st[k-1][i+(1<<(k-1))]]?st[k-1][i]:st[k-1][i+(1<<(k-1))]);
		k++;
	}
}

int rmq(int i, int j)
{
	int k = 0;
	while((1<<k)<=j-i+1)k++;
	return d[st[k-1][i]]<d[st[k-1][j-(1<<(k-1))+1]]?st[k-1][i]:st[k-1][j-(1<<(k-1))+1];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	int t;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &n,&m);
		init();
		dfs(root, 0, 0);
		build();
		while(m--)
		{
			int u,v;
			scanf("%d%d", &u, &v);
			int x = f[u], y = f[v];
			if (x>y) swap(x,y);
			printf("%d\n", dis[u]+dis[v]-2*dis[e[rmq(x,y)]]);
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 78ms
Memory 10600kB
Length 1730
Lang C++
Submitted 2019-07-17 06:40:20
RemoteRunId 29719321

参考

【1】https://yfsyfs.github.io/2019/07/15/LCA/