树剖板题全 WA

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6;

int siz[N], son[N], head[N], dep[N], fa[N], top[N], cnt, dfn[N], rnk[N], n, tot, val[N];
string s;

struct Node{
	int nxt, to, w;
} e[N];

void dfs1(int u, int f) {
	siz[u] = 1;
	son[u] = -1;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v == f) {
			continue;
		}
		dep[v] = dep[u] + 1;
		fa[v] = u;
		val[v] = e[(i + 1) / 2].w;
		dfs1(v, u);
		siz[u] += siz[v];
		if (son[u] == -1 || siz[v] > siz[son[u]]) {
			son[u] = v;
		}
	}
}

void dfs2(int u, int f) {
	top[u] = f;
	cnt++;
	dfn[u] = cnt;
	rnk[cnt] = u;
	if (son[u] == -1) {
		return ;
	}
	dfs2(son[u], f);
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v != son[u] && v != fa[u]) {
			dfs2(v, v);
		}
	}
}

struct SegTree{
	int maxx[N << 2];
	
	void pushup(int p) {
		maxx[p] = max(maxx[p << 1], maxx[p << 1 | 1]);
	}
	
	void biuld(int p, int l, int r) {
		if (l == r) {
			maxx[p] = val[rnk[p]];
			return ;
		}
		int mid = l + r >> 1;
		biuld(p << 1, l, mid);
		biuld(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	
	int st_querymax(int p, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) {
			return -1e9;
		}
		if (ql <= l && qr >= r) {
			return maxx[p];
		}
		int mid = l + r >> 1;
		int maxx = -1e9;
		if (ql <= mid) {
			maxx = max(maxx, st_querymax(p << 1, l, mid, ql, qr));
		} 
		if (qr > mid) {
			maxx = max(maxx, st_querymax(p << 1 | 1, mid + 1, r, ql, qr));
		}
		return maxx;
	}
	
	void update(int p, int l, int r, int x, int k) {
		if (l == r) {
			maxx[p] = k;
			return ;
		}
		int mid = l + r >> 1;
		if (x <= mid) {
			update(p << 1, l, mid, x, k);
		} else {
			update(p << 1 | 1, mid + 1, r, x, k);
		}
		pushup(p);
	}
} st;

int querymax(int x, int y) {
	int maxx = -1, fx = top[x], fy = top[y];
	while (fx != fy) {
		if (dep[fx] >= dep[fy]) {
			maxx = max(maxx, st.st_querymax(1, 1, n, dfn[fx], dfn[x]));
			x = fa[fx];
		} else {
			maxx = max(maxx, st.st_querymax(1, 1, n, dfn[fy], dfn[y]));
			y = fa[fy];
		}
		fx = top[x];
		fy = top[y];
	}
//	cout << maxx << endl;
	maxx = max(maxx, st.st_querymax(1, 1, n, dfn[x] + 1, dfn[y]));
	return maxx;
}	

void add(int u, int v, int w) {
	e[++tot].to = v;
	e[tot].nxt = head[u];
	e[tot].w = w;
	head[u] = tot;
}

int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	dep[1] = 1;
	dfs1(1, 0);
	dfs2(1, 1);
	st.biuld(1, 1, n);
	while (cin >> s) {
		if (s == "DONE") {
			break;
		}
		if (s == "CHANGE") {
			int x, t, b = 0;
			cin >> x >> t;
			if(dep[e[x].to] > dep[e[x].nxt]) {
				b = e[x].to;
			} else {
				b = e[x].nxt;
			}
			st.update(1, 1, n, dfn[b], t);
		} else {
			int a, b;
			cin >> a >> b;
			if (a == b) {
				cout << "0\n";
			} else {
				cout << querymax(a, b) << endl;
			}
		}
	}
	return 0;
}