动态树的最值

一 问题描述

一棵树有 N 个节点，每个节点都有一个权值 Wi ，有 4 种操作。

① 1 x y ，在两个节点 x、y 之间添加一条新边。因此，在这种操作之后，两棵树将连接成一棵新树。

② 2 x y ，在树集合中找到包含节点 x 的树，并且使节点 x 成为该树的根，然后删除节点 y 与其父节点之间的边。在这种操作之后，一棵树将被分成两部分。

③ 3 w x y ，将 x 到 y 路径上所有节点的权值都增加w 。

④ 4 x y ，查询 x 到 y 路径上节点的最大权值。

二 输入和输出

1 输入

包含多个测试用例。每个测试用例的第 1 行都包含一个整数 N（1 ≤ N ≤3×10^5 ）；接下来的 N -1 行，每行都包含两个整数 x、y ，表示它们之间有一条边；下一行包含 N 个整数，表示每个节点的权值都为 Wi（0≤W i ≤3000）；再下一行包含一个整数Q（1≤Q≤3×10^5 ），接下来的 Q 行以整数 1、2、3 或 4 为开头，表示操作类型。

2 输出

对每个查询，都单行输出正确答案。若此查询是特殊操作，则输出 -1。在每个测试用例之后都输出一个空行。

三 输入和输出样例

1 输入样例

5

1 2

2 4

2 5

1 3

1 2 3 4 5

6

4 2 3

2 1 2

4 2 3

1 3 5

3 2 1 4

4 1 4

2 输出样例

3

-1

7

四 注意

在第 1 种操作中，若节点 x 、y 属于同一棵树，则是特殊的。

在第 2 种操作中，若x =y 或者x 、y 不属于同一棵树，则是特殊的。

在第 3 种操作中，若x 、y 不属于同一棵树，则是特殊的。

在第 4 种操作中，若x 、y 不属于同一棵树，则是特殊的。

五 分析

根据输入样例，构建的树形结构如下图所示。

输入样例的 6 种操作如下。

（1）4 2 3：查询 2-3 的最大节点权值，输出 3。

（2）2 1 2：找到包含节点 1 的树，使节点 1 成为该树的根，然后删除节点 2 与其父节点之间的边，实际上就是删除 1-2 的边。

（3）4 2 3：查询 2-3 的最大节点权值，2、3 不属于同一棵树，是非法的，输出 -1。

（4）1 3 5：连接 3-5 的边。

（5）3 2 1 4：将 1-4 路径上的节点权值加 2。

（6）4 1 4：查询 1-4 的最大节点权值，输出 7。

六 设计

本问题包含 4 种基本操作。

（1）连边：在 x、y 之间连接一条新边，若 x、y 属于同一棵树，则非法，输出 -1；否则执行 link(x , y)。

（2）删边：删除 x、y 之间的边。若 x=y 或者 x、y 不属于同一棵树，则非法，输出 -1；否则执行 cut(x , y )。

（3）区间更新：将 x 到 y 路径上所有节点的权值都增加 w 。若节点 x、y 不属于同一棵树，则非法，输出-1；否则执行 addval(x , y ,w )。

（4）区间最值查询：输出 x 到 y 路径上节点的最大权值。若节点 x、y 不属于同一棵树，则非法，输出-1；否则执行 split(x , y )，输出 mx[y]。

七 代码

package com.platform.modules.alg.alglib.hdu4010;
 
public class Hdu4010 {
    private int inf = 0x3f3f3f3f;
    private int N = 300005;
 
    int n, m, top;
    int c[][] = new int[N][2];
    int fa[] = new int[N];
    int v[] = new int[N];
    int st[] = new int[N];
    int add[] = new int[N];
    int mx[] = new int[N];
    int rev[] = new int[N];
 
    void update(int x) {
        int l = c[x][0], r = c[x][1];
        mx[x] = Math.max(mx[l], mx[r]);
        mx[x] = Math.max(mx[x], v[x]);
    }
 
    void pushdown(int x) {
        int l = c[x][0], r = c[x][1];
        if (rev[x] == 1) {
            rev[l] ^= 1;
            rev[r] ^= 1;
            rev[x] ^= 1;
            int temp = c[x][0];
            c[x][0] = c[x][1];
            c[x][1] = temp;
        }
        if (add[x] > 0) {
            if (l > 0) {
                add[l] += add[x];
                mx[l] += add[x];
                v[l] += add[x];
            }
            if (r > 0) {
                add[r] += add[x];
                mx[r] += add[x];
                v[r] += add[x];
            }
            add[x] = 0;
        }
    }
 
    boolean isroot(int x) {
        return c[fa[x]][0] != x && c[fa[x]][1] != x;
    }
 
    void rotate(int x) {
        int y = fa[x], z = fa[y], k;
        if (c[y][0] == x) {
            k = 1;
        } else {
            k = 0;
        }
        if (!isroot(y)) c[z][c[z][1] == y ? 1 : 0] = x;
        fa[x] = z;
        fa[y] = x;
        fa[c[x][k]] = y;
        c[y][k == 0 ? 1 : 0] = c[x][k];
        c[x][k] = y;
        update(y);
        update(x);
    }
 
    void splay(int x) {
        top = 0;
        st[++top] = x;
        for (int i = x; !isroot(i); i = fa[i])
            st[++top] = fa[i];
        while (top > 0) pushdown(st[top--]);
        while (!isroot(x)) {
            int y = fa[x], z = fa[y];
            if (!isroot(y)) {
                if (c[y][0] == x ^ c[z][0] == y) {
                    rotate(x);
                } else {
                    rotate(y);
                }
            }
            rotate(x);
        }
    }
 
    void access(int x) {
        for (int t = 0; x > 0; t = x, x = fa[x]) {
            splay(x);
            c[x][1] = t;
            update(x);
        }
    }
 
    void makeroot(int x) {
        access(x);
        splay(x);
        rev[x] ^= 1;
    }
 
    void link(int x, int y) {
        makeroot(x);
        fa[x] = y;
    }
 
    void split(int x, int y) {
        makeroot(x);
        access(y);
        splay(y);
    }
 
    void cut(int x, int y) {
        split(x, y);
        c[y][0] = fa[c[y][0]] = 0;
        update(y);
    }
 
    int findroot(int x) {
        access(x);
        splay(x);
        while (c[x][0] > 0) x = c[x][0];
        return x;
    }
 
    void addval(int x, int y, int val) {
        split(x, y);
        add[y] += val;
        mx[y] += val;
        v[y] += val;
    }
 
    public String output = "";
 
    public String cal(String input) {
        int opt, x, y, w;
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
 
        for (int i = 0; i <= n; i++)
            add[i] = rev[i] = fa[i] = c[i][0] = c[i][1] = 0;
        mx[0] = -inf;
        for (int i = 1; i < n; i++) {
            String[] num = line[i].split(" ");
            x = Integer.parseInt(num[0]);
            y = Integer.parseInt(num[1]);
            link(x, y);
        }
        String[] wi = line[n].split(" ");
        for (int i = 1; i <= n; i++) {
            v[i] = Integer.parseInt(wi[i - 1]);
            mx[i] = v[i];
        }
        m = Integer.parseInt(line[n + 1]);
        int count = 0;
        while (m-- > 0) {
            String[] query = line[n + 2 + count++].split(" ");
            opt = Integer.parseInt(query[0]);
            x = Integer.parseInt(query[1]);
            y = Integer.parseInt(query[2]);
            switch (opt) {
                case 1:
                    if (findroot(x) == findroot(y)) {
                        output += "-1\n";
                        break;
                    }
                    link(x, y);
                    break;
                case 2:
                    if (findroot(x) != findroot(y) || x == y) {
                        output += "-1\n";
                        break;
                    }
                    cut(x, y);
                    break;
                case 3:
                    w = x;
                    x = y;
                    y = Integer.parseInt(query[3]);
                    if (findroot(x) != findroot(y)) {
                        output += "-1\n";
                        break;
                    }
                    addval(x, y, w);
                    break;
                case 4:
                    if (findroot(x) != findroot(y)) {
                        output += "-1\n";
                        break;
                    }
                    split(x, y);
                    output += mx[y] + "\n";
                    break;
            }
        }
        return output;
    }
}

八 测试