点分治学习小记

点分治

通过一道题，发现了点分治这个算法，现在学习一下并做一个总结。

预备知识

树的直径：树上最长的一条路径
- 求法：两次DFS。
  - 第一次DFS随意定根，找到离根最远的点。
  - 第二次DFS以最远点为根，再找到离根最远的地方，路径长度就是树的直径。
- 证明：脑补可得。
树的重心：找到一个点，其所有子树中最大的子树节点最少。（这个点作为根时最大的子树节点个数最少）
- 优点：删去重心之后，生成的多棵树尽可能平衡。
- 代码

int sz[MAXN],rt,n,mx[MAXN];
void dfs(int x,int fa)
{
    sz[x]=1,mx[x]=0;
    for (int i=head[x];i;i=e[i].next)
    {
        int v=e[i].to;
        if (v==fa) continue;
        dfs(v,x);
        sz[x]+=sz[v];
        mx[x]=max(mx[x],sz[v]);
    }
    mx[x]=max(mx[x],n-sz[x]);
    if (mx[x]<mx[rt] || (mx[x]==mx[rt] && x<rt))
        rt=x;
}

其中rt是树的重心，mx[rt]是树的重量。

点分治

点分治是在树上进行分治的一种方法：根据点的性质来进行“分”，再“治”。

如何“分”

分治的思想是为了减少计算的量级。
根据这一思想，我们选择树的重心为根，可以保证每次子树的大小不超过 $\frac{2}{n}$ ，递归深度就能保证递归深度保持在 $l o g n$ 级别，保证不发生退化，高效处理。

如何“治”

我们发现了一个问题：在计算当前子树的答案时，有一些“完全被子树的子树包含”，也就是答案与当前子树的根无关的贡献，在进行下一步递归时，会被计算到。
如何处理这个问题呢？运用容斥的思想，每次减去所有“仅与子树有关”的答案即可。

例1 POJ1741 Tree

我是题目链接

题目大意：一棵树有 $n$ 个节点，每条边有一个边权w[i]，求两点之间距离不超过 $k$ 的点对个数。
$n \leq 10^{4}, w [i] \leq 1000$

思路：数据范围枚举是肯定过不去的。思考分治来降低枚举的量级。
按重心将树分成了若干子树后，dfs得到子树中每一个节点到当前根的距离，two-pointers统计答案。
发现有重复，观察到重复的情况就是上面提到的“仅与子树有关”的答案（可以理解为是从某一个点向上出发到根再原路折返回来造成的答案），用容斥的思想减去即可。

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<cctype>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
    long long f=1,sum=0;
    char c=getchar();
    while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
    while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
    return sum*f;
}
const int MAXN=10010;
struct edge
{
    int next,to,val;
};
edge e[MAXN*2];
int head[MAXN],cnt;
void addedge(int u,int v,int w)
{
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].val=w;
    head[u]=cnt;
}
bool visit[MAXN];
int sz[MAXN],rt;
int n,k,ans,dis[MAXN],mx[MAXN];
void dfs(int x,int fa)
{
    sz[x]=1,mx[x]=0;
    for (int i=head[x];i;i=e[i].next)
    {
        int v=e[i].to;
        if (visit[v] || v==fa) continue;
        dfs(v,x);
        sz[x]+=sz[v];
        mx[x]=max(mx[x],sz[v]);
    }
    mx[x]=max(mx[x],n-sz[x]);
    if (mx[x]<mx[rt]) rt=x;
}
vector <int> tmp;
void get_dis(int x,int fa)
{
    tmp.push_back(dis[x]);
    for (int i=head[x];i;i=e[i].next)
    {
        int v=e[i].to;
        if (v==fa || visit[v]) continue;
        dis[v]=dis[x]+e[i].val;
        get_dis(v,x);
    }
} 
int calc(int x,int init)
{
    int tot=0;
    dis[x]=init;
    tmp.clear();
    get_dis(x,0);
    sort(tmp.begin(),tmp.end());
    int l=0,r=tmp.size()-1;
    while (l<r)
    {
        if (tmp[l]+tmp[r]<=k)
            tot+=r-l,l++;
        else
            r--;
    }
    return tot;
}
void dfs1(int x)
{
    ans+=calc(x,0);
    visit[x]=1;
    for (int i=head[x];i;i=e[i].next)
    {
        int v=e[i].to;
        if (visit[v]) continue;
        ans-=calc(v,e[i].val);
        n=sz[v];
        rt=0;
        dfs(v,0);
        dfs1(rt);
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    while (n+k)
    {
        memset(head,0,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(dis,0,sizeof(dis));
        cnt=0;
        for (int i=1;i<n;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w),addedge(v,u,w);
        }
        mx[0]=INF;
        rt=0,ans=0;
        dfs(1,0);
        dfs1(rt);
        printf("%d\n",ans);
        scanf("%d%d",&n,&k);    
    }
    return 0;
}

点分治的一般模式

找到重心
计算子树内部答案
重置重心，向深层继续分治。

秒客网