Eternity

Until The End

点分治

发表于 更新于 分类于 ，
本文字数： 4.6k 阅读时长 ≈ 4 分钟

燃其主核，破其王座。

解释

点分治用于对一些具有限定条件的路径进行静态统计的算法。

一般步骤在于：

  1. 任选一个根节点 $p$ （一般 $p$ 必须是树的重心）
  2. 从 $p$ 出发进行一次 $Dfs$ ，求得两个数组 $dist$ 与 $belong$
  3. 执行 $calc(p)$
  4. 删除根节点 $p$ ，对 $p$ 的每一个子树重复 $1 \sim 4$ 的操作。

对于不同的题目，其 $calc(p)$ 函数大同小异。但其他都差不多。

$dist[x]$ 表示节点 $x$ 到根节点 $p$ 的距离。

$belong[x]$ 表示节点 $x$ 所属于的是根节点 $p$ 的哪一棵子树。

规定： $dist[p]=0,belong[p]=p$

我们设 $T$ 为递归操作所到达的最大深度。那么复杂度则为 $\mathcal O(TN\log N)$

总而言之，复杂度的波动范围则是 $\mathcal O(N\log N)\sim\mathcal O(N^2\log N)$ 。

显然，这个波动极大，对于两个极值而言，一个，是链，一个，是重心。所以，这也是为什么 $p$ 必须要取树的重心。但查找重心需要一定的时间，大概是 $\mathcal O(\log N)$

所以，点分治的时间就是 $\mathcal O(N\log^2 N)$ 了。

例题

Luogu.P3806

其他部分不多赘述。重点说 $calc(p)$ 部分。

有两种做法。

树上直接统计

设 $p$ 的子树为 $s_1,s_2…s_m$

对于 $s_i$ 中的每一个节点 $x$ ，将满足 $dist[x]+dist[y]=K$ 的节点 $y$ 统计出即可。

可以使用树状数组。

  1. 对于 $s_i$ 中的每一个节点 $x$ ，查询其前缀和 $ask(K-dist[x])$ ，即 $y$ 的个数。
  2. 对于 $s_i$ 中的每一个节点 $x$ ，进行 $add(dist[x],1)$ ，表示与 $p$ 距离为 $dist[x]$ 的节点增加了 $1$ 个。

按子树一棵棵统计保证了 $belong[x]\neq belong[y]$ ，查询前缀和保证了 $dist[x]+dist[y]=K$ 。

进行优化的话，可以使用平衡树代替树状数组，或者离散化。

指针扫描数组

将树的节点转化为一个一维数组记为 $num[i]$ ，并按照其 $dist$ 值进行由小到大排序。然后创建头指针和尾指针 $l,r$ 或者 $head,tail$ 。从前后扫描 $num$ 数组。

那么，当 ++l 和 --r 在执行时， $dist[num[l]]+dist[num[r]]$ 应该是单调递减的。

用 $cnt[s]$ 表示 $l+1\sim r$ 之间满足 $belong[num[i]]=s$ 的位置 $i$ 的个数。当路径一端 $x$ 等于 $num[l]$ 时，统计答案 $y=r-l-cnt[belong[num[l]]]$

这道题用的就是这个思路。

杂话

对于这道题，转离线统计，用点分治的传统方法，找重心，计算，删点即可。

时间复杂度 $\mathcal O(nm\log n)$

AC Code 
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
151
152
153
154
155
156
157
158
159
160
161
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e7+1;
const int MAXM=1e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M;
struct Road
{
    int next,to,val;
    Road(int next=0,int to=0,int val=0):
        next(next),to(to),val(val){}
}Edge[MAXN<<1];
int Head[MAXN],Total;
int Pos,ans_Pos,Size[MAXN];
bool vis_Pos[MAXN],vis[MAXN];
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=Road(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=Road(Head[v],u,w);Head[v]=Total;
}
void dfs_Pos(int x,int fa,int size)
{
    Size[x]=1;
    int Max_Part=0;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==fa||vis[v]) continue;
        dfs_Pos(v,x,size);
        Size[x]+=Size[v];
        Max_Part=max(Max_Part,Size[v]);
    }
    Max_Part=max(Max_Part,size-Max_Part);
    if(!Pos||Max_Part<ans_Pos)
    {
        ans_Pos=Max_Part;
        Pos=x;
    }
}
int blg[MAXN],dis[MAXN],query[MAXM];
int num[MAXN],Tot;
inline bool cmp(int x,int y)
{
    return dis[x]<dis[y];
}
void dfs_Dist(int x,int fa,int val,int u)
{
    num[++Tot]=x;
    dis[x]=val,blg[x]=u;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==fa||vis[v]) continue;
        dfs_Dist(v,x,val+Edge[e].val,u);
    }
}
bool ans[MAXM];
void dfs_Calc(int x)
{
    Tot=0;
    num[++Tot]=x;
    dis[x]=0,blg[x]=x;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if(vis[(v=Edge[e].to)]) continue;
        dfs_Dist(v,x,Edge[e].val,v);
    }
    sort(num+1,num+1+Tot,cmp);
    for(int i=1;i<=M;++i)
    {
        int l=1,r=Tot;
        while(l<r)
        {
            if(dis[num[l]]+dis[num[r]]>query[i]) --r;
            else if(dis[num[l]]+dis[num[r]]<query[i]) ++l;
            else if(blg[num[l]]==blg[num[r]])
            {
                if(dis[num[r]]==dis[num[r-1]]) --r;
                else ++l;
            }
            else
            {
                ans[i]=1;
                break;
            }
        }
    }
}
void solve(int x)
{
    vis[x]=1;
    dfs_Calc(x);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if(vis[(v=Edge[e].to)]) continue;
        Pos=0;
        dfs_Pos(v,0,Size[v]);
        solve(Pos);
    }
}
int main()
{
    // freopen("tree.in","r",stdin);
    // freopen("tree.out","w",stdout);
    read(N,M);
    for(int i=1,u,v,w;i<N;++i)
    {
        read(u,v,w);
        addEdge(u,v,w);
    }
    dfs_Pos(1,-1,N);
    for(int i=1;i<=M;++i) read(query[i]);
    solve(Pos);
    for(int i=1;i<=M;++i)
    {
        if(ans[i]||!query[i]) printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}
/*
2 1
1 2 2
2
*/

后记

似乎这玩意儿 NOIp 是不考的，省选之后的内容了，最近几年也只有 WC 和 IOI 考过。

相关文章