点分治

介绍

点分治是用来解决树上路径问题的一种方法。

在解决树上路径问题时，我们可以选取一点为根，将树转化为有根树，然后考虑经过根的所有路径（有时将两条从根出发的路径连接为一条）。统计完这些路径的答案后，将根节点标记为删除，对剩下的若干棵树进行同样的操作。

如图，我们可以先考虑经过节点 1 的路径，之后将节点 1 标记为删除，此时可以认为考虑过的路径均已被删除。继续对其它子树做相同处理即可。

每次确认一个根节点后，共有 n 条需要考虑的路径（ n 为当前子树大小）。上图中将 1 删除后，剩下左侧的子树较大，和原树大小相当，继续处理这棵子树时仍然需要与前一过程相当的时间。

最严重的情况，当整棵树是一条链时，每次需要考虑的路径数量是 O(n) 级别的，如果每条路径需要常数时间进行统计，则总时间复杂度为 O(n^2) 。而对于形态随机的树，则远远小于这个级别。

如果我们选择 5 作为这棵树的根节点，情况会好很多 —— 删除 5 后剩余的最大一棵子树的大小比删除 1 时要小。这说明「科学地」选择点作为根节点可以有效的降低复杂度。

重心方面操作

模板

struct Node
{
    struct Edge *firstEdge;
    // solved 表示该节点是否已被解决
    // 在点分治中，标记 solved 的节点被认为不存在
    //
    // vis 表示在当前 DFS / BFS 中是否访问过
    bool solved, vis;
    // size 表示子树大小（和树剖中相同）
    // max 表示最大子节点大小
    int size, max;
    Node *fa; // 父节点
} N[MAXN + 1];

// 找以 start 为根的子树的重心
// 非递归 DFS
inline Node *center(Node *start)
{
    std::stack s;
    s.push(start);
    start->vis = false;
    start->fa = NULL;

    static Node *a[MAXN + 1]; // 储存所有 DFS 到的节点
    int cnt = 0;
    while (!s.empty())
    {
        Node *v = s.top();

        // 如果是第一次出栈，则不将 v 从栈中删除
        // 将所有子节点入栈
        if (!v->vis)
        {
            a[++cnt] = v; // 记录节点

            v->vis = true;
            for (Edge *e = v->firstEdge; e; e = e->next)
            {
                // 判断不走回父节点，不走到已经 solved 的节点
                if (e->to != v->fa && !e->to->solved)
                {
                    e->to->fa = v;
                    e->to->vis = false;
                    // 子节点入栈
                    s.push(e->to);
                }
            }
        }
        else
        {
            // 第二次出栈，表示回溯到 v
            v->size = 1;
            v->max = 0;
            for (Edge *e = v->firstEdge; e; e = e->next)
            {
                if (e->to->fa == v)
                {
                    // 维护 size 和 max
                    v->size += e->to->size;
                    v->max = std::max(v->max, e->to->size);
                }
            }

            // 将 v 从栈中删除
            s.pop();
        }
    }

    // 统计重心
    Node *res = NULL;
    for (int i = 1; i <= cnt; i++)
    {
        // v->max 表示在整棵子树中，删掉 v 后剩余的最大子树
        // 如果把 v 作为根，则原有的除 v 的子树以外的部分会成为 v 的一棵子树
        // 这部分的大小为 总节点数量 - v->size
        // 因为是以 start 作为根进行的 BFS，总节点数量即为 start->size
        a[i]->max = std::max(a[i]->max, start->size - a[i]->size);

        // 更新答案
        if (!res || res->max > a[i]->max) res = a[i];
    }

    return res;
}

// 主求解过程
inline int solve()
{
    std::stack s;
    s.push(&N[1]);

    int ans = 0; // 答案
    while (!s.empty())
    {
        // 这里的 DFS 不需要回溯，所以每次出栈即可
        Node *v = s.top();
        s.pop();

        // 求重心
        Node *root = center(v);

        // 为防止后续的 BFS、DFS 走回根，先将根置为 solved
        root->solved = true;

        ans += calc(root);
    }

    return ans;
}

相关

标签