Zth's Blog

记录学习路上的点滴

0%

点分治

发表于 分类于

点分治模板

算法

概念

点分治是一种用于求解树上路径的分治算法， 最基本的就是解决树上是否存在长度为$len$的路径

详解

点分治的思想同一般分治， 递归将当前问题分解为若干个求解方式相同但规模更小的子问题， 直到子问题可以直接求解， 然后回溯时利用子问题的解合并出当前问题的解

对于本题而言， 假设我们当前面对的是一棵有根树， 那么我们可以把树上的路径分为两种

  1. 经过根节点的路径
  2. 不经过根节点， 完全处于根节点的某棵子树的路径

对于第一种路径， 我们可以直接遍历一下每个点到根节点的距离， 然后两个距离加起来就得到了路径长度

对于第二种路径， 等于在每棵子树中求第一类路径， 递归分治就可以了

那我们的分治策略就有了， 现在的问题就是怎么确定根可以使实践复杂度最低呢？

树的重心

在一棵树中， 以某一节点为根时其子树大小的最大值最小， 则该节点称为这棵树的重心

不难证明， 确定重心为根后， 子树大小的最大值不会超过$\lceil \frac{size}{2} \rceil$， 其中$size$为这棵树的大小， 那我们在每棵子树中找到重心并且以重心为根继续分治。

假设初始问题规模为$n$， 即给出的树有$n$个节点， 我们至多递归$O(\log n)$层， 而每个点在每一层中至多被遍历一次， 所以我们分治的时间复杂度为$O(n \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
#include <iostream>
#include <cstdio>

int n, m;
int q[102];
int head[10004], tot;
struct Edge
{
    int from, to, next, cost;
} edge[20004];
int rt, sum;
int rem[10004], sz[10004], mxz[10004], dis[10004], rsv[10004];
// rem存出现过的路径， sz为子树大小， mxz是以该点为根最大的子树大小， dis是到根的距离， rsv是存的rem， 还原现场用
bool vis[10004], judge[100000008], ans[102];

void Addedge(int u, int v, int e)
{
    edge[++ tot] = (Edge){u, v, head[u], e};

    head[u] = tot;
}

void Get_rt(int u, int fa) // 在子树中寻找重心当作子树的根
{
    sz[u] = 1;
    mxz[u] = 0; // 以u为根节点， 最大子树的大小

    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;

        if(v == fa || vis[v]) continue;

        Get_rt(v, u);
        sz[u] += sz[v];

        mxz[u] = std:: max(mxz[u], sz[v]);
    }

    mxz[u] = std:: max(mxz[u], sum - sz[u]); // 这里是为了处理当前u和上一层的根节点的那些节点， 有点特殊

    if(mxz[u] < mxz[rt]) rt = u;
}

void Get_dis(int u, int fa) // 得到子树每个点到根节点的距离
{
    rem[++ rem[0]] = dis[u];

    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to, e = edge[i].cost;

        if(v == fa || vis[v]) continue;

        dis[v] = dis[u] + e;
        Get_dis(v, u);
    }
}

void Cal(int u) // 计算答案
{
    int cnt = 0;

    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to, e = edge[i].cost;

        if(vis[v]) continue;

        rem[0] = 0; // rem[0]用于存个数
        dis[v] = e;
        Get_dis(v, u);

        for(int j = 1; j <= rem[0]; j ++)
            for(int k = 1; k <= m; k ++)
                if(q[k] >= rem[j])
                    ans[k] |= judge[q[k] - rem[j]]; // 统计答案

        for(int j = 1; j <= rem[0]; j ++)
            rsv[++ cnt] = rem[j], judge[rem[j]] = 1; // 处理完一棵子树， 把其中出现的路径加入judge
    }

    for(int i = 1; i <= cnt; i ++) judge[rsv[i]] = 0; // 处理完u， 还原现场， 不能memset， 会T
}

void Solve(int u)
{
    vis[u] = judge[0] = 1;
    Cal(u); // 处理当前u

    for(int i = head[u]; i; i = edge[i].next) // 分治处理子树
    {
        int v = edge[i].to;

        if(vis[v]) continue;

        sum = sz[v]; // sum理论来说应该是这棵子树的大小， 但是sz不一定对， 看后面解释
        mxz[rt = 0] = 1e9 + 1;

        Get_rt(v, 0);
        Solve(rt);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i ++)
    {
        int u, v, e;
        scanf("%d%d%d", &u, &v, &e);

        Addedge(u, v, e);
        Addedge(v, u, e);
    }
    for(int i = 1; i <= m; i ++) scanf("%d", &q[i]);

    mxz[rt] = sum = n;
    Get_rt(1, 0);
    Solve(rt);

    for(int i = 1; i <= m; i ++)
        if(ans[i])
            printf("AYE\n");
        else
            printf("NAY\n");

    return 0;
}

算法的整体思路就是先找出一个$rt$， 然后开始分治， 分治时先计算第一类路径， 在Cal()中Get_dis()即可求出， 然后分治即可

一点问题

注意到我们对子树确定了$rt$之后并没有再次以$rt$为根遍历一遍子树得到子树中每个点的$size$， 实际上这个$size$在$rt$和本层遍历起点之间的那些点都是错的

举个例子， 在这个例子中， $2$号点(本层$rt$)和$1$号点(本层遍历起点)之间(包括$1$号点)的这棵子树传入的$sum = size$是错误的

最开始， 我们以$1$号点为起点遍历整棵树得到$rt$是$2$

然后我们并没有以$2$为起点遍历一遍这棵树重新得到每个点的$size$， 而是直接计算了第一类路径， 所以这里的$size$还是以$1$为根的

我们接下来要对$2$的子树进行分治了， 我们对每个子树传入一个$sum = size[v]$表示子树大小， 这个值对于$3, 5$节点来说是对的， 对于$7, 1$来说是错的， 因为这个时候$size[7] = 6, size[1] = 7$， 这就出现了我刚才说到的问题

所以我们找到$rt$之后， 理应重新以$rt$为根遍历一下子树得到正确的$size$以传入正确的$sum$， 否则本层重心可能会找错

但是有大佬证明了这样时间复杂度其实没有影响， 那为了省事就不用再遍历一次了