【LOJ2553】[CTSC2018]暴力写挂(边分树)

题目

LOJ 2553

分析

我是男生,第一次写边分治。

这题好像有两种做法,一种是边分治 + 虚树,另一种是边分树 …… 我只写了第二种,但我把两种做法都介 kou 绍 hu 一番。

两种做法一开始都需要用到边分治,这里先简单介绍一下边分治。

边分治是一种树上分治的方法,常用于处理与树上路径有关的问题。主要思想是先选取一条关键边,把这条边「断掉」后将树分成了两个连通块。先处理两个集合之间的路径(即经过这条边的路径),然后向两个连通块递归下去,直到只剩一个点。关键边的选取方式和复杂度的证明下文再说。和点分治相比,边分治的主要好处是断边后只会将树分成两个连通块,而点分治时删去一个点所分成的连通块数目与这个点的度数有关,最大是 \(n-1\) 。当然,不结合应用讲抽象的算法思想是晦 bu 涩 shuo 难 ren 懂 hua 的,所以无论有没有看懂上面的那段话,都直接来看这题的做法。为了方便理解,先介绍第一种,即边分治 + 虚树的做法。

先做一步转换:题目中 \(x\) 和 \(y\) 的距离(这里指题目里那个「距离」。除此之外的「距离」一词指真正的距离而不是题目里定义的)就是 \(\frac{1}{2}\mathrm{dis}(x,y)+\frac{1}{2}\mathrm{depth}(x)+\frac{1}{2}\mathrm{depth}(y)-\mathrm{depth'}(\mathrm{lca'}(x,y))\) .转换的主要目的是消掉不好处理的 \(\mathrm{lca}(x,y)\) 。

按照套路,在第一棵树上选取一条边,然后处理所有经过这条边的路径。在断开这条边后分成的两个连通块中,一个连通块中的点视作黑点,另一个连通块中的点视为白点(这就是边分治的好处。点分治的话可能要有红橙黄绿蓝靛紫 ... 点,复杂度还是错的)。对于当前分治到的点集(也就是两个子连通块的点集并)中的所有点 \(x\) ,求出 \(d_x\) 表示 \(x\) 到关键边的距离。,那么对于黑点 \(x\) 和白点 \(y\) ,就有 \(\mathrm{dis}(x,y)=w_x+w_y+W\) 。

在第二棵树中对当前分治到的点集建出虚树,点 \(x\) 的权值 \(w_x\) 为 \(\frac{1}{2}d_x+\frac{1}{2}\mathrm{depth}(x)\) ,其中 \(W\) 是当前边分治边的权值。现在的目标是选出一黑一白 两颗小药丸 两个点,使这两个点的权值之和减去它们的 lca 的深度最大。在虚树上树形 DP 。具体地,对于一个点 \(u\) ,设 \(f_{u,0/1}\) 是 \(u\) 的子树中权值最大的黑点 / 白点的权值。枚举儿子 \(v\) ,用 \(f_{u,0/1}+f_{v,1/0}+\mathrm{depth'}(u)+W\) 更新最终答案,然后用 \(f_{v,0/1}\) 更新 \(f_{u,0/1}\) 。

回到之前略过的那个问题:如何选择关键边,以及边分治的时间复杂度如何。通过以上做法可以看出,每次分治需要遍历整个连通块中的点,所以复杂度相当于每次分治的连通块的点数之和(当然,这道题中由于求虚树和 lca 的复杂度通常是 \(O(\log n)\) ,所以和连通块的点数之和并不是线性相关,而是要乘上 \(\log n\) —— 但这和分析边分治的复杂度关系不大 )。然后我们就可以惊喜地发现,边分治的复杂度是 \(O(n^2)\) 的 —— 考虑一棵菊花(即有一个度数为 \(n-1\) 的点的树),无论如何选边,第 \(i\) 次都会分成大小为 \(1\) 和 \(n-i\) 的两个连通块,和是 \(n-1+\sum_{i=1}^{n-1} i\) ,即 \(O(n^2)\) 。

解决的方案是把原树转化成一棵二叉树。常用的一种方法是:对于有 \(k\) 个儿子 \(s_1,s_2\cdots s_k\) 的点 \(u_1\) ,在新树上建立点 \(u_1,u_2\cdots u_k\) ,对于 \(1\leq i<k\),\(u_i\) 向 \(u_{i+1}\) 连权值为 \(0\) 的边。对于 \(1\leq i\leq k\) ,\(u_i\) 向 \(s_{i1}\) (即 \(s_i\) 在新树上对应的点序列的第一个点)连权值为原树上 \((u,s_i)\) 权值的边。这样,新树是一棵二叉树,且原树上 \((u,v)\) 的距离等于新树上 \((u_1,v_1)\) 的距离。新树的大小与原树的点数、边数之和同阶,因此是 \(O(n)\) 的。

二叉树的复杂度为什么是优秀的呢?二叉树中每个点的度数最多为 \(3\) 。考虑每次将重心和以重心为根时重心的最大子树之间的边断开。根据重心的性质,最大子树的大小不会超过 \(\frac{n}{2}\) ,因此处理这棵子树的复杂度不会超过处理剩余部分的复杂度。而剩余部分的最大大小是 \(\frac{2}{3}\) ,这种情况发生在三个子树的大小均为 \(\frac{1}{3}\) 时。因此经过最多 \(O(\log n)\) 次(注意这里的 \(\log n\) 可能不是以 \(2\) 为底的,大概是以 \(\frac{3}{2}\) 为底,但这只是常数的差距),树的大小就会变成 \(1\) 。因此复杂度为 \(O(n\log n)\) 。

举一反三:根据这个证法,好像 \(d\) 叉树的复杂度是 \(O(n\log_\frac{d+1}{d}n)\) ,这也就是为什么 \(d=2\) 时是最优的。

(我刚准备发表突然想起来我这题还没讲完)根据以上的证明,这题的时间复杂度是 \(O(n\log^2 n)\) ,听说可能过不去(我没写)。用基数排序求虚树和 RMQ 求 lca 之类的黑科技可能能优化到 \(O(nlog n)\) 。下面介绍另一种做法:边分树。

首先还是进行边分治。对于每一个点,开一棵二叉树表示它的分治路线(我知道你看不懂这句话)。形式化地说说构造方式:每个点有一棵二叉树和一个指向这个二叉树的某个结点(称为「当前结点」)的指针。每个点的二叉树一开始只有一个结点,每个点的「当前结点」就指向它的二叉树上唯一的这个结点。分治时,如果一个点是黑点,就给当前结点新建一个左儿子,并把当前结点设为自己的左儿子;否则,给当前结点新建一个右儿子,并把当前结点设为自己的右儿子。显然,这样每个点构造出来的都是一条独一无二的「二叉链」。

这些二叉树(听说叫边分树?)有一个奇妙的性质。如果两个点的共有某个位置的结点(指从根节点到这个结点走法相同的结点,比如都是从根开始向左走一步,向右走一步,再向左走一步。每个位置对应一次分治,即一条固定的关键边),说明在之前几次分治中这两个点一直位于同一个连通块中。如果这个公共位置的结点下面一个是左儿子,一个是右儿子,说明这次分治将这两个点分开了,它们之间路径应当在这个地方处理。

将这些二叉树建立完成后,在第二棵树上 dfs 一遍,在点 \(u\) 处合并所有子树的二叉树(类似于线段树合并,复杂度证明见 【知识总结】线段树合并及其复杂度证明 )。合并二叉树结点 \(x\) 和 \(y\) 的子树时,用 \(x\) 左子树和 \(y\) 右子树之间的贡献(这里面的所有点 \(a\) 和 \(b\) 在第一棵树上的距离为当前位置对应的分治时的 \(d_a+d_b+W\) ,这些信息可以在二叉树结点上维护出最大值。在第二棵树上的 lca 就是 \(u\) ),和 \(x\) 右子树和 \(y\) 左子树之间的贡献更新答案。时间复杂度 \(O(n\log n)\) 。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using namespace std;

namespace zyt
{
    template<typename T>
    inline bool read(T &x)
    {
        char c;
        bool f = false;
        x = 0;
        do
            c = getchar();
        while (c != EOF && c != '-' && !isdigit(c));
        if (c == EOF)
            return false;
        if (c == '-')
            f = true, c = getchar();
        do
            x = x * 10 + c - '0', c = getchar();
        while (isdigit(c));
        if (f)
            x = -x;
        return true;
    }
    template<typename T>
    inline void write(T x)
    {
        static char buf[20];
        char *pos = buf;
        if (x < 0)
            putchar('-'), x = -x;
        do
            *pos++ = x % 10 + '0';
        while (x /= 10);
        while (pos > buf)
            putchar(*--pos);
    }
    typedef long long ll;
    typedef pair<int, int> pii;
    const int N = 4e5 + 10, B = 20;
    int n;
    ll dis[N], ans;
    vector<pii> g[N], g2[N];
    void dfs(const int u, const int f)
    {
        for (vector<pii>::iterator it = g[u].begin(); it != g[u].end(); it++)
        {
            int v = it->first;
            if (v == f)
                continue;
            dis[v] = dis[u] + it->second;
            dfs(v, u);
        }
    }
    namespace Edge_Divide
    {
        struct edge
        {
            int to, w, next;
        }e[N << 2];
        int size[N << 1], tot, rot, root[N], end[N], cnt, head[N << 1], ecnt;
        bool vis[N << 2];
        void add(const int a, const int b, const int c)
        {
            e[ecnt] = (edge){b, c, head[a]}, head[a] = ecnt++;
        }
        struct node
        { 
            ll val;
            int s[2];
        }tree[N * B * 2];
        void find_rot(const int u, const int f)
        {
            size[u] = 1;
            for (int i = head[u]; ~i; i = e[i].next)
            {
                int v = e[i].to;
                if (v == f || vis[i])
                    continue;
                find_rot(v, u);
                size[u] += size[v];
                if (rot == -1 || max(tot - size[v], size[v]) < max(tot - size[e[rot].to], size[e[rot].to]))
                    rot = i;
            } 
        }
        void dfs(const int u, const int f, const ll d, const bool flag)
        {
            if (u <= n)
            {
                if (!root[u])
                    root[u] = end[u] = ++cnt;
                tree[end[u]].s[flag] = ++cnt;
                tree[cnt].val = d + dis[u], end[u] = cnt;
            }
            for (int i = head[u]; ~i; i = e[i].next)
            {
                int v = e[i].to;
                if (v == f || vis[i])
                    continue;
                dfs(v, u, d + e[i].w, flag);
            }
        }
        void solve(const int i)
        {
            if (i == -1)
                return;
            rot = -1;
            int u = e[i].to, v = e[i ^ 1].to;
            vis[i] = vis[i ^ 1] = true;

            dfs(u, 0, e[i].w, 0);
            tot = size[u], rot = -1;
            find_rot(u, 0);
            solve(rot);

            dfs(v, 0, 0, 1);
            tot = size[v], rot = -1;
            find_rot(v, 0);
            solve(rot);
        }
        int merge(const int x, const int y, const ll d)
        {
            if (!x || !y)
                return x + y;
            if (tree[x].s[0] && tree[y].s[1])
                ans = max(ans, (tree[tree[x].s[0]].val + tree[tree[y].s[1]].val) / 2 - d);
            if (tree[x].s[1] && tree[y].s[0])
                ans = max(ans, (tree[tree[x].s[1]].val + tree[tree[y].s[0]].val) / 2 - d);
            int r = ++cnt;
            tree[r].val = max(tree[x].val, tree[y].val);
            tree[r].s[0] = merge(tree[x].s[0], tree[y].s[0], d);
            tree[r].s[1] = merge(tree[x].s[1], tree[y].s[1], d);
            return r;
        }
        void build(const int u, const int f)
        {
            int now = u;
            for (vector<pii>::iterator it = g[u].begin(); it != g[u].end(); it++)
            {
                int v = it->first;
                if (v == f)
                    continue;
                add(now, v, it->second), add(v, now, it->second);
                head[++tot] = -1;
                add(now, tot, 0), add(tot, now, 0);
                now = tot;
                build(v, u);
            }
        }
        void work()
        {
            memset(head, -1, sizeof(int[n + 1]));
            tot = n;
            build(1, 0);
            rot = -1;
            find_rot(1, 0);
            solve(rot);
        }
    }
    void dfs2(const int u, const int f, const ll d)
    {
        using Edge_Divide::merge;
        using Edge_Divide::root;
        ans = max(ans, dis[u] - d);
        for (vector<pii>::iterator it = g2[u].begin(); it != g2[u].end(); it++)
        {
            int v = it->first;
            if (v == f)
                continue;
            dfs2(v, u, d + it->second);
            root[u] = merge(root[u], root[v], d);
        }
    }
    int work()
    {
        read(n);
        for (int i = 1; i < n; i++)
        {
            int a, b, c;
            read(a), read(b), read(c);
            g[a].push_back(pii(b, c)), g[b].push_back(pii(a, c));
        }
        for (int i = 1; i < n; i++)
        {
            int a, b, c;
            read(a), read(b), read(c);
            g2[a].push_back(pii(b, c)), g2[b].push_back(pii(a, c));
        }
        dfs(1, 0);
        Edge_Divide::work();
        dfs2(1, 0, 0);
        write(ans);
        return 0;
    }
}
int main()
{
    return zyt::work();
}
上一篇:验证码识别


下一篇:CTSC2018 混合果汁