点分治学习笔记

修改

2026年9月3日 · 阅读需 16 分钟

laieahoy

管理员

前言

淀粉质是什么，好吃吗？( ´ ▽ ` )

一、点分治主要解决什么问题？

点分治主要用于解决树上路径统计问题，尤其是所有路径相关的问题。

典型问题：

路径长度等于 $K$ 的路径数量；
路径长度 $\le K$ 的路径数量；
路径权值和满足某种条件的路径数量；
路径上点权异或和满足某种条件的路径数量。

对于这类问题，直接暴力枚举点对的复杂度是 $O(n^2)$ 的，遇到稍微大一点的数据处理起来就捉襟见肘了，于是我们引入了点分治这一方法，它可以在 $O(n\log n）$ 的时间内高效处理上述的问题。

二、点分治如何优化时间？

点分治有一个别名叫做树的重心分解，从此也可以看出它的实现是与重心息息相关的，那么它的核心处理思路是什么呢？其实可以分为下面四个步骤：

找当前连通块的重心;
收集当前重心的每个儿子子树的信息;
统计不同子树之间的配对;
递归处理每个子树。

那么这样为什么可以大大减少时间复杂度呢？让我们想想暴力是怎么处理各个路径的，它会枚举每个点对，再来计算路径信息，那么我们或许已经算过了某点到某点的路径信息，但之后需要使用的时候还会再算一遍，而点分治呢，观察上述步骤我们会发现，点分治会存储已经算过的路径信息，从而减少很多不必要的计算，而其实无论选哪个点作为子树的中心点（就是作为媒介存储信息的点）都是可以达到我们的目的的，选择重心是为了缩小递归层数以保证时间复杂度严格为 $O(n\log n)$ 。

但是需要注意，因为我们需要记录并用到已处理过的路径信息，所以路径上的信息是可以通过选择与已知量快速计算的，否则就不能用点分治，所以一般点分治的题目需要维护的信息都是路径长度，后面我们也统一使用路径长度来讲解。

三、点分治的具体实现

（1）点分治如何拆分路径？

假设当前连通块的重心是 $c$ ，任意一条路径只有两种情况：

路径经过点 $c$ ;
路径不经过点 $c$ ；

这是显然的。我们可以依次考虑如何处理

路径经过重心 $c$ 时

对于路径的端点 $u$ 和 $v$ ，我们可以将路径长度 $dist(u,v)$ 分成 $dist(u,c)+dist(c,v)$ ，比如要求满足路径长度为 $k$ 的路径条数时，我们会先收集已经处理过的点到 $c$ 的距离，然后再寻找当前子树中的到 $c$ 的各路径，在寻找使距离之和满足要求的已经处理过的点有多少个，这样边遍历边处理的方法还可以保证每个点对只被计算一次。

路径不经过重心 $c$ 时

这条路径一定位于 $c$ 的某个子树中，因为如果在它的父亲的儿子子树中某个不为 $c$ 的子树中的话，不会被遍历到。那么直接递归计算即可。

（2）统计经过重心的路径

以“统计边权路径长度等于 $K$ 的路径”为例。

当前重心为 $c$ ，从 $c$ 的某个子树中收集到：

d=距离某个节点到 c 的距离

如果当前节点距离是 $d$ ，那么它需要和之前某个距离为： $K-d$ 的节点配对。

于是可以使用一个桶来记录：

cnt[x]=已经处理过的节点中，距离重心为\, x\, 的节点数

处理一个子树时：

先收集这个子树中所有节点到重心的距离;
对每个距离 $d$ ，查询 $cnt[K-d]$ ，统计能够组成长度为 $K$ 的路径；
查询结束后，再把当前子树的所有距离加入 $cnt$ 。关键是：查询与加入必须分开，而且加入一定要在查询之前，因为如果加入在查询之前，那么可能会查询到自己。

初始化： $cnt[0]=1$ 。因为重心到自己的距离为 $0$ 。

对于其他问题，只能灵活解决了，但是基本流程应该是基本一致的。

（3）点分治的标准流程

solve(当前连通块):
    找到当前连通块的重心 c
    标记 c 已经被分治使用

    初始化统计结构

    对 c 的每个未被标记的邻居 v:
        收集 v 所在子树中所有节点的信息
        用统计结构查询可以配对的节点
        把这些节点的信息加入统计结构

    对 c 的每个未被标记的邻居 v:
        递归处理 v 所在的连通块

（4）点分治的常见各个流程详解

首先，我们发现需要寻找重心，那么如何寻找重心呢？我们通常会分两次 DFS 来求。

第一次 DFS：求子树大小

int get_sz(int u,int fa)
{
    sz[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(v==fa||vis[v]) continue;
        sz[u]+=get_sz(v,u);
    }
    return sz[u];
}

第二次 DFS：寻找最优点（重心）

对于节点 $u$ ，删除它之后最大的连通块大小为：

max(
    当前连通块总大小 - size[u],
    每个子节点方向的 size[v]
)

选择这个值最小的节点，就是重心。

int get_cog(int u,int fa,int totalsz)
{
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(v==fa||vis[v]) continue;
        if(sz[v]>totalsz/2) return get_cog(v,u,totalsz);
    }
    return u;
}

至于为什么这段代码是对的，证明如下：

设当前未被分治切开的连通块大小为 $S$ 。对一个点 $x$ ，删除它后会得到若干连通块，定义：

F(x) = 删除 x 后的最大连通块大小

重心就是使 $F(x)$ 最小的点。

这段代码通过“沿着超过一半的子树向下走”来找到它：

if (sz[v] > totalsz / 2)
    return get_cog(v, u, totalsz);

为什么这样走最终得到的是让最大连通块最小的点？

如果当前点 $u$ 存在一个子树 $v$ ，满足 $sz[v] > S / 2$ ，那么删除 $u$ 后，这个子树就是最大连通块，而且它占了超过一半。
此时把候选点从 $u$ 移到 $v$ ，原来这个“大块”会被继续分割。对于新点 $v$ ：
- 朝 $u$ 方向的连通块大小是 $S - sz[v]$ ，小于 $S / 2$ ；
- $v$ 的其他子树都包含在原来的 $v$ 子树中，因此大小都小于 $sz[v]$ 。

沿着这个方向继续走，就能不断缩小当前最大的“超过一半”的部分。

当代码到达某个点 $c$ ，不存在儿子子树满足：

sz[v] > S / 2

那么所有儿子方向的连通块都不超过 $S / 2$ 。

同时，父节点方向也不超过 $S / 2$ ：如果 $c$ 是从父节点方向走过来的，那么进入 $c$ 的那棵子树原本已经满足 $sz[c] > S / 2$ ，所以父方向大小为：

S - sz[c] < S / 2

如果 $c$ 是初始调用点，则没有父方向。

因此，删除 $c$ 后的每个连通块都不超过 $S / 2$ 。

最后还需要说明，为什么“每个连通块都不超过一半”就等价于最大连通块最小。

设 $c$ 满足这个条件，任意选择另一个点 $x$ 。从 $c$ 走向 $x$ 的第一条边，位于 $c$ 删除后得到的某个连通块 $A$ 中，并且：

|A| <= S / 2

删除 $x$ 后，朝向 $c$ 的那一侧至少包含 $S - |A|$ 个点，因此大小至少为 $S / 2$ 。也就是说：

F(x) >= S / 2 F(c) <= S / 2

所以没有任何其他点能让最大连通块比 $c$ 更小， $c$ 就是重心。重心可能有两个，但它们的 $F$ 值相同。

因此，这份代码不是只找一个“能保证复杂度”的点，而是利用了重心的等价判定条件，确实找到了当前连通块的重心。重心的这个性质随后保证点分治递归的每个子问题规模至多约为原来的 $1/2$ 。

然后统计路径，一般也是用递归求解，还有后续继续递归子树，都与我们前面的流程是一致的，具体的实现可以看代码。

（5）点分治的完整代码

以“统计是否有距离为 $k$ 的点对”（洛谷 P3806）为例：

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;

const int N=1e4+5,M=105,K=1e7+5;
int n,m,ma;
int e[N<<1],ne[N<<1],w[N<<1],h[N],idx;
int sz[N];
int qu[M];
bool vis[N],ans[M],usd[K];

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int get_sz(int u,int fa)
{
    sz[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(v==fa||vis[v]) continue;
        sz[u]+=get_sz(v,u);
    }
    return sz[u];
}

int get_cog(int u,int fa,int totalsz)
{
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(v==fa||vis[v]) continue;
        if(sz[v]>totalsz/2) return get_cog(v,u,totalsz);
    }
    return u;
}

void get_path(int u,int fa,vector<int> &d,int dis)
{
    if(dis>ma) return;
    d.push_back(dis);
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i],ww=w[i];
        if(vis[v]||v==fa) continue;
        get_path(v,u,d,dis+ww);
    }
}

void buildtr(int u)
{
    int ts=get_sz(u,0);
    int tc=get_cog(u,0,ts);
    vis[tc]=1;
    vector<int> path;
    path.push_back(0);
    usd[0]=1;
    for(int i=h[tc];~i;i=ne[i]){
        int v=e[i],ww=w[i];
        if(vis[v]) continue;
        vector<int> dis;
        get_path(v,tc,dis,ww);
        for(int dd:dis){
            for(int j=1;j<=m;j++){
                if(ans[j]) continue;
                int nd=qu[j]-dd;
                if(nd>=0&&usd[nd]) ans[j]=1;
            }
        }
        for(int dd:dis){
            path.push_back(dd);
            usd[dd]=1;
        }
    }
    for(int dd:path) usd[dd]=0;
    for(int i=h[tc];~i;i=ne[i]){
        int v=e[i];
        if(!vis[v]) buildtr(v);
    }
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w;
        add(u,v,w),add(v,u,w);
    }
    for(int i=1;i<=m;i++) cin>>qu[i],ma=max(ma,qu[i]);
    buildtr(1);
    for(int i=1;i<=m;i++){
        if(ans[i]) puts("AYE");
        else puts("NAY");
    }
    
    return 0;
}

四、一些例题

洛谷 P4178 Tree

这道题的题意很明了，就是统计树上距离不超过 $k$ 的点对的数量。

除了基本的点分治处理树上距离的模板之外，我们需要思考的是如何处理距离 $\le k$ 这个条件，这里要用一个很巧妙的技巧，我们知道，点分治处理问题时不能处理位于某点同一儿子子树的两点的路径，因为他们不合法，那么如果我们对某点的子树的全部路径都算一遍答案，那么一定有一些不合法的点对被计算了，但点对只会被计算一次，利用这个特性，可以先把所有不合法但会被计算的点对的数量处理出来，再在总子树的答案中减去，就能得到最终的答案。

那么如何计算不合法但会被计算的点对呢，在点分治递归的过程中，会将当前连通块重心的某个儿子子树的全部距离计算一遍，假如我们用一个 $vector$ 来存储这些距离，再对这些距离算一遍答案，那么这棵儿子子树上的不合法的点对后续会贡献的答案就被计算出来了，以此类推，因为不合法但会被计算的点对只可能出现在当前处理的连通块的重心的儿子子树中，所以这样的点对会被我们算完。类似的，我们存储所有可能出现的距离，最后再求一遍答案，然后减去其中不合法的点对数就行。

现在需要考虑的最后一个问题是，如何对一堆距离求答案呢，我们可以先将距离排序，然后用双指针，让左指针先指向最左端，右指针先指向最右端，那么左指针每右移一个点就会增加左右指针指向的距离的和，右指针每左移一个点会减少左右指针指向的距离的和，这样，若两个指针指向的距离的和小于等于 $k$ 的话，右指针指向在左指针之后，自己之前的任意位置都能使距离和满足条件，增加的答案为 $r-l$ ，然后左指针右移，否则的话就右指针左移。

具体实现见代码。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

const int N=4e4+5;
int n,k;
vector<pii> g[N],path[N];
bool vis[N];
int sz[N];
ll ans;

int get_sz(int u,int fa)
{
	sz[u]=1;
	for(auto i:g[u]){
		int v=i.x;
		if(v==fa||vis[v]) continue;
		sz[u]+=get_sz(v,u);
	}
	return sz[u];
}

int get_cog(int u,int fa,int totalsz)
{
	for(auto i:g[u]){
		int v=i.x;
		if(v==fa||vis[v]) continue;
		if(sz[v]>totalsz/2) return get_cog(v,u,totalsz);
	}
	return u;
}

void get_path(int u,int cog,int fa,int dis,vector<int> &d)
{
	if(dis>k) return;
	path[u].push_back({cog,dis});
	d.push_back(dis);
	for(auto i:g[u]){
		int v=i.x,w=i.y;
		if(v==fa||vis[v]) continue;
		get_path(v,cog,u,dis+w,d);
	}
}

ll calc(vector<int> &d)
{
	ll res=0;
	sort(d.begin(),d.end());
	int l=0,r=d.size()-1;
	while(l<r){
		if(d[l]+d[r]<=k){
			res+=(r-l);
			l++;
		}else{
			r--;
		}
	}
	return res;
}

void buildtr(int u)
{
	int ts=get_sz(u,0);
	int tc=get_cog(u,0,ts);
	vis[tc]=1;
	vector<int> all;
	all.push_back(0);
	for(auto i:g[tc]){
		int v=i.x,w=i.y;
		if(vis[v]) continue;
		vector<int> d;
		get_path(v,tc,0,w,d);
		ans-=calc(d);
		for(int dd:d) all.push_back(dd);
	}
	ans+=calc(all);
	for(auto i:g[tc]){
		int v=i.x,w=i.y;
		if(vis[v]) continue;
		buildtr(v);
	}
}

int main()
{
	cin>>n;
	for(int i=1,u,v,w;i<n;i++){
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	cin>>k;
	buildtr(1);
	cout<<ans<<"\n";

	return 0;
}

洛谷 P2634 [国家集训队] 聪聪可可

题面翻译过来就是统计路径长度是 $3$ 的倍数的路径的数量，很裸的点分治模板（~~虽然好像可以用更好写而且更快的树形 DP 来写~~）。

先转化一下，路径长度为 $3$ 的倍数，就是说长度模 $3$ 后为 $0$ ，那么我们可以统计路径长度模 $3$ 的余数，这样， $1$ 配 $2$ ， $0$ 配 $0$ ，就可以统计了。

但是有一点要注意，计算的是概率，而且两人的决策对方是不知道的，所以可能选到相同的点，而且计算时每条边要算两遍，因为 $3,4$ 与 $4,3$ 是不同情况，而总情况数也是 $n^2$ 的，这个推一下就知道了。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<numeric>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;

const int N=2e4+5;
int n,ans;
int sz[N],cnt[N];
vector<pii> g[N];
bool vis[N];

int get_sz(int u,int fa)
{
    sz[u]=1;
    for(auto i:g[u]){
        int v=i.x;
        if(v==fa||vis[v]) continue;
        sz[u]+=get_sz(v,u);
    }
    return sz[u];
}

int get_cog(int u,int fa,int totalsz)
{
    for(auto i:g[u]){
        int v=i.x;
        if(v==fa||vis[v]) continue;
        if(sz[v]>totalsz/2) return get_cog(v,u,totalsz);
    }
    return u;
}

void get_path(int u,int fa,vector<int> &d,int dis)
{
    d.push_back(dis%3);
    for(auto i:g[u]){
        int v=i.x,w=i.y;
        if(v==fa||vis[v]) continue;
        get_path(v,u,d,dis%3+w);
    }
}

void buildtr(int u)
{
    int ts=get_sz(u,0);
    int cog=get_cog(u,0,ts);
    vis[cog]=1;
    memset(cnt,0,sizeof cnt);
    cnt[0]=1;
    for(auto i:g[cog]){
        int v=i.x,w=i.y;
        if(vis[v]) continue;
        vector<int> d;
        get_path(v,cog,d,w);
        for(int dd:d){
            if(dd==0) ans+=cnt[0];
            else if(dd==1) ans+=cnt[2];
            else ans+=cnt[1];
        }
        for(int dd:d) cnt[dd]++;
    }
    for(auto i:g[cog]){
        int v=i.x;
        if(!vis[v]) buildtr(v);
    }
}

int main()
{
    cin>>n;
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    buildtr(1);
    ans*=2;
    ans+=n;
    int m=n*n;
    int tg=__gcd(m,ans);
    cout<<ans/tg<<"/"<<m/tg<<"\n";

    return 0;
}

前言​

一、点分治主要解决什么问题？​

二、点分治如何优化时间？​

三、点分治的具体实现​

（1）点分治如何拆分路径？​

路径经过重心 ccc 时​

路径不经过重心 ccc 时​

（2）统计经过重心的路径​

（3）点分治的标准流程​

（4）点分治的常见各个流程详解​

第一次 DFS：求子树大小​

第二次 DFS：寻找最优点（重心）​

（5）点分治的完整代码​

四、一些例题​

洛谷 P4178 Tree​

洛谷 P2634 [国家集训队] 聪聪可可​

前言

一、点分治主要解决什么问题？

二、点分治如何优化时间？

三、点分治的具体实现

（1）点分治如何拆分路径？

路径经过重心 $c$ 时

路径不经过重心 $c$ 时

（2）统计经过重心的路径

（3）点分治的标准流程

（4）点分治的常见各个流程详解

第一次 DFS：求子树大小

第二次 DFS：寻找最优点（重心）

（5）点分治的完整代码

四、一些例题

洛谷 P4178 Tree

洛谷 P2634 [国家集训队] 聪聪可可