点分治

OI知识 树

参考资料：洛谷日报2018,8 #23 [守望] 点分治略解

一、主要用途

处理树上有关路径的问题，如：求一棵树上长度为 k 的路径有多少条。

二、思想

分治 （毫无疑问）。

分析：

对于树上的每一个点，一条路径有两种情况
1. 经过这个点
2. 在这个点的子树上

那么对于情况 1，我们可以 dfs 算出它所有子树上的节点到它的距离，从而求出长度为 k 的路径数量；
而对于情况 2，利用分治的思想，我们可以对当前节点的每一棵子树进行对情况 1 的处理，这样递归下去，最终就可以求得答案。

三、具体实现

大体分为三个部分

1.找当前树的重心 u (为了使递归次数尽量的少)
2.求出 u 的子树中的所有节点到 u 的距离
3.统计, 计算出符合条件的路径数量
4.分治, 对 u 的每棵子树进行操作 1

四、代码

找重心

void get_rt(int u,int f){
    int maxn=0;size[u]=1;           // 这里 size 必须先初始化为 1 
    for(int i=lst[u];i;i=nxt[i]){
        int v=to[i];
        if(v==fa||vis[v]) continue;     // 由于要多次找重心，所以要避开已经扫过的点
        get_rt(v,u);
        size[u]+=size[v];
        maxn=max(maxn,size[v]);
    }
    maxn=max(maxn,num-size[u]);
    if(maxn<maxp){
        maxp=maxn;
        rt=u;
    }

求距离

void get_dis(int u,int fa,int dis){
    if(dis>k) return;
    bot[++bot[0]]=dis;      // 先存起来，以便等下统计
    for(int i=lst[u];i;i=nxt[i]){
        int v=to[i];
        if(v==fa||vis[v]) continue;
        get_dis(v,u,dis+len[i]);
    ｝
}

统计

void calc(int u){
    t=0;
    tms[0]=1;       // 到节点 u 不同长度的点出现的次数
    for(int i=lst[u];i;i=nxt[i]){
        int v=to[i];
        if(vis[v])continue;
        bot[0]=0;   // 初始化，清零
        get_dis(v,u,len[i],1);
        for(int j=1;j<=bot[0];j++)
            ans+=tms[k-bot[j]];     // 统计
        for(int j=1;j<=bot[0];j++){
            q[++t]=b1[j];       
            tms[bot[j]]++;      // 统计完一棵子树后再把它存进去，防止统计到同一子树中的节点
        }
    }
    for(int i=1;i<=t;i++)       
        tms[q[i]]=0;        // 由于 k 可能比较大，用 memset 有可能 TLE，所以用一个队列存修改了的点，最后再一一清零
}

五、练习

模版1
模板2（求距离为k的点对个数）
求小于k的点对个数
权值和为k，求最小边数