【图论】点分治

更新于 分类于 ， 阅读次数： 本文字数： 4.7k 阅读时长 ≈ 4 分钟

点分治是解决树上统计问题的一种思想

条件

树上统计问题，常统计路径信息、节点信息

一般是无根树

思想

选定根节点rtrt 则统计数据来自于：

  • rtrt 参与（以路径为例则uu 是端点/经过uu ）
  • rtrt 不参与，子树的统计结果

根的选择：常选择重心，使得分治时的递归层数为log⁡n\log n ，复杂度则是O(nlog⁡2n)O(n\log^2 n) 级别（不证明）

常有容斥思想

题目

路径统计

洛谷P3806 【模板】点分治1

统计结果=经过rtrt 的答案+rtrt 的所有儿子的子树答案。

第二部分递归处理，考虑如何求出第一部分。

第一部分有dist(u,v)=dist(u,rt)+dist(v,rt)dist(u,v)=dist(u,rt)+dist(v,rt) ，对于一颗树到根节点的距离一个dfs就可以解决。

如果对于kk （见题意）求解对数，可以用双指针l,rl,r ，先将所有的distdist 放入一个数组DD 并排序，当D[l]+D[r]<=kD[l]+D[r]<=k 时，总答案加上r−l+1r-l+1

对于洛谷由于只考虑存在性，且多个询问，可以离线，对于每个距离用bool数组记录，找是否存在和为kk 的其他值就可以了。

我没有看懂的是很多题解做了个容斥，可能是在计数部分有所不同。

求重心

很模板，只是多了vst数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Rt,tot; // Rt重心，tot是求重心的树的节点总数
int sz[N],weight[N]; // sz[u]是节点u的儿子总数（看作有根），weight[u]是u的最大子树节点数（无根树）
bool vst[N]; // 是否访问过，在这里因为要对子树操作所以需要做标记，只求重心不需要
void get_root(int rt,int from)
{
    sz[rt]=1;
    weight[rt]=0;
    for(auto p:G[rt])
    {
        int v=p.first,w=p.second;
        if(v==from || vst[v])
            continue;
        get_root(v,rt);
        sz[rt]+=sz[v];
        weight[rt]=max(weight[rt],sz[v]);
    }
    weight[rt]=max(weight[rt],tot-sz[rt]);
    //if(weight[rt]<=(tot>>1))
    if(weight[rt]<weight[Rt])
        Rt=rt;
}

求到根节点的路径长

普通dfs，但是由于这题用了桶排且卡了这个点，需要剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int d[N]; // d[u]表示u到Rt（树根，也是重心）的距离
int D[N]; // D[0...Dcnt-1]记录所有的距离值
int Dcnt;
void get_dist(int rt,int from)
{
    if(d[rt]>=M) return; // 这题用了桶排，k有1e7可以开桶，但实际路径长会爆桶，这里做一个剪枝
    D[Dcnt++]=d[rt];
    for(auto p:G[rt])
    {
        int v=p.first,w=p.second;
        if(v==from || vst[v])
            continue;
        d[v]=d[rt]+w;
        get_dist(v,rt);
    }
}

分治

solve(rt)求解以rt为根节点的树的答案，过程中分为两个部分，一方面调用calc(rt)计算以rt为根节点（第一部分，即“经过”）的答案，另一方面遍历所有子节点递归调用实现分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int tmp[N]; // 桶排卡memset，所以这里用tmp[0...tcnt-1]记录所有可以达到的路径长度，用来清空ok数组
int tcnt;
bool ok[M]; // ok[i]表示有路径长度为i的节点
void calc(int rt)
{
    tcnt=0;
    for(auto p:G[rt])
    {
        int v=p.first,w=p.second;
        if(vst[v])
            continue;
        Dcnt=0; // 清空先前求出的路径长
        d[v]=w;
        get_dist(v,rt); // 求解rt的子树的所有路径长
        for(int i=0;i<Dcnt;i++)
            for(int j=0;j<m;j++)
                if(Q[j]>=D[i])
                    ans[j]|=ok[Q[j]-D[i]]; // 是否存在和为Q[j]的点对
        for(int i=0;i<Dcnt;i++)
            tmp[tcnt++]=D[i],ok[D[i]]=true; // 将v这颗子树的所有路径长标记为可行
    }
    for(int i=0;i<tcnt;i++)
        ok[tmp[i]]=false; // 恢复
}

void solve(int rt)
{
    vst[rt]=ok[0]=true; // 标记已访问，且路径长度为0是可行的（rt为路径端点）
    calc(rt); // 计算过rt的路径长（第一部分）
    for(auto p:G[rt])
    {
        int v=p.first,w=p.second;
        if(vst[v])
            continue;
        tot=weight[Rt=0]=sz[v]; // 准备求子树的重心，初始化节点总数
        get_root(v,0);
        solve(Rt); // 分治求解子树
    }
}

0-1路径统计

Problem - 1156D - Codeforces

这题我一开始理解错题意了。。。但其实很简单，因为1之后不能跟0，那么只有00001111序列。

对于根节点rtrt ，有以下几种拼接方法（以00、01、10、11表示到节点从下到上的序列）：

根节点非端点：(00+00)×2,(00+01),(00+11),(01+11),(11+11)×2(00+00)\times 2,(00+01),(00+11),(01+11),(11+11)\times 2

根节点：(00)×2,(11)×2,(01),(10)(00)\times 2,(11)\times 2,(01),(10)

dfs(rt,from,last)处理01个数，其中last是rt往上走两个的序列，遍历rt的子节点时有新边权，则有以下转换图：

flowchart LR
00 -- 0 -->00
00 -- 1 -->10 -- 1  -->10 -- 0 -->非法
01 -- 0 -->01
11 -- 1 -->11 -- 0 -->01 -- 1 -->非法

求重心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Rt,tot; // Rt重心，tot是求重心的树的节点总数
int sz[N],weight[N]; // sz[u]是节点u的儿子总数（看作有根），weight[u]是u的最大子树节点数（无根树）
bool vst[N]; // 是否访问过，在这里因为要对子树操作所以需要做标记，只求重心不需要
void get_root(int rt,int from)
{
    sz[rt]=1;
    weight[rt]=0;
    for(auto p:G[rt])
    {
        int v=p.first,w=p.second;
        if(v==from || vst[v])
            continue;
        get_root(v,rt);
        sz[rt]+=sz[v];
        weight[rt]=max(weight[rt],sz[v]);
    }
    weight[rt]=max(weight[rt],tot-sz[rt]);
    if(weight[rt]<weight[Rt])
        Rt=rt;
}

dfs找01路径数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ll cnt[4]; // 当前这个儿子是00、01、10、11上来的（顺序是下到上）个数
void get01(int rt,int from,int type)
{
    //cout<<rt<<' '<<from<<':'<<type<<endl;
    cnt[type]++;
    for(auto p:G[rt])
    {
        int v=p.first,w=p.second;
        if(v==from || vst[v])
            continue;
        if((type==1&&w)||(type==2&&!w))
            continue;
        if(!type&&w)
            get01(v,rt,2);
        else if(type==3&&!w)
            get01(v,rt,1);
        else get01(v,rt,type);
    }
}

统计过根节点的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
ll sum[4]; // 已经计算过的儿子是00、01、10、11上来的（顺序是下到上）个数
void calc(int rt)
{
    for(auto p:G[rt])
    {
        int v=p.first,w=p.second;
        if(vst[v])
            continue;
        cnt[0]=cnt[1]=cnt[2]=cnt[3]=0;
        get01(v,rt,(w<<1)|w);
        //端点是rt
        ans+=cnt[0]*2+cnt[3]*2+cnt[1]+cnt[2];
        //端点不是rt（这里写的是序列顺序，注意数组里的要反向）
        // (00+00)*2
        ans+=cnt[0]*sum[0]*2;
        // (00+01)
        ans+=cnt[0]*sum[2]+cnt[2]*sum[0];
        // (00+11)
        ans+=cnt[0]*sum[3]+cnt[3]*sum[0];
        // (01+11)
        ans+=cnt[1]*sum[3]+cnt[3]*sum[1];
        // (11+11)*2
        ans+=cnt[3]*sum[3]*2;
        for(int i=0;i<4;i++)
            sum[i]+=cnt[i];
    }
}

分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(int rt)
{
    //cout<<"Solve "<<rt<<endl;
    vst[rt]=true;
    calc(rt); // 计算过rt的合法路径条数（第一部分）
    for(auto p:G[rt])
    {
        int v=p.first,w=p.second;
        if(vst[v])
            continue;
        tot=weight[Rt=0]=sz[v]; // 准备求子树的重心，初始化节点总数
        sum[0]=sum[1]=sum[2]=sum[3]=0;
        get_root(v,0);
        solve(Rt); // 分治求解子树
    }
}