点分治 笔记

发表于 | 阅读次数：
本文字数： 1.2k 字 | 阅读时长 ≈ 6 分钟

算法概述

点分治用来统计树上满足某种条件的路径个数，一般具有可合并答案的性质（比如是否存在路径长度 $=k$等）。

算法步骤

首先我们考虑经过根节点的满足条件的路径有多少。那比如我们就拿长度为 $k$ 举例，先从根节点 $DFS$ 一遍，求出每个节点的 $dis$。然后对于一个节点的 $dis[i]$，统计 $k-dis[i]$ 是否存在即可。如果存在，那么就有。

当然，并不是所有的路径都经过根节点。那么，不经过根节点的路径，一定经过根节点子树中的某个点。

那么我们把根节点的每个子树都分治一遍（递归），不就能求出答案了吗？

但是我们发现这样太慢了，复杂度为 $O(n\times C)$，其中 $C$ 为递归的次数。但是很显然，树为一条链的时候，$C=n$，复杂度变成 $O(n^2)$。

如何优化这个算法呢？也很简单，我们都有 $DFS$ 一遍的时间，顺便把每颗子树的重心都求出来好了。

然后对于每个子树，我们递归这个子树的时候，以重心为根。

这样，容易证明，递归次数 $C\le\log n$。

模板题

洛谷 3806：给一颗树，多组询问是否存在长度为 $k$ 的路径。
$n\le 10^4,m\le 100$

解法：每次点分治的时候，维护一个 $bool$ 数组 $cxk$，$cxk[i]$ 表示是否存在 $dis[k]=i$。分治的时候，遍历每个询问 $k$，如果 $cxk[k-dis[i]]$，那么这个询问答案变成 $true$ （题目要求输出 AYE）

总的复杂度是 $O(nm\log n)$

模板题代码

点击
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define K 100000007
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class Graph // 图
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Label,Next;
            }Ed[N<<1];
            void clear(int _V=N,int _E=N<<1) 
            {
                memset(Ed,-1,sizeof(Edge)*(_E));
                memset(head,-1,sizeof(int)*(_V));
                EdgeCount=-1;
            }
            void AddEdge(int u,int v,int w=1)
            {
                Ed[++EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v,int w=1) {AddEdge(u,v,w);AddEdge(v,u,w);}
            int Start(int u) {return head[u];}
            int To(int u){return Ed[u].To;}
            int Label(int u){return Ed[u].Label;}
            int Next(int u){return Ed[u].Next;}
    }G;
    

    int n,m;
    int q[N];
    void Input()
    {
        Rd(2,&n,&m);
        G.clear();
        F(i,1,n-1) {int u,v,w;Rd(3,&u,&v,&w); G.Add2(u,v,w);}
        F(i,1,m) {R1(q[i]);}
    }

    bool vis[N];
    bitset<K> cxk,test;
    // cxk[i]  表示是否存在 dis[k]=i
    // test[i] 表示第 i 个询问的答案
    int size[N],bal[N];
    int root,sum;
    // 这些是求重心的
    void GetBal(int u,int f)
    {
        size[u]=1; bal[u]=0;
        Tra(i,u) if (v!=f and !vis[v])
        {
            GetBal(v,u);
            size[u]+=size[v];
            bal[u]=max(bal[u],size[v]);
        }
        bal[u]=max(bal[u],sum-size[u]);
        if (bal[u]<bal[root]) root=u;
    }
    int rec[N],dis[N];
    void GetDis(int u,int f) 
    // 这个 DFS 用来求 dis，顺便把所有的 dis 数组记录在一个数组 rec 里
    // 由于是 1 编号，不用的 rec[0] 就用来存长度
    {
        rec[++rec[0]]=dis[u];
        Tra(i,u) if (v!=f and !vis[v])
        {
            dis[v]=dis[u]+G.Label(i);
            GetDis(v,u);
        }
    }
    void calc(int u) // 计算以 u 为根的答案
    {
        vector<int> d;
        Tra(i,u) if (!vis[v])
        {
            rec[0]=0; dis[v]=G.Label(i);
            GetDis(v,u);

            D(j,rec[0],1) F(k,1,m) if (q[k]>=rec[j]) // 注意 q[k]>=rec[j]
            {
                test[k]=test[k]|cxk[q[k]-rec[j]];
            }
            D(j,rec[0],1) {d.p_b(rec[j]); cxk[rec[j]]=1;}
        }
        F(i,0,sz(d)-1) cxk[d[i]]=0;
    }
    void DFS(int u)
    {
        vis[u]=cxk[0]=1; 
        calc(u); // 计算以 u 为根的答案
        Tra(i,u) if (!vis[v])
        {
            sum=size[v]; bal[root=0]=0x3f3f3f3f;
            GetBal(v,v);
            DFS(root); //求出重心，递归子树
        }
    }
    void Soviet()
    {
        sum=bal[root=1]=n;
        GetBal(1,1);
        DFS(root);
        F(i,1,m) puts(test[i]?"AYE":"NAY");
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w