时间戳

首页 > 技术文章 > 点分治学习笔记

点分治学习笔记

hzoi-liujiahui 2020-09-25 06:21 原文

简介

点分治顾名思义是利用分治的思想，将原本要\(n^3\)的操作降到\(\Theta (n^2\times log_n)\)，大大提高了优越性（不提高效率谁学啊喂）

基本思路

点分治如同普通的分治一样，普通的分治是处理两种情况：在一个区间的任务转化为两个区间的任务，把在两个子区间的任务在两个子区间里运算，而在跨两个子区间的任务则在本次处理掉，可以提高效率。推广到树上，对于要找到的路径（注意不是边），路径可以不经过当前的根节点，也可以经过当前的根节点，把不经过当前根节点的在自己的子树中去处理，而把经过当前根节点的在此时处理掉，因为树的深度限制要想达到提高效率，就要要找到一个节点，使得自己的子树大小均衡，这个节点我们称之为树的重心。通过不断的找树的重心来保证时间效率的优秀性，要是不找重心，树变成一条链，会把点分治(这东西现在还能叫分治？)卡成暴力的复杂度。

例题 Tree

给定一棵树，树上的边有权值，给定一个阈值k，请统计这棵树上总长度小于等于k的路径个数。路径长度为路径路径上所有边的权值和。

框架

这是点分治中很经典的题目，首先写一下点分治的整体代码：

void DFS (int u) {
	ans += Calc(u, 0);//求经过u节点的所有方案数
	vis[u] = true;//表示访问过
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (vis[v]) continue;
		ans -= Calc (v, edge[i].val);//由于同一棵子树中可能有两个点距离满足条件，需要去重
		root = 0;//重新找重心
      		Tsiz = siz[v];//表示当前子树的大小
		getroot(v, u);//找重心
		DFS(root);//分治，处理每个子树中的问题
	}
}

现在看不懂没关系，懂了大体结构再往下读。

找树根

void getroot (int u, int fa) {
	siz[u] = 1, w[u] = 0;//预处理
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == fa || vis[v]) continue;
		getroot (v, u);//递归求重链和树的大小
		siz[u] += siz[v];
		w[u] = max (w[u], siz[v]);//求当前节点子树中节点最多的
	}
	w[u] = max(w[u], Tsiz - siz[u]);//该根节点还有其他的子树
      	if (w[u] < w[root]) root = u;
}

w数组指的是该根节点下的所有子树中size最大的值，而要是一一个节点作为跟节点，那么该树中其他的点都是该根节点的子树，找到一个点让每个子树都很平均即找到了树根。

求方案数

找到了一个树根之后，以这个跟节点作为起点，有dfs求出该子树中的方案数，两个点到根节点的距离之和小于k即满足要求，同时如果两个节点在该根节点的同一棵子树中，就会出现不合法的方案，然后我们只需要在每个子树中减去多余的方案数即可。

void dfs (int u, int fa, int dis) {
	a[++cnt] = dis;//将每个节点的距离都推进数组a
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == fa || vis[v]) continue;
		dfs (v, u, dis + edge[i].val);//递归处理
	}
}
int Calc (int u, int dis) {
	cnt = 0;
	dfs (u, 0, dis);//预处理子树中的方案数
	sort (a + 1, a + 1 + cnt);//排序后可以发现能用双指针维护，要是不用双指针效率大大降低。。
	int sum = 0;
	for (register int i = 1, j = cnt; ; i++) {
		while (j && a[i] + a[j] > k) j--;//找到合法的区间
		if (j < i) break;//防止同一个方案计算两次
		sum += j - i + 1;
	}
	return sum;
}

在返回来看主分治的代码中，

void DFS (int u) {
      ans += Calc (u, 0);
      for (register int i = head[u]; i; i = edge[i].next) {
            ans -= Calc (v, edge[i].val);
      }
}

注意在找子树中不合法方案数的时候一定不要找成子树中的方案，在Calc传参的时候要加上该子树跟节点到u的距离，这样找到的所有方案数才是真正多加上的方案数，否则会减多了。可以自己手画一下图来理解一下。

总结

学会点分治只是一种思想，还需要自己多加练习，才能很好的利用点分治解决一些题目。
放一下整体的代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
const int maxn = 4e4 + 50;
inline int read () {
	int x = 0, f = 1; char ch = getchar();
	for (;!isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	return x * f;
}
int n, k;
int ans;
struct Edge {
	int to, next, val;
} edge[maxn << 1];
int cnt;
int tot, head[maxn];
int a[maxn];
int root;
int Tsiz;
void addedge (int a, int b, int c) {
	edge[++tot].next = head[a];
	head[a] = tot;
	edge[tot].to = b;
	edge[tot].val = c;
}
bool vis[maxn];
int siz[maxn], w[maxn];
void getroot (int u, int fa) {
	siz[u] = 1, w[u] = 0;
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == fa || vis[v]) continue;
		getroot (v, u);
		siz[u] += siz[v];
		w[u] = max (w[u], siz[v]);
	}
	w[u] = max(w[u], Tsiz - siz[u]);
	if (w[u] < w[root]) root = u;
}
void dfs (int u, int fa, int dis) {
	a[++cnt] = dis;
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == fa || vis[v]) continue;
		dfs (v, u, dis + edge[i].val);
	}
}
int Calc (int u, int dis) {
	cnt = 0;
	dfs (u, 0, dis);
	sort (a + 1, a + 1 + cnt);
	int sum = 0;
	for (register int i = 1, j = cnt; ; i++) {
		while (j && a[i] + a[j] > k) j--;
		if (j < i) break;
		sum += j - i + 1;
	}
	return sum;
}
void DFS (int u) {
	ans += Calc(u, 0);
	vis[u] = true;
	for (register int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (vis[v]) continue;
		ans -= Calc (v, edge[i].val);
		root = 0;
		Tsiz = siz[v];
		getroot(v, u);
		DFS(root);
	}
}
int main () {
	n = read();
	int x, y, z;
	for (register int i = 1; i <= n - 1; i ++) {
		x = read(), y = read(), z = read();
		addedge (x, y, z), addedge (y, x, z);
	}
	cin >> k;
	w[0] = 0x3f3f3f3f;
	root = 0;
	getroot (1, 0);
	Tsiz = n;
	DFS (root);
	printf ("%d\n", ans - n);//注意由于在每次dfs维护dis的时候把跟节点也加入到了a数组中，每个点也多算了一次，所以要减去n才是正确答案。
	return 0;
}

完结散花qwq

推荐阅读