浅谈点分治

学习点分治这个算法也有一个多星期了，期间也看了很多大佬的博客，其中@粉兔大佬对我的帮助非常大，建议想要深度学习这个算法的同学去看看他的博客，他对点分治的理解比我透彻许多，我这篇博客里也只是简单分析一下点分治的实现原理以及这样做为什么是正确的。

【算法学习】点分治——粉兔

【点分治算法步骤】

　　1.找根

　　为什么要找根呢？因为在分治过程中，从根节点去遍历全图和从叶子节点去遍历全图显然是两个量级的复杂度，从根节点遍历的时间复杂度大概在logn，根节点遍历最优性的证明网上很容易找到，我这里就不在赘述。

　　那么怎么去找根节点呢？——树上DP

inline void findrt(int u,int fa){
    siz[u]=1;dp[u]=0;
    for(int i=0;i<G[u].size();i++){
        node v=G[u][i];
        if(v.to==fa||vis[v.to])continue;
        findrt(v.to,u);
        siz[u]+=siz[v.to];
        dp[u]=max(dp[u],siz[v.to]);
    }
    dp[u]=max(dp[u],sum-siz[u]);
    if(dp[u]<dp[rt])rt=u;
}

　　2.分治——对每个子树的“根”分治计算答案

　　其实这里就是一个树的遍历过程，只不过只是对每个子树的根进行遍历；

inline void solve(int u){
    vis[u]=1;
    calc(u,0,0);
    ll totsz=sum;
    //puts("444");
    for(int i=0;i<G[u].size();i++){
        node v=G[u][i];
        if(vis[v.to])continue;
        calc(v.to,v.cost,1);
        rt=0;dp[0]=n;
        sum=siz[v.to]>siz[u]?totsz-siz[u]:siz[v.to];
        findrt(v.to,u);
        solve(rt);
    }
}

　　3.calc函数——计算你所需要的答案

　　这个函数就是看题目来写了

inline void calc(int u,ll c,int flag){
    tot=0;dis[u]=c;
    getdis(u,0);
    /*for(int i=1;i<tot;i++){
        for(int j=i+1;j<=tot;j++){
            if(!flag)ans[rev[i]+rev[j]]++;
            else ans[rev[i]+rev[j]]--;
        }
    }这段就是计算你所需要的东西了*/
}

　　4.计算子树节点到当前根的距离

inline void getdis(int u,int fa){
    rev[++tot]=dis[u];
    for(int i=0;i<G[u].size();i++){
        node v=G[u][i];
        if(v.to==fa||vis[v.to])continue;
        dis[v.to]=dis[u]+v.cost;
        getdis(v.to,u);
    }
}

【例题】

　　洛谷P4178 Tree

　　题意简述：n个点，n-1条边，形成一棵树，问有多少简单路径距离小于等于k的点对。

　　读者可以按照我之前讲的顺序来思考一下这道题。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
const int MAXN = 4e4+10;
const double EPS = 1e-12;

int n,k,rt,tot;
ll sum,ans;
ll rev[MAXN],dis[MAXN],dp[MAXN],siz[MAXN];
bool vis[MAXN];
struct node{
    int to;
    ll cost;
};
vector<node>G[MAXN];

inline void findrt(int u,int fa){
    //printf("########## %d  %d
",u,rt);
    siz[u]=1;dp[u]=0;
    for(int i=0;i<G[u].size();i++){
        node v=G[u][i];
        if(v.to==fa||vis[v.to]) continue;
        findrt(v.to,u);
        siz[u]+=siz[v.to],dp[u]=max(dp[u],siz[v.to]);
    }
    dp[u]=max(dp[u],sum-siz[u]);
    if(dp[u]<dp[rt])rt=u;
}

inline void getdis(int u,int fa){
    rev[++tot]=dis[u];
    for(int i=0;i<G[u].size();i++){
        node v=G[u][i];
        if(v.to==fa||vis[v.to])continue;
        dis[v.to]=dis[u]+v.cost;
        getdis(v.to,u);
    }
}

inline ll calc(int x,int c){
    tot=0;
    dis[x]=c;getdis(x,0);
    sort(rev+1,rev+tot+1);
    int l=1,r=tot;
    ll ANS=0;
    while(l<=r){
        if(rev[l]+rev[r]<=k){
            ANS+=r-l;
            l++;
        }
        else r--;
    }
    return ANS;
}

inline void solve(int u){
    vis[u]=1;
    ans+=calc(u,0);
    ll totsz=sum;
    for(int i=0;i<G[u].size();i++){
        node v=G[u][i];
        if(vis[v.to])continue;
        ans-=calc(v.to,v.cost);
        sum=siz[v.to]>siz[u]?totsz-siz[u]:siz[v.to];
        dp[0]=n,rt=0;
        findrt(v.to,u);
        //printf("########## %d  %d
",u,rt);
        solve(rt);
    }
    //printf("**********%d   %lld
",u,ans);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        G[x].push_back(node{y,z});
        G[y].push_back(node{x,z});
    }
    scanf("%d",&k);
    rt=0,dp[0]=sum=n;
    findrt(1,0);
    //printf("*****%d
",rt);
    solve(rt);
    printf("%lld
",ans);
    return 0;
}

【总结】

点分治是经典的分治思想在树上的应用，其精髓在于把无根树平均地分割成若干互不影响的子问题求解，极大降低了时间复杂度，是一种巧妙的暴力。