4 分钟 读完 (大约 641 个字)

边分治

边分治用来解决一些点分治中一些解决不了的问题。

比如说点分治时有很多棵子树，合并这些信息时不能保证时间复杂度。

而边分治时最多只会有两棵子树，就可以很好地解决问题。

算法与点分治大致相同，就是找到一条边使得删去这条边后最大的那棵子树的大小最小。

但这个算法在菊花图时时间复杂度会退化成$O(n^2)$，因此需要将原树转换为一棵二叉树，这样每个点度数最多为$3$，分治后子树大小最多为原树的$\frac{2}{3}$，就不会出现刚刚那样的问题了。

但边分治还有一个限制条件，那就是后来加进去的边对答案不会产生影响

我的多叉树转二叉树的代码，（显然最后的点数nn最多只有$2n$）:

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
void dfs1(int u, int father)
{
	for (int i = head[u]; i; i = nextx[i])
	{
		int v = vet[i];
		if (v != father)
		{
			dfs1(v, u);
			vec[u].push_back(v);
		}
	}
}

int main()
{
	dfs1(1, 0);

	int nn = n;
	edgenum = 1;
	memset(head, 0, sizeof(head));
	for (int i = 1; i <= n; i++)
	{
		if ((int)vec[i].size() < 2)
		{
			for (int j = 0; j < (int)vec[i].size(); j++)
			{
				add(i, vec[i][j], );
				add(vec[i][j], i, );
			}
		}
		else
		{
			int pre = i;
			for (int j = 0; j < (int)vec[i].size() - 2; j++)
			{
				add(pre, vec[i][j], );
				add(vec[i][j], pre, );
				nn++;
				x[nn] = x[i];
				add(pre, nn, );
				add(nn, pre, );
				pre = nn;
			}
			add(pre, vec[i][vec[i].size() - 2], );
			add(vec[i][vec[i].size() - 2], pre, );
			add(pre, vec[i][vec[i].size() - 1], );
			add(vec[i][vec[i].size() - 1], pre, );
		}
	}
}

当然可以更简单粗暴一些，代价就是点数会稍微多一点点，但还是不会超过$2n$:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
	dfs1(1, 0);

	int nn = n;
	edgenum = 1;
	memset(head, 0, sizeof(head));
	for (int u = 1; u <= n; u++)
	{
		int pre = u;
		for (int i = 0; i < (int)vec[u].size(); i++)
		{
			add(pre, vec[u][i], );
			add(vec[u][i], pre, );
			nn++;
			add(pre, nn, );
			add(nn, pre, );
			pre = nn;
		}
	}
}

其他的部分和点分治差不多。

这里是找根的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void getroot(int u, int father, int S)
{
	size[u] = 1;
	for (int i = head[u]; i; i = nextx[i])
	{
		int v = vet[i];
		if (v != father && ! vis[i])
		{
			getroot(v, u, S);
			f[i >> 1] = std::max(size[v], S - size[v]);
			if (f[i >> 1] < f[root >> 1])
			{
				root = i;
			}
			size[u] += size[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
void dfs(int u, int father, int cas, )
{
	size[u] = 1;
	for (int i = head[u]; i; i = nextx[i])
	{
		int v = vet[i];
		if (v != father && ! vis[i])
		{
			dfs(v, u, cas, );
			size[u] += size[v];
		}
	}
	//
}

void solve(int rt, int father, int S)
{
	if (! rt)
	{
		return;
	}
	vis[rt] = vis[rt ^ 1] = 1;
	for (int i = 0; i < 2; i++)
	{
		dfs(vet[rt ^ i], 0, i, );
	}
	//solve
	for (int i = 0; i < 2; i++)
	{
		root = 0;
		int ss = size[vet[rt ^ i]];
		getroot(vet[rt ^ i], 0, ss);
		solve(root, 0, ss);
	}
}
# 分治, 树, 树分治, 算法, 边分治
64位模数乘法
CDQ分治与点分治的碰撞
关注我

目录

标签云

CDQ分治 FFT与NTT 二项式系数 关于本站 几何 分治 反演 后缀自动机 微积分 数学 数论 树 树分治 概率 点分治 算法 线性基 组合数学 自动机 计算几何 边分治 黑科技

归档

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×