记录编号	547760	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	1.714 s
提交时间	2019-12-13 15:04:41	内存使用	14.65 MiB

#include<cstdio>
#include<vector>

using namespace std;
const int N = 10005;
vector<int> g[N];
struct bian {
    int u, v, w;
} e[N];
int top[N], siz[N], father[N], son[N], dep[N], tid[N], rank[N], val[N], tn = 0;
int _max[N << 2] = {0}, _min[N << 2] = {0};
bool flag[N << 2];
char ch[10];

inline int MAX(int x, int y) {
    if (x > y)return x;
    return y;
}

inline int MIN(int x, int y) {
    if (x < y)return x;
    return y;
}

inline void swap(int &x, int &y) {
    x ^= y;
    y ^= x;
    x ^= y;
}

inline void in(int &n) {
    static char c;
    n = 0;
    while (c = getchar(), !(c >= '0' && c <= '9'));
    do n = (n << 3) + (n << 1) + (c ^ '0');
    while (c = getchar(), c >= '0' && c <= '9');
}

inline void dfs1(int x, int fa, int deep) {
    son[x] = -1, siz[x] = 1, father[x] = fa, dep[x] = deep;
    for (int i = 0; i < g[x].size(); i++)
        if (g[x][i] != fa) {
            dfs1(g[x][i], x, deep + 1);
            siz[x] += siz[g[x][i]];
            if (dep[son[x]] < dep[g[x][i]]) son[x] = g[x][i];
        }
}

inline void dfs2(int x, int tp) {
    top[x] = tp, tid[x] = ++tn, rank[tn] = x;
    if (son[x] != -1) dfs2(son[x], tp);
    for (int i = 0; i < g[x].size(); i++)
        if (g[x][i] != father[x] && g[x][i] != son[x]) dfs2(g[x][i], g[x][i]);
}

inline void update(int rt) {
    _max[rt] = MAX(_max[rt << 1], _max[rt << 1 | 1]);
    _min[rt] = MIN(_min[rt << 1], _min[rt << 1 | 1]);
}

inline void push_down(int rt) {
    int t;
    t = _max[rt << 1], _max[rt << 1] = -_min[rt << 1], _min[rt << 1] = -t, flag[rt << 1] = !flag[rt << 1];
    t = _max[rt << 1 | 1], _max[rt << 1 | 1] = -_min[rt << 1 | 1], _min[rt << 1 | 1] = -t, flag[rt << 1 | 1] = !flag[rt << 1 | 1];
    flag[rt] = false;
}

inline void build(int l, int r, int rt) {
    if (l == r) {
        _max[rt] = _min[rt] = val[rank[l]];
        return;
    }
    int m = l + r >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    update(rt);
}

inline void change(int x, int v, int l, int r, int rt) {
    if (l == r) {
        _max[rt] = _min[rt] = v;
        return;
    }
    int m = l + r >> 1;
    if (flag[rt]) push_down(rt);
    if (x <= m) change(x, v, l, m, rt << 1);
    else change(x, v, m + 1, r, rt << 1 | 1);
    update(rt);
}

inline int querymax(int L, int R, int l, int r, int rt) {
    if (l >= L && r <= R) return _max[rt];
    int m = l + r >> 1, ret = -0x7fffffff;
    if (flag[rt]) push_down(rt);
    if (m >= L) ret = querymax(L, R, l, m, rt << 1);
    if (m < R) ret = MAX(ret, querymax(L, R, m + 1, r, rt << 1 | 1));
    return ret;
}

inline void negate(int L, int R, int l, int r, int rt) {
    if (l >= L && r <= R) {
        int t;
        t = _max[rt], _max[rt] = -_min[rt], _min[rt] = -t, flag[rt] = !flag[rt];
        return;
    }
    int m = l + r >> 1;
    if (flag[rt]) push_down(rt);
    if (m >= L) negate(L, R, l, m, rt << 1);
    if (m < R) negate(L, R, m + 1, r, rt << 1 | 1);
    update(rt);
}

inline int findmax(int x, int y) {
    int ret = -0x7fffffff;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret = MAX(ret, querymax(tid[top[x]], tid[x], 1, tn, 1));
        x = father[top[x]];
    }
    if (x == y) return ret;
    if (dep[x] > dep[y]) swap(x, y);
    ret = MAX(ret, querymax(tid[son[x]], tid[y], 1, tn, 1));
    return ret;
}

inline void donegate(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        negate(tid[top[x]], tid[x], 1, tn, 1);
        x = father[top[x]];
    }
    if (x == y) return;
    if (dep[x] > dep[y]) swap(x, y);
    negate(tid[son[x]], tid[y], 1, tn, 1);
}

int main() {
    freopen("maintaintree.in", "r", stdin);
    freopen("maintaintree.out", "w", stdout);
    int n, u, v, w;
    in(n);
    for (int i = 1; i < n; i++)
        in(u), in(v), in(w), g[u].push_back(v), g[v].push_back(u), e[i].u = u, e[i].v = v, e[i].w = w;
    dfs1(1, 1, 1);
    dfs2(1, 1);
    for (int i = 1; i <= n; i++) {
        if (father[e[i].u] != e[i].v) swap(e[i].u, e[i].v);
        val[e[i].u] = e[i].w;
    }
    build(1, n, 1);
    while (1) {
        scanf("%s", ch);
        if (ch[0] == 'D') break;
        in(u), in(v);
        if (ch[0] == 'Q') printf("%d\n", findmax(u, v));
        else if (ch[0] == 'N') donegate(u, v);
        else if (ch[0] == 'C') change(tid[e[u].u], v, 1, n, 1);
    }
    return 0;
}