点更新 ，段更新， 段查询。 注意的是 线段树维护区间最大值 ，在反转的时候 不能直接取反，那样就变成了 当时的最小值。
所以维护两个值，一个最小值 一个最大值 ，在进行反转操作的时候，取反并且交换两个值。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<vector> #include<stdlib.h> using namespace std; typedef long long LL; const int maxn = 22222; struct Node { int next; int to; }e[maxn * 2]; int edge[maxn][10]; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int len; int z; int size[maxn]; int son[maxn]; int deep[maxn], father[maxn]; int color[maxn << 2]; int sum[maxn << 2]; int head[maxn]; int pos[maxn]; int top[maxn]; const int INF = 1 << 30; int sum1[maxn << 2]; void add(int from, int to) { e[len].to = to; e[len].next = head[from]; head[from] = len++; } void init(int x) { size[x] = 1; son[x] = 0; for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; if (cc == father[x]) continue; father[cc] = x; deep[cc] = deep[x] + 1; init(cc); size[x] += size[cc]; if (size[son[x]] < size[cc]) son[x] = cc; } } void dfs(int x, int tp) { pos[x] = ++z; top[x] = tp; if (son[x]) dfs(son[x], tp); for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; if (cc == father[x] || cc == son[x]) continue; dfs(cc, cc); } } void build(int l, int r, int rt) { sum[rt] = -INF; sum1[rt] = INF; color[rt] = 0; if (l == r) return; int mid = (l + r) >> 1; build(lson); build(rson); } void down(int rt) { if (color[rt]){ sum[rt << 1] = -sum[rt << 1]; sum[rt << 1 | 1] = -sum[rt << 1 | 1]; sum1[rt << 1] = -sum1[rt << 1]; sum1[rt << 1 | 1] = -sum1[rt << 1 | 1]; swap(sum[rt << 1], sum1[rt << 1]); swap(sum[rt << 1 | 1], sum1[rt << 1 | 1]); color[rt << 1] ^= 1; color[rt << 1 | 1] ^= 1; color[rt] = 0; } } void up(int rt) { sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]); sum1[rt] = min(sum1[rt << 1], sum1[rt << 1 | 1]); } void update(int L, int R, int l, int r, int rt) { if (L <= l&&r <= R) { color[rt] ^= 1; sum[rt] = -sum[rt]; sum1[rt] = -sum1[rt]; swap(sum[rt], sum1[rt]); return; } int mid = (l + r) >> 1; down(rt); if (L <= mid) update(L, R, lson); if (R > mid) update(L, R, rson); up(rt); } void update1(int key, int ans, int l, int r, int rt) { if (l == r){ sum1[rt] = ans; sum[rt] = ans; return; } down(rt); int mid = (l + r) >> 1; if (key <= mid) update1(key, ans, lson); else update1(key, ans, rson); up(rt); } int ask(int L, int R, int l, int r, int rt) { if (L <= l&&r <= R) return sum[rt]; down(rt); int mid = (l + r) >> 1; int Max = -INF; if (L <= mid) Max = max(Max, ask(L, R, lson)); if (R > mid) Max = max(Max, ask(L, R, rson)); return Max; } int gao(int x, int y) { int Max = -INF; int fx = top[x]; int fy = top[y]; while (fx != fy){ if (deep[fx] < deep[fy]){ swap(x, y); swap(fx, fy); } Max = max(Max, ask(pos[fx], pos[x], 1, z, 1)); x = father[fx]; fx = top[x]; } if (x == y) return Max; if (deep[x]>deep[y])swap(x, y); Max = max(Max, ask(pos[son[x]], pos[y], 1, z, 1)); return Max; } void gao1(int x, int y) { int fx = top[x]; int fy = top[y]; while (fx != fy){ if (deep[fx]<deep[fy]) swap(x, y), swap(fx, fy); update(pos[fx], pos[x], 1, z, 1); x = father[fx]; fx = top[x]; } if (x == y) return; if (deep[x]>deep[y]) swap(x, y); update(pos[son[x]], pos[y], 1, z, 1); } int main() { // freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int t; scanf("%d", &t); int n, a, b; char str[1000]; while (t--){ scanf("%d", &n); len = 0; z = 0; memset(head, -1, sizeof(head)); deep[1] = 1; for (int i = 1; i < n; i++){ scanf("%d%d%d", &edge[i][0], &edge[i][1], &edge[i][2]); add(edge[i][0], edge[i][1]); add(edge[i][1], edge[i][0]); } init(1); dfs(1, 1); build(1, z, 1); for (int i = 1; i < n; i++){ int a = edge[i][0]; int b = edge[i][1]; int c = edge[i][2]; if (deep[a]>deep[b]) swap(edge[i][0], edge[i][1]); update1(pos[edge[i][1]], c, 1, z, 1); } while (scanf("%s", str) != EOF){ if (str[0] == 'D') break; if (str[0] == 'Q'){ scanf("%d%d", &a, &b); int t = gao(a, b); printf("%d ", t); } if (str[0] == 'C'){ scanf("%d%d", &a, &b); edge[a][2] = b; update1(pos[edge[a][1]], b, 1, z, 1); } if (str[0] == 'N'){ scanf("%d%d", &a, &b); gao1(a, b); } } } return 0; }