hdu 2586 How far away LCA Tarjan解法

缘起

【1】中已经给了 hdu 2586 的LCA用dfs转RMQ的解法. 本文给出LCA问题的tarjan解法.

分析

tarjan算法求解LCA的过程其实比【1】中dfs转RMQ要好写很多. 虽然后者的那个转换极为精妙. 但是tarjan算法是 dfs+并查集. 速度更快. tarjan 算法的思想是这样的.

dfs整棵树, 每次搜索一个节点的时候, 都将记录它的儿子节点（注意，仅仅是儿子节点, 不包括孙子节点）的并查集意义上的father是自己. 即

从x进入搜索, 记录f[y]=f[z]=x. f是并查集找爹数组（参见【2】）. 然后

上图中, dfs搜完以x为根的子树之后, 就可以开始回答LCA(x, i) 这个问题. 其中i是在x之前搜完的. 因为i在x之前搜完, 所以i一定在树结构中较x偏左（或者i是x的儿孙子节点）. 那么怎么回答这个询问呢? 只需要求i在并查集意义上的父亲即可. 因为注意下面的算法实现——只要dfs没有从一个节点x退出去, 则f[x]就一直是x自身的（不会变成x的父辈节点）. 这个特性就能保证求出LCA. 不然的话, 如果提前设置了f[x]的话，则x的子节点之间的LCA就可能跑到x的祖先去，就得出了错误的答案了

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

const int MAXN = 40005;

int n,m,f[MAXN],indeg[MAXN],root,d[MAXN],ans[205]; // f是并查集数组,d是各个节点到根节点的距离, ans是答案
bool isVisited[MAXN]; // 是否访问数组, true表示访问过了,false表示没有
struct Query
{
	int end, index; // index是第几个问题, 这是离线算法比在线算法麻烦的地方
	Query(int end, int index):end(end),index(index){}
};
vector<Query> query[MAXN]; // 询问
struct Edge
{
	int end, dis; // 终点，以及弧的长度
	Edge(int end, int dis):end(end),dis(dis){}
};
vector<Edge> tree[MAXN];

int getf(int i){return i==f[i]?i:f[i]=getf(f[i]);} // 并查集找爹

typedef vector<Edge>::iterator ite;
typedef vector<Query>::iterator itq;

void tarjan(int x) // x是当前节点
{
	for (ite i = tree[x].begin(); i!=tree[x].end(); i++)
	{
		d[i->end] = d[x]+i->dis; //计算儿子节点i到根节点的距离,其实就LCA问题而言, 这不是必要的
		tarjan(i->end); // 这就应验了文章中说的, 要一直搜完所有子节点才设置并查集数组
		f[i->end] = x; // x的儿子(不包含孙子)节点i->end的并查集意义上的父亲是x
	}
	isVisited[x] = true; // x搜完了
	for (itq i = query[x].begin(); i!=query[x].end(); i++) if (isVisited[i->end]) ans[i->index] = d[x]+d[i->end]-(d[getf(i->end)]<<1);  // x既然搜完了, 就可以开始回答关于x的询问了,如果  *i也搜完了,第i->index个询问的LCA答案就是getf(i->end), 当然, 距离不是这个,距离还要进一步
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif // LOCAL

	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n, &m);
		for (int i = 1;i<=n;i++) tree[i].clear(),query[i].clear(); // 清空树结构和询问
		for (int i = 1;i<=n;i++) f[i]=i; // 初始化并查集数组
		memset(indeg, 0, sizeof(indeg));
		memset(isVisited, 0, sizeof(isVisited));
		for (int i = 1,j,k,l; i<n;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;
				d[root] = 0;
				break;
			}
		} // 确定根节点
		for (int i =1,j,k;i<=m;i++)
		{
			scanf("%d%d", &j,&k); // 输入询问, 保存询问, 这样先兜着, 所以LCA的tarjan算法是离线算法
			query[j].push_back(Query(k,i));
			query[k].push_back(Query(j,i)); // 两个都要输入, 因为你不晓得先搜到谁
		}
		tarjan(root);
		for (int i = 1;i<=m;i++) printf("%d\n", ans[i]); // 一口气回答m个问题
	}

	return 0;
}

ac结果(可见比dfs+RMQ(78ms)要优秀一点)

Status Accepted
Time 31ms
Memory 4764kB
Length 2044
Lang C++
Submitted 2019-07-19 08:56:10
Shared
RemoteRunId 29762317

参考

【1】https://yfsyfs.github.io/2019/07/16/hdu-2586-How-far-away-LCA-dfs-RMQ/

【2】https://yfsyfs.github.io/2019/05/24/%E5%B9%B6%E6%9F%A5%E9%9B%86%E6%A8%A1%E6%9D%BF/