前言
既然序列可以分治，那么树也可以分治。树上的分治可以分为点分治与边分治。
点分治
边分治主要用于处理树上路径问题。
考虑一个分治的过程：选中一棵树的根，计算经过根的路径的贡献，然后以其子结点为根对子树递归地计算贡献。容易发现，在构造数据下这种算法的复杂度是可以达到 \(O(n^2)\) 的，原因在于递归的层数可能太深了。如果不使用子结点，而是使用子树的重心，那么每一次子树的大小都会减半，递归层数降到了 \(O(\log n)\) 级别。而每一层的点数是 \(O(n)\) 的，所以总时间复杂度变成了 \(O(nk\log n)\)，其中 \(k\) 是统计贡献的复杂度。
然而从理论到实现还是需要一定距离的，因为点分治需要很多细节。贴一份代码，题目是 P3806 【模板】点分治1 。
code1
#include<bits/stdc++.h>
using namespace std;
const int N=10005,M=105;
int n,m,root,k[M],siz[N];
bool vis[N],keg[N*N],ans[M];
vector<pair<int,int> >G[N];
stack<int>s;
void dfs1(int p,int lst) {//修改子树大小
siz[p]=1;
for (auto x:G[p]) {
if (x.first!=lst&&!vis[x.first]) dfs1(x.first,p),siz[p]+=siz[x.first];
}
return;
}
void dfs2(int p,int lst,int sum) {//更新重心
bool f=1;
for (auto x:G[p]) {
if (x.first!=lst&&!vis[x.first]) {
dfs2(x.first,p,sum);
if (siz[x.first]*2>sum) f=0;
}
}
if ((sum-siz[p])*2>sum) f=0;
if (f) root=p;
return;
}
void dfs3(int p,int lst,int d) {//计算贡献
s.push(d);
for (int i=1;i<=m;i++) if (d<=k[i]) ans[i]|=keg[k[i]-d];
for (auto x:G[p]) {
if (x.first!=lst&&!vis[x.first]) {
dfs3(x.first,p,d+x.second);
if (p==root) {//要注意产生贡献的两个点必须在不同的子树内
while (!s.empty()) keg[s.top()]=1,s.pop();
}
}
}
return;
}
void dfs4(int p,int lst,int d) {
keg[d]=0;//消除贡献（必须逐个撤回，否则复杂度有问题）
for (auto x:G[p]) {
if (x.first!=lst&&!vis[x.first]) dfs4(x.first,p,d+x.second);
}
return;
}
void dfz(int p) {
keg[0]=1;
dfs3(root,0,0);
dfs4(root,0,0);
vis[root]=1;//将此节点标记为不可用
for (auto x:G[root]) {
if (!vis[x.first]) {
dfs1(x.first,0);
dfs2(x.first,0,siz[x.first]);
dfz(x.first);
}
}
return;
}
int main() {
scanf("%d %d",&n,&m);
for (int i=1;i<n;i++) {
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
G[u].push_back({v,w});
G[v].push_back({u,w});
}
for (int i=1;i<=m;i++) scanf("%d",&k[i]);//离线下来处理常数会小一些
dfs1(1,0);
dfs2(1,0,n);
dfz(1);
for (int i=1;i<=m;i++) {
if (ans[i]) puts("AYE");
else puts("NAY");
}
return 0;
}
点分树
有了点分治的基础，我们就可以方便定义点分树了。点分树的构造方式就是每一个重心向下一层递归中心连有向边，形成一棵有根树。它有两个重要的性质：
-
它的深度是 \(O(\log n)\) 级别的。
-
对于 \(u\) 和 \(v\)，它们在点分树上的 \(\text{lca}\) 在原树 \(u\) 到 \(v\) 的路径上。
由第二个性质我们可以得到 \(\text{dist}(u,\text{lca})+\text{dist}(v,\text{lca})=\text{dist}(u,v)\)。其中 \(\text{dist}\) 是原树上距离，而 \(\text{lca}\) 是点分树上 \(\text{lca}\)。
标签：int,text,lca,分治,笔记,学习,siz,first From： https://www.cnblogs.com/tulipenoire/p/17368230.html