点分治略解

Dispwnl

2018-07-20 16:53:26

Algo. & Theory

我给你讲，淀粉质可好吃了，真的

点分治，是一种处理树上路径问题的工具，举个例子：

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

做法很简单，枚举不同的两个点，然后dfs算出ta们间的距离，统计一下就行了

大概是O(n^3)的复杂度

布星啊n大一点就搞不了了

那找个根，求出每个点到根的距离，然后枚举两个点，求lca，简单加减一下就行了

大概是O(n^2logn)的复杂度...？

还是布星啊n还要大，几万的数据就搞不了了怎么这么多事

考虑一下形成路径的情况，假设一条满足条件的路径经过点x，那么这条路径在x的一个子树里（以x为端点）或者在x的两个不同的子树里，如图：

一个好的想法是找到一个根，然后dfs遍历ta子树中的每个点，依次处理每个点的子树答案

如图，假设我们选出一个根Root，那么答案路径肯定是要么被一个子树所包含，要么就是跨过Root，在黑子树中选择一部分路径，在红子树中选择一部分路径，然后从Root处拼起来形成一条答案路径

两种情况诶...分类讨论？

分类讨论不会写的，这辈子都不可能写分类讨论的

仔细想一下，发现情况1（被一个子树包含）中，答案路径上的一点变为根Root，就成了情况2（在两棵子树中）

如图，Root为根的子树中存在答案（蓝色实边路径），可以看成以Root2为根的两棵子树存在答案，所以只用处理情况2就行了，可以用分治的方法，这应该是点分治的基本原理

先从找好一个根开始

首先根不能随便选，选根不同会影下面遍历的效率的，如图：

显然选y为根比选x为根不优，选x最多递归2层，选y最多递归4层

显然可以发现找树的重心（重心所有的子树的大小都不超过整个树大小的一半）是最优的

我们可以根据每个点子树大小确定根，当根的最大的子树最小时肯定是重心

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

void GET_ROOT(int x,int fa)//x为当前点，fa为父亲节点
{
    f[x]=0,siz[x]=1;//f表示这个点最大子树的大小，siz是这个点子树大小的和
    for(int i=h[x];i;i=c[i].x)//枚举儿子
      {
        int y=c[i].y;
        if(use[y]||y==fa) continue;//use表示之前遍历过了，这里没啥用
        GET_ROOT(y,x);//往下遍历
        f[x]=max(f[x],siz[y]);//更新f
        siz[x]+=siz[y];
      }
    f[x]=max(f[x],Siz-siz[x]);//Siz表示在现在这棵子树中点的总数，开始时Siz=n，除了枚举的儿子所在的子树外，还有一棵子树是上面的那一堆，容斥原理
    if(f[x]<f[rt]) rt=x;//更新root
}

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

找到根了，现在我们可以dfs一遍重心的子树，求出重心到子树各个点的距离

然后可以枚举子树里的两个点，如果两个点到重心的距离和为k（题目要找距离为k的点对），那么答案+1

这是第二种情况，第一种情况就让距离根为k的点跟重心配对就行了，因为重心到重心的距离为0

如何统计答案呢？

肯定不能直接枚举啊...n^2的复杂度啊喂

考虑枚举一个点，另一个点可以通过二分来求解，sort一下让距离有序，这样要找距离为k-枚举点的距离的点的个数，因为相同距离的点现在是连续的，所以可以二分出左右边界l,r，ans+=r-l+1

int look(int l,int x)//找左边界
{
    int ans=0,r=cnt;
    while(l<=r)
    {
        int mid(l+r>>1);
        if(d[mid]<x) l=mid+1;
        else ans=mid,r=mid-1;
    }
    return ans;
}
int look2(int l,int x)//找右边界
{
    int ans=0,r=cnt;
    while(l<=r)
    {
        int mid(l+r>>1);
        if(d[mid]<=x) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
void GET_NUM(int x,int fa,int D)//求重心到子树每个点的距离
{
    for(int i=h[x];i;i=c[i].x)
      {
        int y=c[i].y;
        if(use[y]||y==fa) continue;
        d[++cnt]=D+c[i].dis;
        GET_NUM(y,x,d[cnt]);
      }
}
int GET_ANS(int x)//求答案
{
    d[cnt=1]=0;
    GET_NUM(x,0,0);
    sort(d+1,d+1+cnt);//排下序
    int l=1,ans=0;
    while(l<cnt&&d[l]+d[cnt]<k) ++l;
    while(l<cnt&&k-d[l]>=d[l])
    {
        int D1(look(l+1,k-d[l])),D2(look2(l+1,k-d[l]));//枚举一个点，因为和是k，所以可以直接求出另一点到重心的距离，二分一下就行了
        if(D2>=D1) ans+=D2-D1+1;
        ++l;
    }
    return ans;
}
void dfs(int x)//分治函数
{
    use[x]=1,ans+=GET_ANS(x);//统计这个点的答案
    for(int i=h[x];i;i=c[i].x)
      {
        int y=c[i].y;
        if(use[y]) continue;//防止找父亲
        Siz=siz[y],rt=0;//下一个重心肯定在当前点的子树里
        GET_ROOT(y,x),dfs(rt);//找下一个重心
      }
}

也可以通过移动两个指针来实现只要不是枚举两个点就行了

这样我们就快乐的A掉了这道题

了吗？

求一遍发现答案不对诶...似乎多了几种情况？如图：

假设k=4，图中A到Root的距离为2，B到Root的距离为2，合起来是4，这时候答案+1，但是显然这两个点最短路径不是4

这是因为ta们在同一子树中，到重心的路径有重叠部分

处理方法：

1.可以求距离的时候把点染色，不同子树不同颜色，那么求答案的时候就得枚举每个符合答案的每个点看是否不在一个子树里

2.可以求当前点儿子的答案，统计儿子答案时各个点的距离加上儿子到根的距离，即把符合在一个子树条件的情况统计出来，最后这个点的答案减去儿子答案就行了

图中求Root儿子son的答案，因为加上儿子到重心的距离，所以A的距离还是2，B的距离还是2，这样就把不符合条件的答案去掉了

int GET_ANS(int x,int D)//改一下这里就行了
{
    d[cnt=1]=D;
    GET_NUM(x,0,D);
    sort(d+1,d+1+cnt);
    int l=1,ans=0;
    while(l<cnt&&d[l]+d[cnt]<k) ++l;
    while(l<cnt&&k-d[l]>=d[l])
    {
        int D1(look(l+1,k-d[l])),D2(look2(l+1,k-d[l]));
        if(D2>=D1) ans+=D2-D1+1;
        ++l;
    }
    return ans;
}
void dfs(int x)//分治函数也改一下
{
    use[x]=1,ans+=GET_ANS(x,0);//当前点答案
    for(int i=h[x];i;i=c[i].x)
      {
        int y=c[i].y;
        if(use[y]) continue;//防止找父亲
        ans-=GET_ANS(y,1);//去掉满足在一个子树条件的不合法答案
        Siz=siz[y],rt=0;
        GET_ROOT(y,x),dfs(rt);//找下一个重心
      }
}

这样答案就对了写丑了就不怪我了

每次处理找树的重心，保证递归层数不超过logn，dfs求距离复杂度是O(n)，这里处理答案是logn，所以这个题总复杂度是O(nlog^2n)的...？反正过几万的数据是绰绰有余的（逃

补充：经Aufun大爷嘲讽教导后，因为有的题可以用桶排序，所以复杂度可以降到O(logn)

当然有的题桶开不下必须sort了QAQ我一直用sort竟然没被卡

模板题（雾）

模板题（求距离为k的点对个数）

求小于k的点对个数

权值和为k，求最小边数

最后一题题解