Kruskal重构树

Posted on | In |
Words count in article: 1.3k | Reading time ≈ 5

看到NOI2018Day1T1要用到Kruskal重构树，蒟蒻就学习了一下。

看到这个名字，大家一定会想起Kruskal，对，没错，可以说这个重构树就是稍微改动了一点的Kruskal。它的基本思想就是将一个图的最小生成树中的边转成点建一棵新树，边权也就转换成了点权。

做法依然是每次取出一条最短的边，如果它所连接的两个节点不在一个集合里，那么就加入一个新的节点，它的两个儿子节点为所连节点的最远祖先，并将这两个节点以及新点合并。

可知这样新建的树共有$2 \times n-1$个节点以及$2 \times n-2$条边，它还满足以下几个性质：

  1. 二叉树
  2. 原树与新树两点间路径上边权（点权）值相等
  3. 子节点的边权小于等于父亲节点
  4. 原树中两点之间路径上边权的最大值等于新树上两点的LCA的点权

如果你对建树过程依然不能理解，那么我们来看一道例题：BZOJ 3732 Network

可以看到原图是这样的：

然后它对应的Kruskal重构树就长这样（圆点为原图中的点，方点为新加入的点，绿框内数为点权）：

然而这两张图并不能让你理解它是如何建成的，所以我将会分步描述建树过程

  1. 按边权从小到大排序
  2. 当前最小边为4 6 2，发现4,6并不在一个集合中，加入7号点，点权为2，并与4,6分别连边，将4,6加入7的集合中
  3. 当前最小边为3 4 3，发现3,4也不在一个集合中，加入8号点，点权为3，此时3号点的最远祖先为3，4号点的最远祖先为7，于是在8,7、8,3之间连边，并将3,7加入8的集合中
  4. 当前最小边为2 3 4，发现2,3还不在一个集合中，加入9号点，点权为4，此时2号点的最远祖先为2，3号点的最远祖先为8，于是在9,8、9,2之间连边，并将2,8加入9的集合中
  5. 当前最小边为1 2 5，发现1,2依然不在一个集合中，加入10号点，点权为5，此时1号点的最远祖先为1，2号点的最远祖先为9，于是在10,9、10,1之间连边，并将1,9加入10的集合中
  6. 当前最小边为2 5 7，发现2,5居然也不在一个集合中，加入11号点，点权为7，此时2号点的最远祖先为10，5号点的最远祖先为5，于是在11,10、11,5之间连边，并将10,5加入11的集合中
  7. 当前最小边为1 4 8，然而1,4在同一个集合里，不做任何操作
  8. 已经没有边了，重构树宣告建成

这样剩下的就只有求LCA的过程了，瞎yy两下代码就出来了，然而还是把代码放一下（树剖求LCA）：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e5 + 110;
const int inf = 0x7fffffff;
const int MAXN = 110;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, m, k, cnt, tot;
int fa[N], head[N], w[N], dfn[N], top[N], dep[N], son[N], siz[N];

struct edge
{
	int fr, to, weight;
};
struct Edge
{
	int to, nxt;
};
edge e[N];
Edge E[N];
il bool cmp(edge x, edge y)
{
	return x.weight < y.weight;
}

il int findf(int x)
{
	if (fa[x] == x)
		return x;
	return fa[x] = findf(fa[x]);
}

il void add_edge(int u, int v)
{
	E[++tot] = (Edge){v, head[u]};
	head[u] = tot;
	E[++tot] = (Edge){u, head[v]};
	head[v] = tot;
}
il void Ex_Kruskal()
{
	cnt = n;
	for (ri i = 1; i <= m; i++)
	{
		int f1 = findf(e[i].fr);
		int f2 = findf(e[i].to);
		if (f1 != f2)
		{
			cnt++;
			add_edge(cnt, f1);
			add_edge(cnt, f2);
			fa[f1] = cnt, fa[f2] = cnt;
			w[cnt] = e[i].weight;
		}
	}
}

il void DFS(int x)
{
	dfn[++dfn[0]] = x;
	siz[x]++;
	for (ri i = head[x]; i; i = E[i].nxt)
	{
		int v = E[i].to;
		if (v == fa[x])
			continue;
		fa[v] = x;
		dep[v] = dep[x] + 1;
		DFS(v);
		siz[x] += siz[v];
		if (siz[v] > siz[son[x]])
			son[x] = v;
	}
	if (!son[x])
		son[x] = x;
}
il int LCA(int x, int y)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	return x;
}

int main()
{
	n=read(), m=read(), k=read();
	for (ri i = 1; i <= m; i++)
		e[i].fr = read(), e[i].to = read(), e[i].weight = read();
	sort(e + 1, e + 1 + m, cmp);
	for (ri i = 1; i <= n; i++)
		fa[i] = i, fa[i + n] = i + n;
	Ex_Kruskal();
	int rt = findf(1);
	memset(fa, 0, sizeof(fa));
	DFS(rt);
	for (ri i = 1; i <= dfn[0]; i++)
		top[dfn[i]] = (dfn[i] == son[fa[dfn[i]]]) ? top[fa[dfn[i]]] : dfn[i];
	for (ri i = 1; i <= k; i++)
	{
		int x = read(), y = read();
		printf("%d\n", w[LCA(x, y)]);
	}
	return 0;
}

0%