84分求助-170行

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int fa[N], son[N], head[N];
int siz[N], dep[N], dfn[N], rnk[N];
vector<int>graph[N];
map<pair<int, int>, int>mp;
int n;
void heavy(int u, int Fa, int Dep) {
	siz[u] = 1;
	fa[u] = Fa;
	dep[u] = Dep;
	int msiz = 0, mid = 0;
	for (auto v : graph[u]) {
		if (v == Fa)continue;
		heavy(v, u, Dep + 1);
		if (siz[v] > msiz) {
			msiz = siz[v];
			mid = v;
		}
		siz[u] += siz[v];
	}
	son[u] = mid;
}
int cnt = 0;
void dfs(int u, int Fa, int Head) {
	dfn[u] = ++cnt;
	rnk[cnt] = u;
	head[u] = Head;
	if (son[u])dfs(son[u], u, Head);
	for (auto v : graph[u]) {
		if (v == Fa || v == son[u])continue;
		dfs(v, u, v);
	}
}
struct node {
	int sum = 0, ma = -1001, mi = 1001;
} tree[N * 4];
int tag[N * 4];
node operator+(node a, node b) {
	return {a.sum + b.sum, max(a.ma, b.ma), min(a.mi, b.mi)};
}
void build(int id, int l, int r) {
	if (l == r) {
		int w = mp[ {rnk[l], fa[rnk[l]]}];
		if (fa[rnk[l]])tree[id] = {w, w, w};
		return ;
	}
	int mid = (l + r) >> 1;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	tree[id] = tree[id * 2] + tree[id * 2 + 1];
}
void pushdown(int id) {
	if (tag[id] == -1) {
		tree[id * 2] = {-1 * tree[id * 2].sum, -1 * tree[id * 2].mi, -1 * tree[id * 2].ma};
		tag[id * 2] = -1 * tag[id * 2];
		tree[id * 2 + 1] = {-1 * tree[id * 2 + 1].sum, -1 * tree[id * 2 + 1].mi, -1 * tree[id * 2 + 1].ma};
		tag[id * 2 + 1] = -1 * tag[id * 2 + 1];
		tag[id] = 1;
	}
}
node query(int id, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		return tree[id];
	}
	pushdown(id);
	int mid = (l + r) >> 1;
	node res = {0, -1001, 1001};
	if (ql <= mid)res = res + query(id * 2, l, mid, ql, qr);
	if (qr > mid)res = res + query(id * 2 + 1, mid + 1, r, ql, qr);
	return res;
}
void up(int id, int l, int r, int ql, int qr, int val) {
	if (ql <= l && r <= qr) {
		if (val != -1) {
			tree[id] = {val, val, val};
		} else {
			tag[id] = -1 * tag[id];
			tree[id] = {-1 * tree[id].sum, -1 * tree[id].mi, -1 * tree[id].ma};
		}
		return ;
	}
	pushdown(id);
	int mid = (l + r) >> 1;
	if (ql <= mid)up(id * 2, l, mid, ql, qr, val);
	if (qr > mid)up(id * 2 + 1, mid + 1, r, ql, qr, val);
	tree[id] = tree[id * 2] + tree[id * 2 + 1];
}
node querychain(int x, int y) {
	node res = {0, -1001, 1001};
	while (head[x] != head[y]) {
		if (dep[head[x]] < dep[head[y]]) {
			swap(x, y);
		}
		res = res + query(1, 1, n, dfn[head[x]], dfn[x]);
		x = fa[head[x]];
	}
	if (dep[x] > dep[y]) {
		swap(x, y);
	}
	res = res + query(1, 1, n, dfn[x] + 1, dfn[y]);
	return res;
}
void upchain(int x, int y) {
	while (head[x] != head[y]) {
		if (dep[head[x]] < dep[head[y]]) {
			swap(x, y);
		}
		up(1, 1, n, dfn[head[x]], dfn[x], -1);
		x = fa[head[x]];
	}
	if (dep[x] > dep[y]) {
		swap(x, y);
	}
	up(1, 1, n, dfn[x] + 1, dfn[y], -1);
}
int m;
vector<pair<int, int>>side;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n * 4; i++) {
		tag[i] = 1;
	}
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u++, v++;
		graph[u].push_back(v);
		graph[v].push_back(u);
		mp[ {u, v}] = w;
		mp[ {v, u}] = w;
		side.push_back({u, v});
	}
	heavy(1, 0, 1);
	dfs(1, 0, 1);
	build(1, 1, n);
	cin >> m;
	while (m--) {
		string op;
		int x, y;
		cin >> op >> x >> y;
		x++, y++;
		if (op == "C") {
			x -= 2, y--;
			int a = side[x].first, b = side[x].second;
			if (fa[a] == b) {
				swap(a, b);
			}
			up(1, 1, n, dfn[b], dfn[b], y);
		} else if (op == "N") {
			upchain(x, y);
		} else if (op == "SUM") {
			node ans = querychain(x, y);
			cout << ans.sum << "\n";
		} else if (op == "MAX") {
			node ans = querychain(x, y);
			cout << ans.ma << "\n";
		} else if (op == "MIN") {
			node ans = querychain(x, y);
			cout << ans.mi << "\n";
		}
	}
	return 0;
}

求助，84分