点分治

点分治，又称淀粉质，淀粉脂。是用来解决树上路径问题。

1.例题引入

P3806 点分治板子

给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。

就是求无根树中长度为k的路径数目

暴力做法：考虑枚举每个点，每一次都统计距离路径。时间复杂度$O(n^2)$

我们假设一个点为根节点$rt$，把它先转化为有根树

考虑对每个路径进行统计，路径统计可以分为2类路径，一个路径是过当前点$rt$，一个路径是不过当前点$rt$。

这样分类是显然正确的，而且对于不经过$t$的路径，它们一定在$t$的某个子节点所构成的子树中。

对于前者，设$dis[u]$表示从节点$u$到根节点$rt$的路径长度，则$u$到$v$的路径长度就是$dis[u]+dis[v]$

对于后者，我们可以考虑重新统计子树，找到子树的根，让后再子树求第一类路径。

就是分治的思想，点分治途径中每一层所有递归都对点仅处理一次，即时间复杂度$O(T\times N)$ ，$T$即子树大小。

若树退化为一条链，那么$T=n$，总时间复杂度降为$O(n^2)$。那怎么选根节点呢？

我们观察时间复杂度，$N$是固定的，我们只需要让$T$平均小即可。

那么这个时候就要请出——树的重心

树的重心有一个性质，就是它的最大子树大小不大于整颗树大小的一半，也就是说刚好能满足我们即不能退化为链又能满足平均更小

我们可以先求树的重心，代码如下

void dfs(int u,int fa){
    //siz即子树大小，maxp即最大子树大小
    // sum即总节点数
    siz[u]=1;
    maxp[u]=0;
    for(auto e:adj[u]){
        int v=e.v,w=e.w;
        if(v==fa||vis[v]) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        maxp[u]=max(maxp[u],siz[v]);
    }
    maxp[u]=max(maxp[u],sum-siz[u]);
    //考虑与u相邻节点子树的大小
    if(maxp[u]<maxp[rt]) rt=u;
}

我们在分治的时候每次选取子树的重心为子树的树根进行处理，这样的$T$就不会超过$logN$层，故时间复杂度为$O(n\log n)$

回到本题，本题可以离线询问，并在分治中处理答案。

对于每一次处理子树，我们需要处理每个节点到$rt$的深度。

令$judge[dis]$表示在子树中是否存在某个点到$rt$距离为$dis$

离线询问用$query$数组记录。
若当前询问距离为$query[j]$
如果$judge[query[j]-rem[i]]=1$，那么表明存在这个点。则代表询问的路径存在，其实就是将子树内的节点进行配对，看是否有满足询问的条件。

配对完后继续下一个子树的处理。

记得查询完后清空judge，我们发现数组太长每次memset会炸时间，那么就考虑记录rem中出现的数，考虑用$s$数组维护出现个数，这样每一次就不用memset只需要遍历数组赋值就好了。

故代码如下

#include<bits/stdc++.h>
using namespace std;
const int MN=1e5+15;
const int INF=1e9;
int n,m,query[MN],sum,siz[MN],dis[MN],maxp[MN],rt;
int s[MN],top,rem[MN];
bool test[MN],judge[MN],vis[MN];
struct edge
{
    int v,w;
};
vector<edge> adj[MN];
void dfs(int u,int fa){
    //siz即子树大小，maxp即最大子树大小
    siz[u]=1;
    maxp[u]=0;
    for(auto e:adj[u]){
        int v=e.v,w=e.w;
        if(v==fa||vis[v]) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        maxp[u]=max(maxp[u],siz[v]);
    }
    maxp[u]=max(maxp[u],sum-siz[u]);
    //考虑与u相邻节点子树的大小
    if(maxp[u]<maxp[rt]) rt=u;
}

void getdis(int u,int fa){
    rem[++rem[0]]=dis[u];
    for(auto e:adj[u]){
        int v=e.v,w=e.w;
        if(v==fa||vis[v]) continue;
        dis[v]=dis[u]+w;
        getdis(v,u);
    }
}

void clac(int u){
    int p=0;
    for(auto e:adj[u]){
        int v=e.v,w=e.w;
        if(vis[v]) continue;
        rem[0]=0,dis[v]=w;
        getdis(v,u);//重新计算深度
        for(int i=rem[0];i>=1;i--){
            for(int j=1;j<=m;j++){
                if(query[j]>=rem[i]){
                    test[j]|=judge[query[j]-rem[i]];
                    //要特判是否大于rem[i]
                }
            }
        }
        for(int i=rem[0];i>=1;i--){
            s[++p]=rem[i];
            judge[rem[i]]=1;//记录距离出现过
        }
    }
    for(int i=1;i<=p;i++){
        judge[s[i]]=0;
    }
}

void solve(int u){
    vis[u]=1;//当前节点已经处理
    judge[0]=1;//初始化
    clac(u);//计算以当前节点为根的子树贡献
    for(auto e:adj[u]){
        int v=e.v,w=e.w;
        if(vis[v]) continue;
        sum=siz[v];
        maxp[rt=0]=INF;
        dfs(v,0);//找出子树重心
        solve(rt);//solve！
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    for(int i=1;i<=m;i++){
        cin>>query[i];
    }
    maxp[rt]=sum=n;
    dfs(1,0);
    solve(rt);

    for(int i=1;i<=m;i++){
        if(test[i]) cout<<"AYE\n";
        else cout<<"NAY\n";
    }
    return 0;
}

2.P4178 Tree

给定一棵 n个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。

我们发现这个题和上一道唯一一点不同在于这个题是小于等于。

当然我们可以和上一题一样算dis，但是在枚举路径的时候很麻烦。

我们考虑在一条合法路径上，路径上的点肯定都能满足条件贡献答案。

现在问题在于如何快速统计路径答案？题目要求是$len \le k$ ,那么我们可以考虑对求的的深度进行排序。

在处理出来$dis$数组后，我们可以利用其对子树节点进行排序，设处理出来后的节点数组为$scnt$，排序后可以考虑双指针，左右指针分别在数组一端，若$dis[scnt[l]]+dis[scnt[r]]>k$ 则缩小右指针
直到$dis[scnt[l]]+dis[scnt[r]]\le k$ 显然答案贡献为$r-l$，之后不断右移左指针直到相遇，这样的时间复杂度是$O(n)$。

但是这样会有一个问题，如果单个节点重复贡献，有没有这种情况发生？有的兄弟有的。

很丑，但大概是这么个意思，当计算clac(u,0)的时候，这个函数统计的是所有在u的分治区域内，距离之和<=k的点对。这其中包括了同一子树内的点对，这些点对虽然它们的路径可能在子树内部，但因为当前的根是u，所以在计算的时候，它们的路径会被错误地认为经过u。但实际上，这些点对应该属于该子树的内部问题，会在后续递归处理该子树时被正确计算。因此，为了避免重复计算，需要将这些情况减去。

如何解决？考虑容斥原理，很容易发现这种情况下每个节点的答案都会算至多2次（你不可能有好几个根节点吧…)，总的结果是当前根的所有可能点对，减去各个子树内部的情况。所以我们可以在$solve$函数中先统计完以$u$为根的答案，让后不更新深度，遍历子节点v时，计算v子树中节点到u的距离（初始化为w，即u到v的边权），并统计这些点对。这些点对属于同一子树，其路径不经过u，会被后续递归处理。此处减去以避免重复计数。

故代码如下

#include<bits/stdc++.h>
using namespace std;
const int MN=1e5+15,INF=1e9;
int n,m,siz[MN],maxp[MN],sum,dis[MN],rem[MN],rt,res;
bool vis[MN];
struct edge
{
    int v,w;
};
vector<edge> adj[MN];
bool cmp(int x,int y){
    return dis[x]<dis[y];
}
void dfs(int u,int fa){
    siz[u]=1;
    maxp[u]=0;
    for(auto e:adj[u]){
        int v=e.v,w=e.w;
        if(vis[v]||v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        maxp[u]=max(maxp[u],siz[v]);
    }
    maxp[u]=max(maxp[u],sum-siz[u]);
    if(maxp[u]<maxp[rt]) rt=u;
}

void getdis(int u,int fa){
    rem[++rem[0]]=u;
    for(auto e:adj[u]){
        int v=e.v,w=e.w;
        if(v==fa||vis[v]) continue;
        dis[v]=dis[u]+w;
        getdis(v,u);
    }
}

int clac(int u,int w){
    rem[0]=0;
    dis[u]=w;
    getdis(u,0);
    sort(rem+1,rem+rem[0]+1,cmp);
    int l=1,r=rem[0],ans=0;
    while (l<=r){
        if(dis[rem[l]]+dis[rem[r]]<=m){
            ans+=r-l;
            l++;
        }else r--;
    }
    return ans;
}

void solve(int u){
    vis[u]=1;
    res+=clac(u,0);
    for(auto e:adj[u]){
        int v=e.v,w=e.w;
        if(vis[v]) continue;
        res-=clac(v,w);
        sum=siz[v];
        rt=0;
        maxp[rt]=INF;
        dfs(v,u);
        solve(rt);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    cin>>m;
    maxp[rt]=sum=n;
    dfs(1,0);
    solve(rt);
    cout<<res;
    return 0;
}

3. P2664 树上游戏

lrb 有一棵树，树的每个节点有个颜色。给一个长度为$n$ 的颜色序列，定义$s(i,j)$ 为$i$ 到$j$ 的颜色数量。以及

$$sum_i=\sum_{j=1}^n s(i, j)$$

求出所有的$sum_i$

求单个路径上的颜色数量，我们可以像之前的题一样在$rem$数组中维护颜色信息，但是问题出现在了合并答案，合并信息很难合并因为rem数组中的数据满足$DFS$序，但是仅凭dfs序无法知道是否处于同一路径。

我们考虑能否转化$sum$，对于$sum$来说影响他的只有经过边的点颜色在不同的时候有贡献，并且统计的颜色数量是要求不相同的。

设$cnt[j]$表示颜色为$j$的情况下，以$i$为端点包含$j$颜色的路径数量，我们显然可以得到

$$sum=\sum\limits_{j\in color(u,v)}{cnt_j}$$

其中color就是在路径上是否有这个颜色，如果没有默认我们置$cnt[j]=0$。

显然我们可以在dfs子树是可以统计以rt为根节点到子树的答案。时间复杂度$O(n\log n)$

但是跨子树的答案如何统计？显然这个时候$rt$根节点就是路径的拐点。

考虑对当前根节点的一个字节点$d$，$d$的子树中任取一个点为$v$

考虑$(u,v)$路径上出现的颜色，数量设为$now$，$u$除了$d$以外其他子树的总大小为$siz1$，那么贡献即为$num\times siz1$

考虑没有出现过的颜色$j$，它的贡献来自于$u$除了$d$以外其他所有子树的$cnt_j$，那么这部分的答案就是$\sum\limits_{j\notin (u,v)}{cnt_j}$

代码也就呼之欲出了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MN=1e5+15,INF=1e9;
// sum就是题面意思的sum答案,summ即节点总数
// visc即表示这个颜色已经访问过了
// cnt即子树对当前节点的贡献,下表应为颜色。siz即子树大小
ll n,c[MN];
int vis[MN];
ll cnt[MN],siz[MN],sum,summ,ans[MN],visc[MN];

vector<int> adj[MN];
ll rt,maxp[MN];
void dfs(int u,int fa){
    siz[u]=1;
    maxp[u]=0;
    for(auto v:adj[u]){
        if(v==fa||vis[v]) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        maxp[u]=max(maxp[u],siz[v]);
    }
    maxp[u]=max(maxp[u],summ-siz[u]);
    if(maxp[u]<maxp[rt]){
        rt=u;
    }
}

void getdis(int u,int fa,int now){
    // now即当前路径（不含u）的颜色数
    siz[u]=1;
    if(!visc[c[u]]){
        sum-=cnt[c[u]];
        now++;
    }
    visc[c[u]]++;
    ans[u]+=sum+now*siz[rt];
    // 前面是其他颜色到当前节点的贡献
    // 后面是跨rt（就是跨子树,相当于rt就是路径拐点）的贡献
    for(auto v:adj[u]){
        if(v==fa||vis[v]) continue;
        getdis(v,u,now);
        siz[u]+=siz[v];
    }
    visc[c[u]]--;
    if(!visc[c[u]]){
        sum+=cnt[c[u]];// 回溯防止处理下一个子树出问题
    }
}

void getcnt(int u,int fa){
    if(!visc[c[u]]){
        // 统计答案
        cnt[c[u]]+=siz[u];
        sum+=siz[u];
    }
    visc[c[u]]++;
    for(auto v:adj[u]){
        if(v==fa||vis[v]) continue;
        getcnt(v,u);
    }
    visc[c[u]]--;
}

void clear(int u,int fa,int now){
    if(!visc[c[u]]){
        now++;
    }
    visc[c[u]]++;
    ans[u]-=now;//减去重复贡献
    ans[rt]+=now;//加上贡献
    for(auto v:adj[u]){
        if(v==fa||vis[v]) continue;
        clear(v,u,now);
    }
    visc[c[u]]--;
    cnt[c[u]]=0;
}

void clearcnt(int u,int fa){
    cnt[c[u]]=0;
    for(auto v:adj[u]){
        if(v==fa||vis[v]) continue;
        clearcnt(v,u);
    }
}

void solve(int u){
    vis[u]=1;
    ans[u]++;
    rt=u;
    siz[u]=sum=cnt[c[u]]=1;
    visc[c[u]]++;
    for(auto v:adj[u]){
        if(vis[v]) continue;
        getdis(v,u,0);
        getcnt(v,u);
        siz[u]+=siz[v];
        cnt[c[u]]+=siz[v];
        sum+=siz[v];
    }
    clearcnt(u,0);
    //逆序处理是为了保证所有子树对路径的贡献都被覆盖
    siz[u]=sum=cnt[c[u]]=1;
    for(int i=adj[u].size()-1;i>=0;i--){
        int v=adj[u][i];
        if(vis[v]) continue;
        getdis(v,u,0);
        getcnt(v,u);
        siz[u]+=siz[v];
        cnt[c[u]]+=siz[v];
        sum+=siz[v];
    }
    visc[c[u]]--;
    clear(u,0,0);//清理并统计2次的答案
    //继续分治
    for(auto v:adj[u]){
        if(vis[v]) continue;
        summ=siz[v];
        rt=0;
        maxp[rt]=INF;
        dfs(v,u);
        solve(rt);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    summ=n;
    maxp[rt]=n+1;
    dfs(1,0);
    solve(rt);
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

3.总结

在面对不同点分治题型的时候，要设计不同的clac函数。