题目链接：SPOJ 16580

给定一棵 $n$ 个节点的树，每个点都有一个黑白颜色和一个点权 $w_i$。接下来进行 $m$ 次操作，操作分为如下 $2$ 种：

• 0 u：询问和点 $u$ 相连的所有点中的最大点权，两个点 $u, v$ 是相连的当且仅当两者路径（包括 $u, v$）上的点颜色相同。
• 1 u：反转点 $u$ 的颜色（黑色变成白色，白色变成黑色）。
• 2 u w：将点 $u$ 的点权修改为 $w$。

数据范围：$1\le n, m\le 10 ^ 5$，$\vert w_i\vert \le 10 ^ 9$。

Solution

本题的套路和 SPOJ 16549（题解）相同，只不过需要维护连通块最大值罢了。又可以搬代码啦 QAQ

时间复杂度：$\mathcal O((n + m)\log n)$。

Code

#include <cstdio>
#include <algorithm>
#include <set>

const int N = 1e5 + 5, M = 2e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, tot, w[N], col[N], lnk[N], ter[M], nxt[M], fa[N];

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    int idx, val, mx;
    std::multiset<int> s;
    Node(int _idx = 0, int _val = 0) {
        ch[0] = ch[1] = fa = null;
        idx = _idx, mx = val = _val;
        s.clear();
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void pushup() {
        mx = std::max(val, std::max(ch[0]->mx, ch[1]->mx));
        if (!s.empty()) {
            mx = std::max(mx, *s.rbegin());
        }
    }
};

struct LCT {
    Node *a[N];
    bool C;
    void build(int n) {
        a[0] = new Node(), a[0] = null;
        for (int i = 1; i <= n; i++) {
            a[i] = new Node(i, w[i]);
        }
    }
    void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        int 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();
    }
    void access(Node *x) {
        for (Node *y = null; x != null; x = (y = x)->fa) {
            splay(x);
            if (x->ch[1] != null) x->s.insert(x->ch[1]->mx);
            if ((x->ch[1] = y) != null) x->s.erase(x->s.find(y->mx));
            x->pushup();
        }
    }
    Node *findroot(Node *x) {
        access(x), splay(x);
        while (x->ch[0] != null) x = x->ch[0];
        splay(x);
        return x;
    }
    void link(Node *x, Node *y) {
        if (y == null) return;
        access(y), splay(y), splay(x);
        x->fa = y;
        y->s.insert(x->mx);
        y->pushup();
    }
    void cut(Node *x, Node *y) {
        if (y == null) return;
        access(x), splay(x);
        x->ch[0] = x->ch[0]->fa = null;
        x->pushup();
    }
    int query(Node *x) {
        Node *f = findroot(x);
        if (col[f->idx] == C) {
            return f->mx;
        } else {
            return f->ch[1]->mx;
        }
    }
} T[2];

void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
void dfs(int u, int p) {
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        fa[v] = u;
        dfs(v, u);
    }
}
void init() {
    null = new Node();
    null->ch[0] = null->ch[1] = null->fa = null;
    null->mx = -INF;
    T[0].build(n), T[0].C = 0;
    T[1].build(n), T[1].C = 1;
    for (int i = 1; i <= n; i++) {
        int c = col[i];
        T[c].link(T[c].a[i], T[c].a[fa[i]]);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &col[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    dfs(1, 0);
    init();
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int opt, u;
        scanf("%d%d", &opt, &u);
        int &c = col[u];
        if (!opt) {
            printf("%d\n", T[c].query(T[c].a[u]));
        } else if (opt == 1) {
            T[c].cut(T[c].a[u], T[c].a[fa[u]]);
            c ^= 1;
            T[c].link(T[c].a[u], T[c].a[fa[u]]);
        } else {
            int w;
            scanf("%d", &w);
            for (int j = 0; j <= 1; j++) {
                T[j].access(T[j].a[u]);
                T[j].splay(T[j].a[u]);
                T[j].a[u]->val = w;
                T[j].a[u]->pushup();
            }
        }
    }
    return 0;
}