点分治总结（个人笔记）
柒葉灬
2018-12-19 14:54:46
# 点分治。
-----
## 基础
首先得知道什么是点分治，点分治就是利用每次用$O(n\times K)$计算一个块内的贡献，每一次将块至少缩小一半（树上重心，链上中点）来达到递归次数不超过$logn$次，从而达到总复杂度不超过$O(nlogn\times K)$的算法。
#### 用一个实际栗子（模板题目）说明一下。
>题目大意：给定一棵$n$节点的树，问长度不超过$K$的路径的个数。
如果我们假设每条路径**必须穿过根**，
那么用$O(nlogn)$的时间内就能算出来了，
把每个点到根的路径长度算出来，排序之后就可以查找了。
还剩下不经过根的点，把每个儿子所在的子树全部都这样算一遍，
这样的算法只能过**完全二叉树**的情况。
剩下来要做的就是把树变成完全二叉树，
具体做法是：每次找当前子树的**重心**，
保证递归次数不超过$logn$次。
知道这样子的话就可以差不多A掉这道题目了。
（需要注意的是：要把来自同一个子树的路径给删掉（容斥））
### 模板代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void tomax(T &a,T b){if(a<b)a=b;}
const int maxn=3e4+5;
int n,K,x,y,z,ans;
int tot,head[maxn],to[maxn*2],nxt[maxn*2],w[maxn*2];
void add_edge(int u,int v,int c){
to[++tot]=v;
nxt[tot]=head[u];
w[tot]=c;
head[u]=tot;
}
int Siz,rt,sz[maxn],mx[maxn];
int id,res[maxn];
bool vis[maxn];//已经处理过了
void clear(){
tot=0;
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
ans=0;
}
void dfs_root(int f,int x){
mx[x]=0;
sz[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f||vis[y])continue;
dfs_root(x,y);
tomax(mx[x],sz[y]);
sz[x]+=sz[y];
}
tomax(mx[x],Siz-sz[x]);
if(mx[x]<mx[rt]||rt==0)rt=x;
}
void dfs_dis(int f,int x,int Dis){
res[++id]=Dis;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f||vis[y])continue;
dfs_dis(x,y,Dis+w[i]);
}
}
int solve_ans(int x,int D){
id=0;
dfs_dis(0,x,D);
sort(res+1,res+1+id);
int l=1,r=id,ans=0;
while(l<r){
while(l<r && res[l]+res[r]>K)r--;
ans+=r-l;
l++;
}
return ans;
}
void dfs(int x){
vis[x]=1;
ans+=solve_ans(x,0);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(vis[y])continue;
ans-=solve_ans(y,w[i]);
rt=0;
Siz=sz[y];
dfs_root(x,y);
dfs(rt);
}
}
int main(){
while(~scanf("%d%d",&n,&K),n!=0&&K!=0){
clear();
for(int i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z);
add_edge(y,x,z);
}
Siz=n;rt=0;
dfs_root(0,1);
dfs(rt);
printf("%d\n",ans);
}
return 0;
}
```
-----
然而，有些题目不适合容斥写，
比如说不问你方案个数了，是最值问题，那么就不能这么写了。
其实点分治的板子还有另一种，逐个Query后再Update。
具体代码就像下面这样：
```cpp
void add(int x){
/*
这里写修改的信息，
一般如果是数组不清空的话，需要多传入top
防止2条路径来自不同的块
*/
}
void calc(int x){
/*
这里写计算贡献
同样记得如果数组不清空，多传入top
*/
}
void dfs_update(int f,int x){
add(x);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f||vis[y])continue;
dfs_update(x,y);
}
}
void dfs_query(int f,int x){
calc(x);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f||vis[y])continue;
dfs_query(x,y);
}
}
void solve_ans(int x){
add(x);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(vis[y])continue;
dfs_query(x,y);
dfs_update(x,y);
}
}
```
-------
## 进阶
### 动态点分治
动态点分治只要在上面的dfs函数里面多加一点东西就可以了。
```cpp
void dfs(int f,int x){
vis[x]=1;
fa[x]=f;
ans+=solve_ans(x,0);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(vis[y])continue;
ans-=solve_ans(y,w[i]);
rt=0;
Siz=sz[y];
dfs_root(x,y);
dfs(rt);
}
}
```
不同的地方：
```cpp
fa[x]=f;
```
~~还是用例题来说~~
[HDU4918 Query On the subtree](http://acm.hdu.edu.cn/showproblem.php?pid=4918)
需要维护每个点到重心的贡献（动态开线段树），
而我们之前已经通过找重心的方法来使新树不超过$logn$层了，
所以修改和查询的时候不会访问超过$logn$个重心
注意修改的时候贡献来自同一个子树的情况，容斥掉，
多开$n$棵线段树，维护到父亲重心的信息，
每次查询减掉就可以了，复杂度$O(nlog^2n)$。
#### 栗子题目的代码：
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug(x) cerr<<"\t DEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e5+5,maxm=2e7+5;
int n,q,x,y,A[maxn];
char c;
int id,head[maxn],to[maxn*2],nxt[maxn*2];
void add_edge(int u,int v){
to[++id]=v;
nxt[id]=head[u];
head[u]=id;
}
int Fa[maxn],dep[maxn],top[maxn],son[maxn],Sz[maxn];
void dfs1(int f,int x){
Fa[x]=f;
dep[x]=dep[f]+1;
Sz[x]=1;
son[x]=0;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f)continue;
dfs1(x,y);
Sz[x]+=Sz[y];
if(Sz[son[x]]<Sz[y])son[x]=y;
}
}
void dfs2(int Top,int f,int x){
top[x]=Top;
if(son[x])dfs2(Top,x,son[x]);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=f&&to[i]!=son[x])
dfs2(to[i],x,to[i]);
}
int LCA(int a,int b){
while(top[a]!=top[b]){
if(dep[top[a]]>dep[top[b]])a=Fa[top[a]];
else b=Fa[top[b]];
}
return dep[a]<dep[b]?a:b;
}
int Dis(int a,int b){
return dep[a]+dep[b]-dep[LCA(a,b)]*2;
}
int tot,rt[maxn*2],lson[maxm],rson[maxm],sum[maxm];
void update(int &rt,int l,int r,int x,int num){
if(!rt)rt=++tot;
sum[rt]+=num;
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)update(lson[rt],l,mid,x,num);
else update(rson[rt],mid+1,r,x,num);
}
int Query(int rt,int l,int r,int x){
if(!rt||x==r)return sum[rt];
int mid=(l+r)>>1;
if(x<=mid)return Query(lson[rt],l,mid,x);
else return sum[lson[rt]]+Query(rson[rt],mid+1,r,x);
}
int root,Siz,fa[maxn],sz[maxn],mx[maxn];
bool vis[maxn];
void dfs_root(int f,int x){
sz[x]=1;mx[x]=0;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f||vis[y])continue;
dfs_root(x,y);
mx[x]=max(mx[x],sz[y]);
sz[x]+=sz[y];
}
mx[x]=max(mx[x],Siz-sz[x]);
if(mx[x]<mx[root]||root==0)root=x;
}
void dfs(int f,int x){
fa[x]=f;
vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(vis[y])continue;
Siz=sz[y];
root=0;
dfs_root(x,y);
dfs(x,root);
}
}
void add(int x,int pos){
update(rt[x],0,n,0,pos);
for(int i=x;fa[i];i=fa[i]){
int Dep=Dis(x,fa[i]);
update(rt[fa[i]],0,n,Dep,pos);
update(rt[i+n],0,n,Dep,pos);
}
}
int query(int x,int K){
int res=Query(rt[x],0,n,K);
for(int i=x;fa[i];i=fa[i]){
int Dep=Dis(x,fa[i]);
if(K-Dep<0)continue;
res+=Query(rt[fa[i]],0,n,K-Dep);
res-=Query(rt[i+n],0,n,K-Dep);
}
return res;
}
void clear(){
for(int i=1;i<=tot;i++)
lson[i]=rson[i]=sum[i]=0;
tot=0;
id=0;
root=0;
memset(rt,0,sizeof(rt));
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
}
int main(){
while(scanf("%d%d",&n,&q)!=EOF){
clear();
for(int i=1;i<=n;i++)
scanf("%d",&A[i]);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
dfs1(0,1);dfs2(1,0,1);
Siz=n;dfs_root(0,1);dfs(0,root);
for(int i=1;i<=n;i++)
add(i,A[i]);
while(q--){
scanf("%s%d%d",&c,&x,&y);
if(c=='?')printf("%d\n",query(x,y));
else {
add(x,y-A[x]);
A[x]=y;
}
}
}
return 0;
}
```
---------
## 技巧
- 先想暴力，如果想到的暴力可以过**二叉树**，那么尝试套用点分治。
- 考虑把每个点的信息用路径的方式来表达。（专题O题）
- 学会活用点分治，不要硬套板子。（专题F题）
- 想暴力尽量往$O(n^2)$的地方想。（专题I题）每个节点不接受父亲的信息，每个节点都要遍历一次所有子树。