题目链接：UOJ 374

九条可怜是一个热爱阅读的女孩子。

这段时间，她看了一本非常有趣的小说，这本小说的架空世界引起了她的兴趣。

这个世界有 $n$ 个城市，这 $n$ 个城市被恰好 $n − 1$ 条双向道路联通，即任意两个城市都可以互相到达。同时城市 $1$ 坐落在世界的中心，占领了这个城市就称霸了这个世界。

在最开始，这 $n$ 个城市都不在任何国家的控制之下，但是随着社会的发展，一些城市会崛起形成国家并夺取世界的霸权。为了方便，我们标记第 $i$ 个城市崛起产生的国家为第 $i$ 个国家。

在第 $i$ 个城市崛起的过程中，第 $i$ 个国家会取得城市 $i$ 到城市 $1$ 路径上所有城市的控制权。新的城市的崛起往往意味着战争与死亡，若第 $i$ 个国家在崛起中，需要取得一个原本被国家 $j(j \ne i)$ 控制的城市的控制权，那么国家 $i$ 就必须向国家 $j$ 宣战并进行战争。

现在，可怜知道了，在历史上，第 $i$ 个城市一共崛起了 $a_i$ 次。但是这些事件发生的相对顺序已经无从考究了，唯一的信息是，在一个城市崛起称霸世界之前，新的城市是不会崛起的。

战争对人民来说是灾难性的。可怜定义一次崛起的灾难度为崛起的过程中会和多少不同的国家进行战争（和同一个国家进行多次战争只会被计入一次）。可怜想要知道，在所有可能的崛起顺序中，灾难度之和最大是多少。

同时，在考古学家的努力下，越来越多的历史资料被发掘了出来，根据这些新的资料，可
怜会对 $a_i$ 进行一些修正。具体来说，可怜会对 $a_i$ 进行一些操作，每次会将 $a_x$ 加上 $w$。她希望在每次修改之后，都能计算得到最大的灾难度。

然而可怜对复杂的计算并不感兴趣，因此她想让你来帮她计算一下这些数值。

对题面的一些补充：

  • 同一个城市多次崛起形成的国家是同一个国家，这意味着同一个城市连续崛起两次是不会和任何国家开战的：因为这些城市原来就在它的控制之下。
  • 在历史的演变过程中，第 $i$ 个国家可能会有一段时间没有任何城市的控制权。但是这并不意味着第 $i$ 个国家灭亡了，在城市 $i$ 崛起的时候，第 $i$ 个国家仍然会取得 $1$ 到 $i$ 路径上的城市的控制权。

数据范围：$1 \le n, m \le 4 \times 10 ^ 5$。

Solution

将题意简述一下：给出一棵树，给定每个点的 $\text{access}$ 次数，求轻重链切换次数的最大值。

首先我们考虑没有修改的情况下如何计算答案，注意到每个点的贡献是独立的，于是我们可以分开计算贡献。现在考虑第 $i$ 个点处的轻重链切换次数的最大值，我们设它自己的 $\text{access}$ 次数为 $A_0$，它的 $k$ 个儿子中第 $i$ 个儿子的子树内的 $\text{access}$ 总次数为 $A_i$。

又观察到，对于相邻的 $2$ 次 $\text{access}$，如果他们都在 $i$ 的同一棵子树内或者都是 $i$，那么点 $i$ 次不会发生轻重链切换；否则会发生一次轻重链切换。

于是我们可以把问题转化为：给定 $k + 1$ 种颜色的小球，第 $i(0 \le i \le k)$ 个球有 $A_i$ 个，要求把所有小球排成一行，求相邻小球颜色不同的最大数量。这个问题可以在 $\mathcal O(1)$ 的时间内解决。我们设 $t = \sum_{i = 0} ^ k A_i$，$h = \max_{i = 0} ^ k A_i$，那么经过简单的讨论可以得出答案：

  • 当 $h > t - h$ 时：最多的插入后多余部分放到最后，答案为 $2 \times (t - h)$。
  • 当 $h \le t - h$ 时：此时总有一种方案使得相邻不同，答案为 $t - 1$。

计算出每个点的答案后，将 $n$ 个点的答案累加就是最终答案。于是我们可以在 $\mathcal O(n)$ 的时间内计算出没有修改时的答案。此时已经可以获得 $30$ 分。

接下来考虑如何处理修改。我们记 $f(i)$ 表示节点 $i$ 的子树中的 $\text{access}$ 的总次数。考虑点 $v$ 到其父亲 $u$ 的一条边，如果 $2\cdot f(v) > f(u)$，那么将 $(u, v)$ 标记为实边；否则这条边为虚边。不难发现每个点往下最多只有一条实边，即所有的实边在树上是若干条链。

如果我们对 $a_i$ 加上 $w$，那么这会影响到点 $i$ 到根节点路径上的所有点的答案和边的虚实关系。对于路径上的实边 $(u, v)$，在 $f(u), f(v)$ 同时加上 $w$ 后，仍然是满足 $2\cdot (f(v) + w) > (f(u) + w)$ 的，因此可以得到结论：路径上的实边不会改变，我们只需要考虑那些虚边就行了。

我们可以用类似 $\text{LCT}$ 的方法维护这棵树。用一棵 $\text{Splay}$ 来维护全是实边的链，然后对于一次修改操作，将 $i$ 到根节点的路径上的虚边进行修改，更新它们对答案的贡献。但是需要注意：在 $\text{access}$ 的过程中，经过的虚边不一定都会变成实边！

最后分析一下复杂度。发现 $\text{splay}$ 的复杂度不会改变，唯一有变化的是 $\text{access}$ 操作，其复杂度只和经过的虚边数量有关。如果一条边是虚边，那么一定有 $f(u) \ge 2\cdot f(v)$；又因为 $f(1)$ 的值为 $\sum_{i = 1} ^ n a_i$，因此经过的虚边数量为 $\mathcal O(\log \sum_{i = 1} ^ n a_i)$。这个复杂度可以通过本题。

时间复杂度：$\mathcal O(m \log \sum a_i)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 4e5 + 5, M = 8e5 + 5;

int n, m, tot, lnk[N], ter[M], nxt[M];
long long ans;

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    long long val, si, sum;
    Node() {
        ch[0] = ch[1] = fa = null;
        val = si = sum = 0;
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void pushup() {
        sum = ch[0]->sum + ch[1]->sum + si + val;
    }
} *a[N];

struct LCT {
    void build(int n) {
        null = new Node();
        null->ch[0] = null->ch[1] = null->fa = null;
        for (int i = 1; i <= n; i++) {
            a[i] = new Node();
        }
    }
    void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        bool k = x->get();
        !y->isroot() && (z->ch[y->get()] = x), x->fa = z;
        y->ch[k] = x->ch[!k], x->ch[!k]->fa = y;
        x->ch[!k] = y, y->fa = x;
        y->pushup();
    }
    void splay(Node *x) {
        while (!x->isroot()) {
            Node *y = x->fa;
            if (!y->isroot()) {
                rotate(x->get() == y->get() ? y : x);
            }
            rotate(x);
        }
        x->pushup();
    }
    long long calc(Node *x, long long s, long long m) {
        return x->ch[1] != null ? (s - m) << 1 : (x->val << 1) > s ? (s - x->val) << 1 : s - 1;
    }
    void access(Node *x, long long v) {
        splay(x);
        long long s = x->sum - x->ch[0]->sum, m = x->ch[1]->sum;
        ans -= calc(x, s, m);
        x->sum += v, x->val += v, s += v;
        if ((m << 1) <= s) {
            x->si += m, m = 0;
            x->ch[1] = null;
        }
        ans += calc(x, s, m), x->pushup();
        for (Node *y; (x = (y = x)->fa) != null; ) {
            splay(x);
            long long s = x->sum - x->ch[0]->sum, m = x->ch[1]->sum;
            ans -= calc(x, s, m);
            x->sum += v, x->si += v, s += v;
            if ((m << 1) <= s) {
                x->si += m, m = 0;
                x->ch[1] = null;
            }
            if ((y->sum << 1) > s) {
                x->si -= (m = y->sum);
                x->ch[1] = y;
            }
            ans += calc(x, s, m), x->pushup();
        }
    }
} T;

void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
void dfs(int u, int p) {
    Node *x = a[u];
    x->sum = x->val;
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        a[v]->fa = x;
        dfs(v, u);
        x->sum += a[v]->sum;
    }
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        if ((a[v]->sum << 1) > x->sum) x->ch[1] = a[v];
    }
    x->si = x->sum - x->val - x->ch[1]->sum;
    ans += T.calc(x, x->sum, x->ch[1]->sum);
}
int main() {
    scanf("%d%d", &n, &m);
    T.build(n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]->val);
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs(1, 0);
    printf("%lld\n", ans);
    for (int i = 1; i <= m; i++) {
        int x;
        long long v;
        scanf("%d%lld", &x, &v);
        T.access(a[x], v);
        printf("%lld\n", ans);
    }
    return 0;
}
最后修改：2019 年 07 月 30 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏