代码编织梦想

关于点分治的常见写法及时间复杂度

0x01 概述

点分治是一种基于树的重心,统计树上路径的优秀算法。将树上的路径分为经过树的重心和不经过树的重心两种,同时利用树的重心性质,使得递归深度不超过 l o g n logn logn次。

总时间复杂取决于每次递归统计答案的时间复杂度。若每次统计是 O ( n ) O(n) O(n)的,那么总时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)。若统计的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)的,那么总时间复杂度为 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)。这两种时间复杂度均为可也接受的。

0x02 写法

点分治有2种写法:

  1. 对于某个重心 u u u,统计以 u u u为根的所有路径,然后计算出所有组合情况。递归子树时,首先删除全部在一颗子树的路径,然后再进入子树递归求解。这样可以保证路径全部合法且不重不漏。

  2. 对于某个重心 u u u,先进入子树 v 1 v_1 v1,求解出 u u u到子树 v 1 v_1 v1所有节点的路径,然后进入子树 v 2 v_2 v2,进入时先统计答案,然后再统计相关值……每次进入新的子树时,先统计答案,这样每次计算的路径一定是和之前统计过子树的相连而成的,没有不合法的答案,所以不用删除。最后,依次递归进子树,找出重心递归求解。

点分治

图1表示直接统计以重心为根的子树上的路径,递归进入子树之前,首先删除子树中的不合法路径。

图2表示按子树依次递归进入,进入后先统计答案,然后再统计相关值。统计答案是利用到了先前子树的信息。

一般地,写法2常数更小。

0x03 分析

下面来探讨两种写法的时间复杂度。

两种写法首先在“分治”过程中,每次都是中心划分,树的层数(递归深度)是严格 l o g n logn logn的。也就是说总体框架上都是带一个log。

对当前层答案统计、每次问题规模减半,可看作 T ( n ) = T ( n / 2 ) + O ( n ) T(n)=T(n/2)+O(n) T(n)=T(n/2)+O(n)

问题就出在两种写法在”统计计算”这块的时间。

对于写法1,一般会将所有子树的dis全部排个序或者二分,这样就躲不掉的一个log的时间,总时间复杂度是 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

对于写法2,采用的桶来记录前面子树的dis信息,或占用一定量的空间(当然在范围允许的情况下),或用map增加一个log的时间,总时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn) O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

下给出两份题目的代码,供读者阅读体会:

Luogu P4178 Tree

//写法1实现
#include <bits/stdc++.h>
using namespace std;
inline int read() {
	int x = 0; bool f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
const int MAXN = 4e4 + 6;
int n, k, root, cnte, cntd, ans;
int mxp[MAXN], vis[MAXN], sz[MAXN], hd[MAXN], dis[MAXN];
struct tEdge { int to, nxt, wei; } e[MAXN << 1];
inline void link(int u, int v, int w) {
	e[++cnte] = {v, hd[u], w};
	hd[u] = cnte;
}
void getroot(int u, int p, int n) {
	sz[u] = 1; mxp[u] = 0;
	for (int i = hd[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v == p || vis[v]) continue;
		getroot(v, u, n);
		sz[u] += sz[v];
		mxp[u] = max(mxp[u], sz[v]);
	}
	mxp[u] = max(mxp[u], n - sz[u]);
	if (mxp[u] < mxp[root]) root = u;
	// mxp[u] < mxp[root]    ...YES
	// mxp[u] <= n / 2       ...NO
}
void getdis(int u, int d, int p) {
	dis[++cntd] = d;
	for (int i = hd[u]; i; i = e[i].nxt) {
		int v = e[i].to, w = e[i].wei;
		if (v == p || vis[v]) continue;
		getdis(v, d + w, u);
	}
}
int calc(int u, int d) {
	cntd = 0; getdis(u, d, 0);
	sort(dis + 1, dis + cntd + 1);
	int sum = 0;
	for (int l = 1, r = cntd; ; ++l) {
		while (r && dis[l] + dis[r] > k) --r;
		if (r < l) break;
		sum += r - l;
	}
	return sum;
}
void solve(int u) {
	ans += calc(u, 0); vis[u] = 1;
	for (int i = hd[u]; i; i = e[i].nxt) {
		int v = e[i].to, w = e[i].wei;
		if (vis[v]) continue;
		ans -= calc(v, w);
		mxp[root = 0] = INT_MAX;
		getroot(v, 0, sz[v]); solve(root);
	}
}
int main() {
	n = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read(), w = read();
		link(u, v, w); link(v, u, w);
	}
	k = read();
	mxp[root = 0] = INT_MAX;
	getroot(1, 0, n); solve(root);
	printf("%d\n", ans);
	return 0;
}

Luogu P3806【模板】点分治 1

//写法2实现
#include <bits/stdc++.h>
using namespace std;
inline int read() {
	int x = 0; bool f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
const int MAXN = 1e4 + 6, INF = 1e8 + 6;
int n, m, cnte, cntd, root;
int hd[MAXN], sz[MAXN], mxp[MAXN], vis[MAXN];
int q[MAXN], f[MAXN], dic[INF], dis[MAXN], tf[MAXN];
struct tEdge { int to, nxt, wei; } e[MAXN << 1];
inline void link(int u, int v, int w) {
	e[++cnte] = {v, hd[u], w};
	hd[u] = cnte;
}
void getroot(int u, int p, int n) {
	sz[u] = 1, mxp[u] = 0;
	for (int i = hd[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (vis[v] || v == p) continue;
		getroot(v, u, n);
		sz[u] += sz[v];
		mxp[u] = max(mxp[u], sz[v]);
	}
	mxp[u] = max(mxp[u], n - sz[u]);
	if (mxp[u] < mxp[root]) root = u;
}
void getdis(int u, int d, int p) {
	dis[++cntd] = d;
	for (int i = hd[u]; i; i = e[i].nxt) {
		int v = e[i].to, w = e[i].wei;
		if (v == p || vis[v]) continue;
		getdis(v, d + w, u);
	}
}
void calc(int u) {
	int tot = 0;
	for (int i = hd[u]; i; i = e[i].nxt) {
		int v = e[i].to, w = e[i].wei;
		if (vis[v]) continue;
		cntd = 0; getdis(v, w, u);
		for (int j = cntd; j; --j)
			for (int k = 1; k <= m; ++k) {
				if (q[k] < dis[j]) continue;
				f[k] |= dic[q[k] - dis[j]];
			}
		for (int j = cntd; j; --j)
			tf[++tot] = dis[j], dic[dis[j]] = 1;
	}
	for (int i = 1; i <= tot; ++i)
		dic[tf[i]] = 0;
}
void solve(int u) {
	vis[u] = dic[0] = 1; calc(u);
	for (int i = hd[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (vis[v]) continue;
		mxp[root = 0] = INT_MAX;
		getroot(v, 0, sz[v]); solve(root);
	}
}
int main() {
	n = read(), m = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read(), d = read();
		link(u, v, d); link(v, u, d);
	}
	for (int i = 1; i <= m; ++i)
		q[i] = read();
	mxp[root = 0] = INT_MAX;
	getroot(1, 0, n); solve(root);
	for (int i = 1; i <= m; ++i) {
		if (f[i]) puts("AYE");
		else puts("NAY");
	}
	return 0;
}

0x04 相关

点分治常见题型有:

  • 路径和等于或小于等于 k k k的点对(路径条数)。
  • 路径和为某个数的倍数。
  • 路径和为 k k k且路径的边数最少。
  • 路径和 m o d M mod M modM后为某个值。
  • 路径上经过不允许点的个数不超过某个值,且路径和最大。
  • ……

若使用写法1,一般开一个栈,保存路径上的距离等相关信息,排序后利用单调性或者二分找答案。

若使用写法2,则一般处理这些问题时,都是开一个桶 m p i mp_i mpi表示距离为i的相关信息。

0x05 总结

个人感觉写法2更好,效率更高、适用面广、调试与思维难度低。

浅谈分治算法的时间复杂度分析-爱代码爱编程

在我的周围, 发现好多的同事, 朋友, 对一个算法进行时间复杂度分析时,尤其是递归函数进行分析时, 比较吃力, 因此特写这篇文章, 给刚做程序员或者对分治算法(Divide and Conquer),递归(Recursive)算法时间复杂度不太会分析的同学吧. 如有不对之处,共同探讨学习。   关于分治算法是这样定义的: 为解决一个给定的问题, 算法

jzoj 5496 tree(点分治+树形dp)_mogician_evian的博客-爱代码爱编程

Tree * Description* 从前有棵树。 找出 k 个点 A 1 , A 2 , · · · , A k 。 ∑ k−1 使得 i=1 dis(A i A i+1 ) 最小。 Input

bzoj3451 tyvj1953 normal(概率期望+点分治+fft)_coco_t_的博客-爱代码爱编程

Description 某天WJMZBMR学习了一个神奇的算法:树的点分治! 这个算法的核心是这样的: 消耗时间=0 Solve(树 a)  消耗时间 += a 的 大小  如果 a 中 只有 1 个点  

点分治+cdq分治+整体二分全纪录_coco_t_的博客-爱代码爱编程

点分治 点分治讲解 解决树上路径问题 经典例题:点分治(长度小于m的路径计数) 经典例题:点分治(聪聪可可) 经典例题:点分治(多个定值路径计数) 经典例题:点分治(采药) 经典例题:点分治+ST表+优先队列

【算法学习】点分治的两种写法与常见套路总结_pengwill97的博客-爱代码爱编程

概述 点分治是一种基于树的重心,统计树上路径的优秀算法。将树上的路径分为经过树的重心和不经过树的重心两种,同时利用树的重心性质,使得递归深度不超过 logn l

七种内部排序 实现及时间复杂度分析-爱代码爱编程

排序分类 排序分为内部排序和外部排序两种 内部排序 内部排序通常为常见的七种算法,本实验要求掌握选择排序、冒泡排序、合并排序、快速排序、插入排序、堆排序、希尔排序 算法一:插入排序 插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入 算法步骤: 将第一待排序序列第一

点分治学习模板及一些例题-爱代码爱编程

点分治 这里没有动态点分治。。 点分治是解决树上问题的一类算法,很多复杂度能从暴力的 O ( n 2

平面下的分治算法(平面点对问题和凸包问题)及其分治算法的改进(下)-爱代码爱编程

如果说吃一个包子不饱,两个包子不饱,到第五个才能饱。这是量变引起的质变。 如果说一个原始文明到一个古代文明再到一个近代文明到现代再到未来。这就是文明的传承。这两个都是前面的铺垫给了现在的辉煌 文明从来都没有灭亡。我们看不到不代表不存在,不仅存在还有可能是我们今朝的缩影。我们不是替换了它,而是一步步传承下去,想了好的方向发展。我们祖宗一辈辈的摸索到了现在中国

快速排序时间、空间复杂度-爱代码爱编程

  基本思想: Quicksort是对归并排序算法的优化,继承了归并排序的优点,同样应用了分治思想。 优缺点: 排序算法的应用都需要结合具体环境来考虑,例如若给定序列部分有序,希尔算法最快 快速排序的”快“是建立在综合考虑的基础上,具体情况则不一定(排序效率取决增量序列) 快速排序也不是万能的,例如当给定序列规模很小时,选择排序/插入排序就要比快

算法(二) 从二分到分治(含复杂度分析)-爱代码爱编程

算法(二):从二分到分治 1.二分: 二分可以看作是特殊的分治,其内容与分治极其像。顾名思义,二分通过将序列分为左右两段进行解题,如此递归(通过递归实现)。那么,像这样解题显然是需要序列的 单调性 I .

点分治(树分治)详解-爱代码爱编程

       作者: hsez_yyh        链接:https://blog.csdn.net/yyh_getAC/article/details/126696654        来源:湖北省黄石二中信息竞赛组        著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。         点分治,又叫树分治,顾名思义,