【模板】点分治 Centroid Decomposition
posted on 2022-07-20 18:59:16 | under 模板 | source
0x00 模板（P3806）
给定 $n,k$ 和一棵树，计算
$$\sum\limits_{i,j\leq n}[{\tt dist}(i,j)=k]$$
即树上距离为 $k$ 的点对数量。
点分治，令 ${\tt solve}(x)$ 表示我们要计算 $u$ 所在连通块的答案。选一个根 $u$（它应该是重心），把点对分成两类：
- 路径经过 $u$ 的：在 ${\tt calc}(u)$ 中计算，表示计算经过 $u$ 的点对数量。
- 路径不经过 $u$ 的：那么这两个点在 $u$ 的某个儿子的子树里，删掉 $u$，继续递归 ${\tt solve}(v)$ 计算。
将这个过程递归下去，就一定能解决所有点对，因为每个根都会被枚举。
选定的根 $u$ 应该是这棵树的重心，考虑重心的定义：删掉一个点后剩余的最大连通块最小（指点数），那么这点称作树的重心。重心最多有两个，最少有一个。
node getroot(int u,int fa,int T){
node res=node(1e9,0);
siz[u]=1,smx[u]=0;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(v==fa||cut[v]) continue;
res=min(res,getroot(v,u,T));
siz[u]+=siz[v];
smx[u]=max(smx[u],siz[v]);
}
smx[u]=max(smx[u],T-siz[u]);
return min(res,node(smx[u],u));
}
注意这个 $\min$，这有一组数据供自测。
把递归的每一层的重心连起来连成一棵树，这棵树叫作点分树。从点分树上的一个点往上跳，点分树的子树大小翻倍，所以点分树只有 $O(\log n)$ 层，总时间复杂度为 $T(n)=2T(\frac{n}{2})+O({\tt calc})$。
//写法一
LL solve(int u,int k){
cut[u]=1;
LL res=calc(u,k);
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(cut[v]) continue;
res+=solve(getroot(v,0,siz[v]).second,k);
}
return res;
}
//写法二：容斥
LL solve(int u){
cut[u]=1;
LL res=calc(u,0);
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(cut[v]) continue;
res-=calc(v,g[i].w);
res+=solve(getroot(v,0,siz[v]).second);
}
return res;
}
solve(getroot(1,0,n).second,k);
你注意到这个递归调用很奇怪，怎么能说 $siz_v$ 是连通块大小呢？膜拜了 这位大佬 后，你不觉得奇怪了，它真的是对的。
那么 ${\tt calc}(u)$ 应该怎么写？
- ${\tt getdist}(u)$：从根出发，把每个点到根的距离存到一个数组里。
- 两种写法：
- 写法一：${\tt getdist}(u)$ 的同时记录这些点来自哪棵子树，计算答案时严格按照这个限制做（即不能有两个点在同一子树中），可以双指针。
- 写法二：我不管什么子树不子树的，我容斥，全部点对减去在子树内的点对就是 $u$ 的答案。注意写法，容斥的时候传下去的初始值要一样。
bool cmp(int x,int y){return dis[x]<dis[y];}
void getdist(int u,int fa,int w,int from){
dis[id[++tot]=u]=w,fom[u]=from;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(v==fa||cut[v]) continue;
getdist(v,u,w+g[i].w,from);
}
}
//写法一
LL calc(int u,int){
dis[id[tot=1]=u]=0,fom[u]=u;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(cut[v]) continue;
getdist(v,u,g[i].w,v);
}
sort(id+1,id+tot+1,cmp);
for(int i=1;i<=m;i++){
int k=q[i];LL res=0;
if(k<0) continue;
for(int L=1,R=tot;L<R;){
if(dis[id[L]]+dis[id[R]]<k) L++;
else if(dis[id[L]]+dis[id[R]]>k) R--;
else res+=fom[id[L]]!=fom[id[R]],L++;
if(res) break;
}
if(res) q[i]=-q[i];
}
return 19491001;
}
//写法二：O(n^2) 暴力
于是我们解决了这一题，这是 P3806 的代码实现。
0x01（P4178）
给定 $n,k$ 和一棵树，计算
$$\sum\limits_{i,j\leq n}[{\tt dist}(i,j)\leq k]$$
没有什么区别，就是这个 $\leq$，也可以双指针，注意写法：
template<int N> struct counter{
int c[N+10],u[N+10][2],tot;
counter():tot(0){memset(c,0,sizeof c);}
void insert(int k,int p){u[++tot][0]=k,u[tot][1]=p,c[p]+=k;}
int& operator[](int i){return c[i];}
void undo(int){c[u[tot][1]]-=u[tot][0],tot--;}
void rollback(){for(;tot>0;undo(1));}
};
LL calc(int u,int k){
dis[id[tot=1]=u]=0,fom[u]=u;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(cut[v]) continue;
getdist(v,u,g[i].w,v);
}
sort(id+1,id+tot+1,cmp);
for(int i=1;i<=tot;i++) c.insert(1,fom[id[i]]);
LL res=0;
for(int L=1,R=tot;L<=tot;L++){
while(dis[id[L]]+dis[id[R]]>k&&R>=1) c.undo(fom[id[R--]]);
if(dis[id[L]]+dis[id[R]]<=k) res+=R-c[fom[id[L]]];
//当前 [1,R] 可以和 L 配对，但要减掉和 L 同子树的点。
}
c.rollback();
return res;
}
0x02（P2634）
给定 $n$ 和一棵树，计算
$$\sum\limits_{i,j\leq n}[3|{\tt dist}(i,j)]$$
还是一样的，考虑算出 $c_0,c_1,c_2$ 表示一共有多少条路径长度模 $3$ 是 $0,1,2$。用容斥的写法（双指针没有单调性）。方案数为 $(c_0)^2+2c_1c_2$。
关于这个方案数，有时 $(i,j)$ 和 $(j,i)$ 会算两次，有时 $(i,i)$ 会混进答案（这会有 $n$ 个），看题决定写法。
原文地址：http://www.cnblogs.com/caijianhong/p/16863294.html
