题目链接：SPOJ 375

给定一棵 $n$ 个节点的树，边按照输入顺序编号为 $1$ 到 $n - 1$，每条边都有一个权值 $c_i$。需要对这棵树进行若干次操作，操作分为 $2$ 种：

• CHANGE i t：将第 $i$ 条边的权值 $c_i$ 修改为 $t$。
• QUERY a b：询问从节点 $a$ 到 $b$ 的路径上的边权最大值。

询问以 DONE 结束。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 20$，$1 \le n \le 10 ^ 4$，$1 \le c_i, t \le 10 ^ 6$。

Solution

直接把边化为点，然后用 $\text{LCT}$ 维护最大边权即可。当然也可以用树链剖分实现。

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

Code

#include <cstdio>
#include <algorithm>

const int N = 2e4 + 5;

int n, m, val[N];

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    int mx, idx;
    bool rev;
    Node(int _idx = 0) {
        ch[0] = ch[1] = fa = null;
        mx = rev = 0, idx = _idx;
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void reverse() {
        rev ^= 1, std::swap(ch[0], ch[1]);
    }
    void pushup() {
        mx = idx;
        if (ch[0] != null && val[ch[0]->mx] > val[mx]) mx = ch[0]->mx;
        if (ch[1] != null && val[ch[1]->mx] > val[mx]) mx = ch[1]->mx;
    }
    void pushdown() {
        if (rev) {
            ch[0]->reverse();
            ch[1]->reverse();
            rev = 0;
        }
    }
} *a[N];

struct LCT {
    LCT() {
        null = new Node();
        null->ch[0] = null->ch[1] = null->fa = null;
    }
    void build(int n) {
        for (int i = 1; i <= n; i++) {
            a[i] = new Node(i);
            val[i] = 0;
        }
    }
    void clear(int n) {
        delete null;
        for (int i = 1; i <= n; i++) {
            delete a[i];
        }
    }
    void pushtag(Node *x){
        if (!x->isroot()) pushtag(x->fa);
        x->pushdown();
    }
    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) {
        pushtag(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), x->ch[1] = y, x->pushup();
        }
    }
    void makeroot(Node *x) {
        access(x), splay(x), x->reverse();
    }
    void split(Node *x, Node *y) {
        makeroot(x), access(y), splay(y);
    }
    void link(Node *x, Node *y) {
        makeroot(x);
        x->fa = y;
    }
};

int main() {
    int T;
    for (scanf("%d", &T); T--; ) {
        scanf("%d", &n);
        LCT T;
        T.build(n + n - 1);
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d%d", &u, &v, &val[i + n]);
            T.link(a[u], a[i + n]);
            T.link(a[v], a[i + n]);
        }
        while (1) {
            char s[10];
            scanf("%s", s + 1);
            if (s[1] == 'D') break;
            if (s[1] == 'C') {
                int x, w;
                scanf("%d%d", &x, &w);
                T.splay(a[x + n]);
                val[x + n] = w;
                a[x + n]->pushup();
            } else {
                int u, v;
                scanf("%d%d", &u, &v);
                T.split(a[u], a[v]);
                printf("%d\n", val[a[v]->mx]);
            }
        }
        T.clear(n + n - 1);
    }
    return 0;
}