点分治

以下讲解都以为例

点分治，是一个很简单非常常见的数据结构

她是一种处理树上路径问题的工具，举个栗子：

给定一棵树和一个整数k，求树上边数等于k的路径有多少条

当树的节点数比较多的时候，就不能使用暴力了，我该怎么办

就要用点分治

原理

如图，我们在这棵树上选出一个root，那路径一共有三种情况：

1.在红子树中

2.在黑子树中

3.一半在红子树，一半在黑子树，要过root，拼成一条完整的路径

分类讨论，不存在的qaq，或许这辈子我也不会分类讨论

仔细想一下，实际情况1,2都珂以看做情况3，如图将答案中一点变成root，就成了情况3

好的上面只是思想，好像很虚空

我们需要实现

选根

选根的过程实际就是一个树形dp

选root是非常重要的，选不好会使复杂度爆炸

想想会发现这个根最好是树的重心

所以一个简单的树形dp就能搞定

inline void getroot(register int u,register int fa){    size[u]=1;    int num=0;    for(register int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(v==fa||vis[v])            continue;        getroot(v,u);        size[u]+=size[v];        num=Max(num,size[v]);    }    num=Max(num,sizee-size[u]);    if(mx>num)        mx=num,rt=u;}

因为之后的分治过程还需要对子树单独找重心，所以代码中有vis，但是开始对整棵树无影响

分治

这才是点分治的精华qaq

根据代码来理解

inline ll devide(register int u){    ll res=solve(u,0); //把当前节点的答案加上去     vis[u]=true; //把节点标记，防止陷入死循环     int totsize=sizee;    for(register int i=head[u];i;i=e[i].next)    {        //分别处理每一棵子树         int v=e[i].to;        if(vis[v])            continue;        res-=solve(v,e[i].v); //容斥原理，下面说         rt=0,sizee=size[v]>size[u]?totsize-size[u]:size[v],mx=inf;        //把所有信息更新，递归进子树找重心，并继续分治         getroot(v,0);        res+=devide(rt);    }    return res;}

大部分都应该比较好理解，除了ans-=slove(v,1）这句

我们先看一种情况：

在路径A->Root和B->Root合并时，这种情况显然是不合法的

所以要减去一些路径

完整代码

#include 
    
     #define N 50005#define ll long long#define inf 0x3f3f3f3fusing namespace std;inline int read(){    register int x=0,f=1;register char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();    return x*f;}inline void write(register ll x){    if(!x)putchar('0');if(x<0)x=-x,putchar('-');    static int sta[36];int tot=0;    while(x)sta[tot++]=x%10,x/=10;    while(tot)putchar(sta[--tot]+48);}inline int Max(register int a,register int b){    return a>b?a:b;}struct node{    int to,next,v;}e[N<<1];int head[N],tot=0;inline void add(register int u,register int v,register int k){    e[++tot]=(node){v,head[u],k};    head[u]=tot;}int n,k;int size[N];int rt,sizee,mx;bool vis[N];ll ans=0;ll d[N],q[N],l,r;inline void getroot(register int u,register int fa){    size[u]=1;    int num=0;    for(register int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(v==fa||vis[v])            continue;        getroot(v,u);        size[u]+=size[v];        num=Max(num,size[v]);    }    num=Max(num,sizee-size[u]);    if(mx>num)        mx=num,rt=u;}inline void getdis(register int u,register int fa){    q[++r]=d[u];    for(register int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(v==fa||vis[v])            continue;        d[v]=d[u]+e[i].v;        getdis(v,u);    }}inline ll solve(register int u,register int val){    r=0;    d[u]=val;    getdis(u,0);    ll sum=0;    l=1;    sort(q+1,q+r+1);    while(l
     
      size[u]?totsize-size[u]:size[v],mx=inf;        getroot(v,0);        res+=devide(rt);    }    return res;}int main(){    n=read();    for(register int i=1;i
     
    

动态点分治

一般，点分治只能处理静态的问题

但是，毒瘤的出题人加上了修改操作该怎么办qaq？

每修改一次做一次点分治？复杂度直接飞天

考虑一下，修改操作修改的是点权（不是树的结构，树的结构的话请找lct同学）

树的重心不会改变

先给出点分树的定义qaq：

点分治时每一层的重心连出的一个深度为logn的树

我们假设已经处理完了所有经过点1的路径，然后递归进子树继续点分，那么实际上原树被拆成了这么两棵树，两个重心分别为2和6

那么把第一层的重心和第二层的重心给连接起来（用红色表示）

然后我们继续进行点分，我们已经把经过点2和点6的所有路径都已经处理完了，那么子树又会继续拆分

然后因为子树大小只有1，重心就是他们自己，继续和上一层的重心连边

一棵点分树就这样建好了

在代码实现上实际只有一点点小的变动

inline void devide(register int u){    vis[u]=true;     int totsize=sizee;    for(register int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v])            continue;        rt=0,sizee=size[v]>size[u]?totsize-size[u]:size[v],mx=inf;        getroot(v,0);        fa[rt]=u;        devide(rt);    }    return res;}

那么每一次修改，只要在点分树里不断往上跳，就能够维护整棵树的信息了

好像十分抽象，结合一道例题来讲或许会更好

我们以作为模板来说一下动态点分治

题意简介：

给你了一棵树，每个节点有个权值（0/1），一开始所有点全是0

有一下两种操作：

C（Change）i，把i这个节点的权值取反

G（Game）查询距离最远的两个权值为0的点的距离

题解先咕咕咕