求条AC on #12其他全WA

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 1e6 + 1, INF = 1e18;

int n, m, q, a[MAXN], s[MAXN], maxn[MAXN], minn[MAXN];
int cnt, fa[MAXN], dep[MAXN], siz[MAXN], dfn[MAXN], son[MAXN], top[MAXN], seg[MAXN];
vector<int> c[MAXN];
struct EDGE {
	int x, y, w;
}edge[MAXN]; 

void dfs1(int x, int f) {
    dep[x] = dep[f] + 1;
    fa[x] = f;
    siz[x] = 1;
    for(int i = 0; i < c[x].size(); i++) {
        int y = c[x][i];
        if(y == f) {
            continue;
        }
        dfs1(y, x);
        siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) {
            son[x] = y;
        }
    }
}

void dfs2(int x, int tp) {
    dfn[x] = ++cnt;
    seg[cnt] = x;
    top[x] = tp;
    if(son[x]) {
        dfs2(son[x], tp);
    }
    for(int i = 0; i < c[x].size(); i++) {
        if(c[x][i] != fa[x] && c[x][i] != son[x]) {
            dfs2(c[x][i], c[x][i]);
        }
    }
}

long long lazy_add[MAXN << 2], lazy_mul[MAXN << 2];
void push_up(int k) {
	s[k] = s[k * 2] + s[k * 2 + 1];
	minn[k] = min(minn[k * 2], minn[k * 2 + 1]);
	maxn[k] = max(maxn[k * 2], maxn[k * 2 + 1]);
}
void update_son(int l, int r, int k, int add, int mul) {
	lazy_mul[k] = lazy_mul[k] * mul;
	lazy_add[k] = lazy_add[k] * mul + add;
	s[k] = s[k] * mul;
	s[k] = s[k] + (r - l + 1) * add;
	minn[k] = minn[k] * mul + add;
	maxn[k] = maxn[k] * mul + add;
	if(mul == -1) {
		swap(minn[k], maxn[k]);
	}
}
void push_down(int l, int r, int x) {
	int mid = (l + r) / 2;
	update_son(l, mid, x * 2, lazy_add[x], lazy_mul[x]);
	update_son(mid + 1, r, x * 2 + 1, lazy_add[x], lazy_mul[x]);
	lazy_add[x] = 0;
	lazy_mul[x] = 1;
}
void build(int k, int l, int r) {
	lazy_add[k] = 0;
	lazy_mul[k] = 1;
	if(l == r) {
		s[k] = maxn[k] = minn[k] = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(k * 2, l, mid);
	build(k * 2 + 1, mid + 1, r);
	push_up(k);
}
long long query_sum(int L, int R, int l, int r, int k) {
	if(l >= L && r <= R) {
		return s[k];
	}
	long long mid = (l + r) / 2, res = 0;
	push_down(l, r, k);
	if(L <= mid) {
		res = query_sum(L, R, l, mid, k * 2) + res;
	}
	if(mid < R) {
		res = query_sum(L, R, mid + 1, r, k * 2 + 1) + res;
	}
	return res;
}
long long query_max(int L, int R, int l, int r, int k) {
	if(l >= L && r <= R) {
		return maxn[k];
	}
	long long mid = (l + r) / 2, res = -INF;
	push_down(l, r, k);
	if(L <= mid) {
		res = max(res, query_max(L, R, l, mid, k * 2));
	}
	if(mid < R) {
		res = max(res, query_max(L, R, mid + 1, r, k * 2 + 1));
	}
	return res;
}
long long query_min(int L, int R, int l, int r, int k) {
	if(l >= L && r <= R) {
		return minn[k];
	}
	long long mid = (l + r) / 2, res = INF;
	push_down(l, r, k);
	if(L <= mid) {
		res = min(res, query_min(L, R, l, mid, k * 2));
	}
	if(mid < R) {
		res = min(res, query_min(L, R, mid + 1, r, k * 2 + 1));
	}
	return res;
}
void update(int L, int R, int l, int r, int k, int add, int mul) {
	if(l >= L && r <= R) {
		update_son(l, r, k, add, mul);
		return;
	}
	long long mid = (l + r) / 2;
	push_down(l, r, k);
	if(L <= mid) {
		update(L, R, l, mid, k * 2, add, mul);
	}
	if(mid < R) {
		update(L, R, mid + 1, r, k * 2 + 1, add, mul);
	}
	push_up(k);
}
int LCA_change(int x, int y) {
    int res = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] > dep[top[y]]) {
            update(dfn[top[x]], dfn[x], 1, n, 1, 0, -1);
            x = fa[top[x]];
        }
        else {
            update(dfn[top[y]], dfn[y], 1, n, 1, 0, -1);
            y = fa[top[y]];
        }
    }
    if(dfn[x] > dfn[y]) {
        swap(x, y);
    }
    update(dfn[x] + 1, dfn[y], 1, n, 1, 0, -1);
    return res;
}
int LCA_sum(int x, int y) {
    int res = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] > dep[top[y]]) {
            res += query_sum(dfn[top[x]], dfn[x], 1, n, 1);
            x = fa[top[x]];
        }
        else {
            res += query_sum(dfn[top[y]], dfn[y], 1, n, 1);
            y = fa[top[y]];
        }
    }
    if(dfn[x] > dfn[y]) {
        swap(x, y);
    }
    res += query_sum(dfn[x] + 1, dfn[y], 1, n, 1);
    return res;
}
int LCA_min(int x, int y) {
    int res = INF;
    while(top[x] != top[y]) {
        if(dep[top[x]] > dep[top[y]]) {
            res = min(res, query_min(dfn[top[x]], dfn[x], 1, n, 1));
            x = fa[top[x]];
        }
        else {
            res = min(res, query_min(dfn[top[y]], dfn[y], 1, n, 1));
            y = fa[top[y]];
        }
    }
    if(dfn[x] > dfn[y]) {
        swap(x, y);
    }
    res = min(res, query_min(dfn[x] + 1, dfn[y], 1, n, 1));
    return res;
}
int LCA_max(int x, int y) {
    int res = -INF;
    while(top[x] != top[y]) {
        if(dep[top[x]] > dep[top[y]]) {
			res = max(res, query_max(dfn[top[x]], dfn[x], 1, n, 1));
            x = fa[top[x]];
        }
        else {
            res = max(res, query_max(dfn[top[y]], dfn[y], 1, n, 1));
            y = fa[top[y]];
        }
    }
    if(dfn[x] > dfn[y]) {
        swap(x, y);
    }
    res = max(res, query_max(dfn[x] + 1, dfn[y], 1, n, 1));
    return res;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1, x, y, w; i < n; i++) {
        cin >> x >> y >> w;
        x++, y++;
        c[x].push_back(y);
        c[y].push_back(x);
        edge[i] = {x, y, w};
    }
    dfs1(1, 0);
    dfs2(1, 1);
    
    for(int i = 1; i < n; i++) {
    	int x = edge[i].x, y = edge[i].y, z = edge[i].w;
    	if(dep[x] < dep[y]) {
    		swap(x, y);
		}
		a[x] = z;
	}
    
    build(1, 1, n);
    cin >> q;
    while(q--) {
    	string op;
    	int x, y, i, w;
    	cin >> op;
		if(op == "C") {
			cin >> i >> w;
			int x = edge[i].x, y = edge[i].y;
			if(dep[x] < dep[y]) {
				swap(x, y);
			}
			int tmp = query_sum(dfn[x], dfn[x], 1, n, 1);
			int add = w - tmp;
			update(dfn[x], dfn[x], 1, n, 1, add, 1);
		}
		else if(op == "N") {
			cin >> x >> y;
			x++, y++; 
			LCA_change(x, y);
		}
		else if(op == "SUM") {
			cin >> x >> y;
			x++, y++; 
			cout << LCA_sum(x, y);
			cout << "\n";
		}
		else if(op == "MAX") {
			cin >> x >> y;
			x++, y++; 
			cout << LCA_max(x, y);
			cout << "\n";
		}
		else {
			cin >> x >> y;
			x++, y++; 
			cout << LCA_min(x, y);
			cout << "\n";
		}
    }
    return 0;
}