点分治

参考博客

概述

点分治适合处理大规模的树上路径信息问题。——摘自 OI Wiki

时间复杂度 \(O(n\log n)\) （每次 \(calc\) 时间复杂度为 \(O(size_{root})\)）。

对于树上的所有路径及一个假定的根 \(rt\) ，有两种路径：

1. 经过 \(rt\) 的；
2. 不经过 \(rt\) 的。

第一种路径显然分两部分（可以为空），分别位于不同的子树中。
显然第二种路径对于某个节点 \(u\) ，属于第一种路径。所以分治解决即可。

点分治时间复杂度为 \(O(nT)\) ，其中 \(T\) 为树的深度。（因为每次分治要一共处理整棵树，而最多要进行 \(T\) 次分治）。当树是一条链且每次选择链头分治时，时间复杂度就是 \(O(n^2)\) 了。

因此，我们每次寻找子树的重心作为 \(rt\) 进行分治（重心满足最大子树 \(size\) 最小）。时间复杂度 \(O(nlogn)\) 。

该算法大致流程如下：

1. \(rt\gets\) 树的重心。
2. 计算经过 \(rt\) 的路径贡献。
3. 对 \(rt\) 的每棵子树分别找重心，重复流程。

大致 Code（未过编）

#include<bits/stdc++.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+7;
int n,m;
int u,v,w;
int q;
int head[N],cnt;
int siz[N],mxsiz[N];//siz 即子树大小,mxsiz 以 u 为根最大子树 size 
int rt;
bool de[N]; //点分治专属，是否删除 
struct edge{
	int to,val,ne;
}e[N<<1];
void add(int u,int v,int w){
	e[++cnt].val=w,e[cnt].to=v,e[cnt].ne=head[u];
	head[u]=cnt;
}
void getroot(int u,int fa){// 找根 
	siz[u]=1;// 初始化 size 
	mxsiz[u]=0;// 初始化 max_size 
	for(int i=head[u];i;i=e[i].ne){
		int v=e[i].to,w=e[i].val;
		if(de[v]||v==fa) continue;
		getroot(v,u);
		siz[u]+=siz[v];
		mxsiz[u]=max(mxsiz[u],siz[v]);
	}
	mxsiz[u]=max(mxsiz[u],n-mxsiz[u]);//以 u 为根的子树包括上面那一堆 
	if(mxsiz[u]<mxsiz[rt]) rt=u;
}
void getans(int u,int fa,int ans,int from){// from 表示结点 u 来自哪棵子树 
	// 存储 ans 
	for(int i=head[u];i;i=e[i].ne){
		int v=e[i].to,w=e[i].val;
		if(v==fa||de[v]) continue;
		getans(v,u,/*ans的一些操作*/,from);
	}
}
void calc(int u){
	for(int i=head[u];i;i=e[i].ne){//遍历每个子树 
		int v=e[i].to,w=e[i].val;
		if(de[v]) continue;
		getans(v,u,w,v);
	}
	// 对存储的 ans 进行一些操作 
}
void solve(int u){ // 点分治 
	de[u]=1;
	calc(u);// 计算经过 u 的路径的贡献 
	for(int i=head[u];i;i=e[i].ne){
		int v=e[i].to,w=e[i].val;
		if(de[v]) continue;
		rt=0;// 初始化 
		n=siz[v];//当前要找重心的子树的总大小 
		getroot(v,u);
		solve(rt);
	}
}
int main(){
	sf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		sf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
	}
	sf("%d",&q);
	mxsiz[0]=n;//初始化 
	getroot(1,0);
	solve(rt);
	pf("%d\n",ans);
}

经验

P3806 模板

暴力思路

暴力枚举两个点，然后倍增求LCA求距离。时间复杂度 \(O(n^2logn)\) 。

点分治做法

参考该题解

暴力做法重复算了很多次距离。

以重心为根，计算每个点到根的距离，并排序。枚举每个点， \(logn\) 求出符合的第二个点的数量（代码中双指针 \(O(n)\) ）。

这样就求出了经过根的所有答案。

对于不经过根的答案，拆分子树，找到子树的重心，递归下去。

因为每次找的是重心，所以一共要递归 \(logn\) 次，每次算距离共要遍历整棵树，即 \(n\) 个点，排序共 \(nlogn\) ，找第二个点双指针共 \(n\) ，答案处理共 \(nm\) ，因此算法总复杂度为 \(nlog^2n+nlogn+nmlogn=O(nlog^2n+nmlogn)\) 。

P4178 Tree

给定一棵 \(n\) 个节点的树，每条边有边权，求出树上两点距离小于等于 \(k\) 的点对数量。

做法时间复杂度 \(O(nlog^2n)\) 。

一眼点分治，这里解释 \(calc\) （计算经过结点 \(u\) 的路径贡献）部分。

将 \(u\) 子树下的所有点记录深度并排序，双指针即可，时间复杂度 \(nlogn\) 。

需要减去路径起点和终点经过 \(u\) 的同一棵子树的情况，只需要遍历 \(u\) 的儿子，分别减去 \(calc(v)\) 即可。

P4149 Race

给定一棵 \(n\) 个节点的树，每条边有边权，求出树上两点距离等于 \(k\) 的路径最小边数。

树上路径问题，用点分治。

时间复杂度 \(O(nlogn)\) 。

计算每个结点的贡献：\(clac\) 中用桶记录每个深度的最小边数即可，然后清空桶（不可 memset）。

其他和模板一样。

求第 k 长路径

给定一棵树，求树上第 k 长路径的长度。\(n,m\le 10^5\)。

考虑二分答案，二分长度 \(len\) 然后点分治求长度 \(\le len\) 的路径数量。时间复杂度 \(O(n\log^2n\log V)\)。

优化：发现每次点分治的过程都是一样的，没必要做 \(\log V\) 次。考虑到每次求经过重心的路径的方法是先求 \(calc(rt)\) 然后减去所有儿子的答案（减去重复经过一个儿子的答案）。开一个结构体记录点分治的过程，vector d_u; 记录经过点 \(u\) 的所有 \(dis\)。设 \(u\) 的子树大小为 \(size\)，显然 vector 的空间为 \(size\)。对于每个点，我们要记录它自己和它的儿子，所以一共要开 \(2n\) 个 vector。

然后每次二分 \(O(n\log n)\) 统计长度 \(\le mid\) 的边数即可。

总时间复杂度 \(O(n\log n \log V )\)。