更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19623719

大意

树上修改，路径和，路径最值，路径取反。

思路

基础树剖 + 线段树维护。

代码

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

#define lc u << 1
#define rc u << 1 | 1
const int MAXN = 2 * 1e5 + 5;
const int INF = 1e9;
int sz[MAXN], top[MAXN], dep[MAXN];
int fa[MAXN], son[MAXN], dfn[MAXN], stk;
int nw[MAXN], n, val[MAXN];
int u_in[MAXN], v_in[MAXN], w_in[MAXN];

struct node{
	int to, nxt, len;
}e[MAXN << 1];
int tot = 0, h[MAXN];

void add(int u, int v, int w){
	e[++ tot] = {v, h[u], w};
	h[u] = tot;
}

void dfs1(int u, int f, int w){
	sz[u] = 1;
	fa[u] = f;
	dep[u] = dep[f] + 1;
	val[u] = w;
	son[u] = 0;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == f) continue;
		dfs1(v, u, e[i].len);
		sz[u] += sz[v];
		if(sz[v] > sz[son[u]]){
			son[u] = v;
		}
	}
}

void dfs2(int u, int tp){
	top[u] = tp;
	dfn[u] = ++ stk;
	nw[stk] = val[u];
	if(!son[u]) return;
	dfs2(son[u], tp);
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa[u] || v == son[u]){
			continue;
		}
		dfs2(v, v);
	}
}

int sum[MAXN << 2];
int mx[MAXN << 2], mn[MAXN << 2];
bool lz[MAXN << 2];

void pushup(int u){
	sum[u] = sum[lc] + sum[rc];
	mx[u] = max(mx[lc], mx[rc]);
	mn[u] = min(mn[lc], mn[rc]);
}

void apply(int u){
	sum[u] = -sum[u];
	swap(mx[u], mn[u]);
	mx[u] = -mx[u];
	mn[u] = -mn[u];
	lz[u] = !lz[u];
}

void pushdown(int u){
	if(lz[u]){
		apply(lc);
		apply(rc);
		lz[u] = 0;
	}
}
void build(int u, int l, int r){
	if(l == r){
		if(l == 1){
			sum[u] = 0, mx[u] = -INF, mn[u] = INF;
		}
		else{
			sum[u] = mx[u] = mn[u] = nw[l];
		}
		return;
	}
	int mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	pushup(u);
}

void p_modify(int u, int l, int r, int x, int v){
	if(l == r){
		sum[u] = mx[u] = mn[u] = v;
		lz[u] = false;
		return;
	}
	pushdown(u);
	int mid = (l + r) >> 1;
	if(x <= mid){
		p_modify(lc, l, mid, x, v);
	}
	else{
		p_modify(rc, mid + 1, r, x, v);
	}
	pushup(u);
}

void l_modify(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		apply(u);
		return;
	}
	pushdown(u);
	int mid = (l + r) >> 1;
	if(L <= mid) l_modify(lc, l, mid, L, R);
	if(R > mid) l_modify(rc, mid + 1, r, L, R);
	pushup(u);
}

int ask_sum(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		return sum[u];
	}
	pushdown(u);
	int ans = 0;
	int mid = (l + r) >> 1;
	if(L <= mid){
		ans += ask_sum(lc, l, mid, L, R);
	}
	if(R > mid){
		ans += ask_sum(rc, mid + 1, r, L, R);
	}
	return ans;
}

int ask_max(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		return mx[u];
	}
	pushdown(u);
	int ans = -INF;
	int mid = (l + r) >> 1;
	if(L <= mid){
		ans = max(ask_max(lc, l, mid, L, R), ans);
	}
	if(R > mid){
		ans = max(ans, ask_max(rc, mid + 1, r, L, R));
	}
	return ans;
}

int ask_min(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		return mn[u];
	}
	pushdown(u);
	int ans = INF;
	int mid = (l + r) >> 1;
	if(L <= mid){
		ans = min(ans, ask_min(lc, l, mid, L, R));
	}
	if(R > mid){
		ans = min(ans, ask_min(rc, mid + 1, r, L, R));
	}
	return ans;
}

void path_modify(int u, int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		l_modify(1, 1, n, dfn[top[u]], dfn[u]);
		u = fa[top[u]];
	}
	if(u == v) return;
	if(dep[u] > dep[v]) swap(u, v);
	l_modify(1, 1, n, dfn[u] + 1, dfn[v]);
}

int path_sum(int u, int v){
	int ans = 0;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		ans += ask_sum(1, 1, n, dfn[top[u]], dfn[u]);
		u = fa[top[u]];
	}
	if(u == v) return ans;
	if(dep[u] > dep[v]){
		swap(u, v);
	}
	ans += ask_sum(1, 1, n, dfn[u] + 1, dfn[v]);
	return ans;
}

int path_max(int u, int v){
	int ans = -INF;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		ans = max(ans, ask_max(1, 1, n, dfn[top[u]], dfn[u]));
		u = fa[top[u]];
	}
	if(u == v) return ans;
	if(dep[u] > dep[v]){
		swap(u, v);
	}
	ans = max(ans, ask_max(1, 1, n, dfn[u] + 1, dfn[v]));
	return ans;
}

int path_min(int u, int v){
	int ans = INF;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		ans = min(ans, ask_min(1, 1, n, dfn[top[u]], dfn[u]));
		u = fa[top[u]];
	}
	if(u == v) return ans;
	if(dep[u] > dep[v]){
		swap(u, v);
	}
	ans = min(ans, ask_min(1, 1, n, dfn[u] + 1, dfn[v]));
	return ans;
}

int main(){
    freopen("travel.in", "r", stdin);
    freopen("travel.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++){
		cin >> u_in[i] >> v_in[i] >> w_in[i];
		u_in[i]++; v_in[i]++;
		add(u_in[i], v_in[i], w_in[i]);
		add(v_in[i], u_in[i], w_in[i]);
	}
	dfs1(1, 0, 0);
	dfs2(1, 1);
	build(1, 1, n);
	int m; cin >> m;
	while(m--){
		string op; cin >> op;
		int x, y; cin >> x >> y;
		if(op == "C"){
			int target = dep[u_in[x]] > dep[v_in[x]] ? u_in[x] : v_in[x];
			p_modify(1, 1, n, dfn[target], y);
		} else {
			x++; y++;
			if(op == "N") path_modify(x, y);
			else if(op == "SUM") cout << path_sum(x, y) << "\n";
			else if(op == "MAX") cout << path_max(x, y) << "\n";
			else if(op == "MIN") cout << path_min(x, y) << "\n";
		}
	}
	return 0;
}