SPOJ 375 边操作

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define sz size()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e4 + 5;
int N, M, T;

// 线段树 
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int seg[maxN << 2];
void push_up(int rt) { seg[rt] = max(seg[rt << 1], seg[rt << 1 | 1]); }
void build(int l, int r, int rt) {
    seg[rt] = 0;
    if (l == r) return;
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
}
int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R)
        return seg[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m) ret = max(ret, query(L, R, lson));
    if (R > m) ret = max(ret, query(L, R, rson));
    return ret;
}
void update(int p, int x, int l, int r, int rt) {
    if (l == r) {
        seg[rt] = x;
        return;
    }
    int m = (r + l) >> 1;
    if (p <= m) update(p, x, lson);
    else update(p, x, rson);
    push_up(rt);
}

// 树链剖分
struct Edge {
    int to, next;
} edge[maxN * 2];

int head[maxN], tot;
int top[maxN];  // top[v]即v所在重链的顶端结点
int fa[maxN];   // 父节点
int deep[maxN]; // 深度
int num[maxN];  // num[v] 以v为根的子树结点数
int p[maxN];    // p[v]为v的dfs位置
int fp[maxN];   // 与p相反
int son[maxN];  // 重子编号
int pos;

void init() {
    tot = 0;
    pos = 0;
    mst(head, -1);
    mst(son, -1);
}

void addEdge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void dfs1(int u, int pre, int d) {
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != pre) {
            dfs1(v, u, d + 1);
            num[u] += num[v];
            if (son[u] == -1 || num[v] > num[son[u]])
                son[u] = v;
        }
    }
}

void getPos(int u, int sp) {
    top[u] = sp;
    p[u] = pos++;
    fp[p[u]] = u;
    if (son[u] == -1)
        return;
    getPos(son[u], sp);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u])
            getPos(v, v);
    }
}

// 查询u->v边的max
int findMax(int u, int v) {
    int f1 = top[u], f2 = top[v];
    int tmp = 0;
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        tmp = max(tmp, query(p[f1], p[u], 0, pos - 1, 1));
        u = fa[f1];
        f1 = top[u];
    }
    if (u == v) return tmp;
    if (deep[u] > deep[v]) swap(u, v);
    return max(tmp, query(p[son[u]], p[v], 0, pos - 1, 1));
}

int e[maxN][3];

// CHANGE i ti 修改第i条边的值为ti
// QUERY a b 询问a到b的最大边权
// DONE 结束符号
int main() {
//#ifndef ONLINE_JUDGE
//    freopen("data.in", "r", stdin);
//#endif

    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d", &N);
        rep(i, 0, N - 1) {
            scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
            addEdge(e[i][0], e[i][1]);
            addEdge(e[i][1], e[i][0]);
        }
        dfs1(1, 0, 0);
        getPos(1, 1);
        build(0, pos - 1, 1);

        rep(i, 0, N - 1) {
            if (deep[e[i][0]] > deep[e[i][1]])
                swap(e[i][0], e[i][1]);
            update(p[e[i][1]], e[i][2], 0, pos - 1, 1);
        }
        char op[10];
        int u, v;
        while (~scanf("%s", op)) {
            if (op[0] == 'D') break;
            scanf("%d %d", &u, &v);
            if (op[0] == 'C')
                update(p[e[u - 1][1]], v, 0, pos - 1, 1);
            else
                printf("%d\n", findMax(u, v));
        }
    }
    return 0;
}