点分治 & 点分树 学习笔记
RabbieWjy
·
·
算法·理论
点分治 & 点分树 学习笔记
点分治（树分治）
点分治是什么？
字面上理解，点分治就是“点”和“分治”。它的思路是把一个无根树树上问题拆分成若干个规模更小的无根树上问题和一个有根树（？）上问题。
例题
【模板】点分治1 - 洛谷
给定一棵有 n 个节点的树，m 次询问树上距离为 k 的点对是否存在。
#### 暴力做法
每次询问，考虑对于每一个点，用树形 dp 求出经过这个点（包括以这个点为端点）的路径中是否有长度为 $k$ 的，这个判断可以处理出深度后用双指针实现。时间复杂度 $O(mn^2\log n)$，显然过不去。换根 dp 也因为 $k$ 太大，做不了。
#### 点分治做法
考虑优化这个暴力，发现对于每个点都做一次树形 dp 很浪费时间。
看一下一棵树上的路径有哪些？
我们可以简单把树上的所有路径分为两类：**经过根节点的** 和 **不经过根节点的**。而暴力做法中，就是把每个点都当成一次根节点，在经过根节点的路径中找长度为 $k$ 的。
一个显然的发现是，不经过根节点的路径肯定在根节点的一个子树中。把根节点删掉，剩下的几个子树就成为了几个规模更小的同样的问题，可以分治解决。时间复杂度为 $O(mn\log n\times 层数)$。
这个“层数“看起来很难受，如果随便取每次分治的根节点（也就是 **分治中心**）的话，层数可以达到 $O(n)$ 级别，那就优化了个寂寞。我们要想办法把层数减少。
可以想到，每次 **分出来的几个子问题的规模最大的要尽量小**，才能使得时间减少。这让我们想到了**重心**。
树的重心有一条性质，叫做 **以树的重心为根时，所有子树的大小都不超过整棵树大小的一半**。这条性质使得分治的层数变成了 $O(\log n)$ 级别，总的时间复杂度变成了 $O(mn\log^2 n)$，足以通过这道题。
#### 总结
至此，我们已经了解了这道题中的点分治做法，可以归纳成下面几步：
1. 找重心，作为根；
2. 树形 dp+ 双指针求解每个询问；
3. 递归求解每个子树。
而点分治的大多数问题，只是把第 $2$ 步改一改，总体思路都是一样的。
#### 例题代码（点分治主体部分）
```cpp
void fndroot(int x,int la)//找根
{
siz[x] = 1;
maxsiz[x] = 0;
for (int i = head[x];i;i = nxt[i])
{
int u = to[i];
if (u == la || vis[u]) continue;
fndroot(u,x);
siz[x] += siz[u];
maxsiz[x] = max(maxsiz[x],siz[u]);
}
maxsiz[x] = max(maxsiz[x],nsiz - siz[x]);
if (maxsiz[x] < maxsiz[root]) root = x;
}
void caldis(int x,int la,int topx)//树形 dp
{
for (int i = head[x];i;i = nxt[i])
{
int u = to[i];
if (u == la || vis[u]) continue;
dis[u] = dis[x] + val[i];
v.push_back(make_pair(dis[u],topx));
caldis(u,x,topx);
}
}
void cal(int x)//双指针
{
v.clear();
v.push_back(make_pair(0,x));
for (int i = head[x];i;i = nxt[i])
{
int u = to[i];
if (vis[u]) continue;
dis[u] = val[i];
v.push_back(make_pair(dis[u],u));
caldis(u,x,u);
}
sort(v.begin(),v.end());
for (int i = 1;i <= m;i ++)
{
if (ans[i]) continue;
int l = 0,r = v.size() - 1;
while (l < r)
{
if (v[l].first + v[r].first < que[i]) l ++;
else if (v[l].first + v[r].first > que[i]) r --;
else
{
if (v[l].second == v[r].second)
{
if (v[r].first == v[r - 1].first) r --;
else l ++;
}
else
{
ans[i] = 1;
break;
}
}
}
}
}
void dfs(int x)//点分治主体
{
vis[x] = 1;
cal(x);
for (int i = head[x];i;i = nxt[i])
{
int u = to[i];
if (vis[u]) continue;
nsiz = siz[u];
root = 0;
fndroot(u,x);
dfs(root);
}
}
```
#### 另：关于找重心
[一种基于错误的寻找重心方法的点分治的复杂度分析 - 博客 - liu_cheng_ao的博客](https://liu-cheng-ao.blog.uoj.ac/blog/2969)
####
### 练习题目
[Tree - 洛谷](https://www.luogu.com.cn/problem/P4178)
[[国家集训队]聪聪可可 - 洛谷](https://www.luogu.com.cn/problem/P2634)
[[IOI2011]Race - 洛谷](https://www.luogu.com.cn/problem/P4149)
[树上游戏 - 洛谷](https://www.luogu.com.cn/problem/P2664)
[[BJOI2017]树的难题 - 洛谷](https://www.luogu.com.cn/problem/P3714)
## 点分树（动态点分治）
在点分治中，我们依次作为分治中心的点根据访问顺序可以形成一棵树（就像 dfs 树那样），这棵树成为点分树。
这颗树的节点与原树的节点相同，且深度为 $O(\log n)$，所以许多点分树上的暴力做法的时间复杂度都是正确的。
点分树有一个常用性质：点分树上两点的 LCA 一定在这两点在原树上的路径上。
还有一个注意点：点分树上两点的关系（父子关系之类的）与原树上这两点的关系 **并没有什么关系**。
### 例题
[【模板】点分树 | 震波 - 洛谷](https://www.luogu.com.cn/problem/P6329)
题面见链接。
#### 做法
想一想与点 $x$ 距离为 $k$ 的点有哪些。（以下都是在点分树上）
这些点可能在 $x$ 的子树里，可能在 $x$ 的父亲的子树里但不在 $x$ 的子树里，可能在 $x$ 的父亲的父亲的子树里但不在 $x$ 的父亲的子树里……
于是我们想到，可以用一个（$n$ 个？）数据结构存下每个点的子树的节点信息，比如距离 $x$ 为 $k$ 的点的价值和，询问的时候一层一层往父亲跳，同时更新答案就可以了。正好层数那么少，数据结构用动态开点线段树或者什么别的就行了。
但是还有一个问题：跳到 $x$ 的父亲之后，怎么找 $x$ 的子树以外的距离 $x$ 为 $k$ 的点呢？
显然，直接减掉 $x$ 的子树内的就好了。具体的说，用 $dis(x,y)$ 表示点 $x$ 和 $y$ 的距离，要找的点的权值和就是 $\sum \limits _{u \in fa(x) 的子树 \& dis(x,u)=k} val(u) - \sum \limits _{u \in x 的子树 \& dis(x,u)=k} val(u)$。
根据上面提到的性质，这个式子可以变为：$\sum \limits _{u \in fa(x) 的子树 \& dis(fa(x),u)=k-dis(x,fa(x))} val(u)-\sum \limits _{u \in x 的子树 \& dis(fa(x),u)=k-dis(x,fa(x))}val(u)$。
左半部分可以继续用数据结构求出，而右半部分则需要多维护一个叫 $dis(fa(x),u)$ 的东西。根据上面的注意点，$dis(fa(x),u) \neq dis(x,u)+dis(x,fa(x))$，所以我们必须多用一个数据结构维护这个东西。
至于修改操作，直接一层一层往上跳修改就好了。
时间复杂度为 $O(n\log^2 n+m\log^2 n)$。
### 练习题
[[HNOI2015]开店 - 洛谷](https://www.luogu.com.cn/problem/P3241)
[[ZJOI2007] 捉迷藏 - 洛谷](https://www.luogu.com.cn/problem/P2056)
[QTREE4 - Query on a tree IV - 洛谷](https://www.luogu.com.cn/problem/SP2666) [Qtree4 - 洛谷](https://www.luogu.com.cn/problem/P4115)（卡常题）
[[ZJOI2015]幻想乡战略游戏 - 洛谷](https://www.luogu.com.cn/problem/P3345)
[[CTSC2018]暴力写挂 - 洛谷](https://www.luogu.com.cn/problem/P4565)