题目地址：洛谷：【SP16580】QTREE7 – Query on a tree VII – 洛谷、SPOJ：SPOJ.com – Problem QTREE7

题目描述

You are given a tree (an acyclic undirected connected graph) with n nodes. The tree nodes are numbered from 1 to n. Each node has a color, white or black, and a weight. We will ask you to perfrom some instructions of the following form:

• 0 u: ask for the maximum weight among the nodes which are connected to u, two nodes are connected if all the node on the path from u to v (inclusive u and v) have a same color.
• 1 u: toggle the color of u(that is, from black to white, or from white to black).
• 2 u w: change the weight of u to w.

给一个带点权的树，点有黑白两种颜色。操作：1.询问到u路径上颜色都一样的点中点权的最大值2.改变颜色3.改变点权

输入输出格式

输入格式：
The first line contains a number n denoted how many nodes in the tree(1 ≤ n ≤ 10^5). The next n-1 lines, each line has two numbers (u, v) describe a edge of the tree(1 ≤ u, v ≤ n). The next 2 lines, each line contains n number, the first line is the initial color of each node(0 or 1), and the second line is the initial weight, let’s say Wi, of each node(|Wi| ≤ 10^9). The next line contains a number m denoted how many operations we are going to process(1 ≤ m ≤ 105). The next m lines, each line describe a operation (t, u) as we mentioned above(0 ≤ t ≤ 2, 1 ≤ u ≤ n, |w| ≤ 10^9).

输出格式：
For each query operation, output the corresponding result.

输入输出样例

输入样例#1：

5
1 2
1 3
1 4
1 5
0 1 1 1 1
1 2 3 4 5
3
0 1
1 1
0 1

输出样例#1：

1
5

输入样例#2：

7
1 2
1 3
2 4
2 5
3 6
3 7
0 0 0 0 0 0 0
1 2 3 4 5 6 7
4
0 1
1 1
0 2
0 3

输出样例#2：

7
5
7

题解

参考资料：【Qtree】Query on a tree系列LCT解法 – CSDN博客
可以从QTREE6的代码改过来。QTREE6见：[SPOJ-QTREE6]Query on a tree VI 题解 | KSkun’s Blog
实际上和QTREE6的区别就在于要维护的值变成了若干最大值。那么我们考虑Splay子树直接算，轻边子树用一个set维护，这样方便在access的时候增删元素。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <set>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], ecnt, fa[MAXN], col[MAXN];

inline void addedge(int u, int v, int w) {
    gra[ecnt] = Edge {v, w, head[u]}; head[u] = ecnt++;
}

struct LCT {
    struct LCTNode {
        int ch[2], fa, val, mx;
        std::multiset<int> s;
        bool rev;
    } lct[MAXN];

    inline bool isleft(int p) {
        return lct[lct[p].fa].ch[0] == p;
    }

    inline bool isroot(int p) {
        register int fa = lct[p].fa;
        return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
    }

    inline void update(int p) {
        register int ls = lct[p].ch[0], rs = lct[p].ch[1];
        lct[p].mx = lct[p].val;
        if(!lct[p].s.empty()) lct[p].mx = std::max(lct[p].mx, *--lct[p].s.end());
        if(ls) lct[p].mx = std::max(lct[p].mx, lct[ls].mx);
        if(rs) lct[p].mx = std::max(lct[p].mx, lct[rs].mx);
    }

    inline void reverse(int p) {
        std::swap(lct[p].ch[0], lct[p].ch[1]);
        lct[p].rev ^= 1;
    }

    inline void pushdown(int p) {
        register int ls = lct[p].ch[0], rs = lct[p].ch[1];
        if(lct[p].rev) {
            if(ls) reverse(ls);
            if(rs) reverse(rs);
            lct[p].rev ^= 1;
        }
    }

    int sta[MAXN], stop;

    inline void pushto(int p) {
        stop = 0;
        while(!isroot(p)) {
            sta[stop++] = p;
            p = lct[p].fa;
        }
        pushdown(p);
        while(stop) {
            pushdown(sta[--stop]);
        }
    }

    inline void rotate(int p) {
        register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
        lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
        lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
        lct[p].ch[!t] = fa; lct[fa].fa = p;
        update(fa);
    }

    inline void splay(int p) {
        pushto(p);
        for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
            if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
        }
        update(p);
    }

    inline void access(int p) {
        for(register int q = 0; p; q = p, p = lct[p].fa) {
            splay(p);
            if(lct[p].ch[1]) lct[p].s.insert(lct[lct[p].ch[1]].mx);
            if(q) lct[p].s.erase(lct[p].s.find(lct[q].mx));
            lct[p].ch[1] = q;
            update(p);
        }
    }

    inline void makert(int p) {
        access(p);
        splay(p);
        reverse(p);
    }

    inline int findrt(int p) {
        access(p);
        splay(p);
        while(lct[p].ch[0]) p = lct[p].ch[0];
        return p;
    }

    inline void link(int u) {
        access(fa[u]);
        splay(fa[u]);
        splay(u);
        lct[fa[u]].ch[1] = u;
        lct[u].fa = fa[u];
        update(fa[u]);
    }

    inline void cut(int u) {
        access(u);
        splay(u);
        lct[u].ch[0] = lct[lct[u].ch[0]].fa = 0;
        update(u);
    }

    inline void modify(int u, int w) {
        access(u);
        splay(u);
        lct[u].val = w;
        update(u);
    }

    inline int query(int u) {
        int c = col[u];
        u = findrt(u);
        splay(u);
        return col[u] == c ? lct[u].mx : lct[lct[u].ch[1]].mx;
    }
} L[2];

inline void dfs(int u, int f) {
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(v == f) continue;
        fa[v] = L[col[v]].lct[v].fa = u;
        dfs(v, u);
        L[col[v]].lct[u].s.insert(L[col[v]].lct[v].mx);
    }
    L[0].update(u); L[1].update(u);
}

int n, q, ut, vt, op;

int main() {
    memset(head, -1, sizeof(head));
    n = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        addedge(ut, vt, 1);
        addedge(vt, ut, 1);
    }
    for(int i = 1; i <= n; i++) {
        col[i] = readint();
    }
    for(int i = 1; i <= n; i++) {
        L[0].lct[i].val = L[1].lct[i].val = readint();
    }
    dfs(1, 0);
    q = readint();
    while(q--) {
        op = readint(); ut = readint();
        if(op == 0) {
            printf("%d\n", L[col[ut]].query(ut));
        } else if(op == 1) {
            if(fa[ut]) {
                L[col[ut]].cut(ut);
                L[col[ut] ^ 1].link(ut);
            }
            col[ut] ^= 1;
        } else {
            vt = readint();
            L[0].modify(ut, vt);
            L[1].modify(ut, vt);
        }
    }
    return 0;
}