WA on#11 otherTLE石山代码求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,tot,dep[200005],up[200005],sz[200005],in[200005],fa[200005];//dep深度，up链顶，sz子树大小，in时间戳（dfn），fa父亲，重儿子的处理是排序
vector<int> g[200005];//图
array<int,3> a[200005];//边
struct Segment_tree{//石山线段树
    struct node{int l,r,lazy,minn,maxn,sum;}a[800005];
    void build(int op,int l,int r){
    	a[op].l = l;
    	a[op].r = r;
    	if (l == r) return;
    	int mid = (l + r) / 2;
    	build(op * 2,l,mid);
    	build(op * 2 + 1,mid + 1,r);
    }
    void spread(int op){if (a[op].l != a[op].r && a[op].lazy){
        swap(a[op].maxn,a[op].minn);
        a[op].sum = -a[op].sum;
        a[op].maxn = -a[op].maxn;
        a[op].minn = -a[op].minn;
        a[op].lazy ^= 1;
        a[op * 2].lazy ^= 1;
        a[op * 2 + 1].lazy ^= 1;
    }}
    void change(int op,int p,int x){
        if (a[op].l == a[op].r){
            a[op].sum = a[op].maxn = a[op].minn = x;
            return;
        }
        spread(op);
    	int mid = (a[op].l + a[op].r) / 2;
    	if (a[op].l <= p && p <= mid) change(op * 2,p,x);
    	else change(op * 2 + 1,p,x);
    	a[op].sum = a[op * 2].sum + a[op * 2 + 1].sum;
    	a[op].maxn = max(a[op * 2].maxn,a[op * 2 + 1].maxn);
    	a[op].minn = min(a[op * 2].minn,a[op * 2 + 1].minn);
    }
    void shift(int op,int l,int r){
        if (l <= a[op].l && a[op].r <= r){
            a[op].sum = a[op].maxn = a[op].minn = -a[op].minn;
            a[op].lazy ^= 1;
            return;
        }
        spread(op);
    	int mid = (a[op].l + a[op].r) / 2;
    	if (l <= mid && a[op].l <= r) shift(op * 2,l,r);
    	if (l <= a[op].r && mid < r) shift(op * 2 + 1,l,r);
    	a[op].sum = a[op * 2].sum + a[op * 2 + 1].sum;
    	a[op].maxn = max(a[op * 2].maxn,a[op * 2 + 1].maxn);
    	a[op].minn = min(a[op * 2].minn,a[op * 2 + 1].minn);
    }
    int query_sum(int op,int l,int r){
    	if (l <= a[op].l && a[op].r <= r) return a[op].sum;
        spread(op);
    	int mid = (a[op].l + a[op].r) / 2,ans = 0;
    	if (l <= mid && a[op].l <= r) ans += query_sum(op * 2,l,r);
    	if (l <= a[op].r && mid < r) ans += query_sum(op * 2 + 1,l,r);
    	return ans;
    }
    int query_max(int op,int l,int r){
    	if (l <= a[op].l && a[op].r <= r) return a[op].maxn;
        spread(op);
    	int mid = (a[op].l + a[op].r) / 2,ans = INT_MIN;
    	if (l <= mid && a[op].l <= r) ans = max(ans,query_max(op * 2,l,r));
    	if (l <= a[op].r && mid < r) ans = max(ans,query_max(op * 2 + 1,l,r));
    	return ans;
    }
    int query_min(int op,int l,int r){
    	if (l <= a[op].l && a[op].r <= r) return a[op].minn;
        spread(op);
    	int mid = (a[op].l + a[op].r) / 2,ans = INT_MAX;
    	if (l <= mid && a[op].l <= r) ans = min(ans,query_min(op * 2,l,r));
    	if (l <= a[op].r && mid < r) ans = min(ans,query_min(op * 2 + 1,l,r));
    	return ans;
    }
}tree;
void dfs1(int x,int f){
    dep[x] = dep[f] + 1;
    sz[x] = 1;
    fa[x] = f;
    for (int i = 0; i < g[x].size(); i++){
        int nxt = g[x][i];
        if (nxt != f){
            dfs1(nxt,x);
            sz[x] += sz[nxt];
        }
    }
}
void dfs2(int x,int u){
    up[x] = u;
    in[x] = ++tot;
    sort(g[x].begin(),g[x].end(),[](int x,int y){return sz[x] > sz[y];});
    for (int i = 0; i < g[x].size(); i++){
        int nxt = g[x][i];
        if (nxt != fa[x]) dfs2(nxt,i == (x != 1) ? u : nxt);
    }
}
int modify(int x,int y){
    while (up[x] != up[y]){
        if (dep[up[x]] < dep[up[y]]) swap(x,y);
        tree.shift(1,in[up[x]],in[x]);
        x = fa[up[x]];
    }
    tree.shift(1,min(in[x],in[y]) + 1,max(in[x],in[y]));
}
int ask_sum(int x,int y){
    int res = 0;
    while (up[x] != up[y]){
        if (dep[up[x]] < dep[up[y]]) swap(x,y);
        res += tree.query_sum(1,in[up[x]],in[x]);
        x = fa[up[x]];
    }
    return res + tree.query_sum(1,min(in[x],in[y]) + 1,max(in[x],in[y]));
}
int ask_max(int x,int y){
    int res = INT_MIN;
    while (up[x] != up[y]){
        if (dep[up[x]] < dep[up[y]]) swap(x,y);
        res = max(res,tree.query_max(1,in[up[x]],in[x]));
        x = fa[up[x]];
    }
    return max(res,tree.query_max(1,min(in[x],in[y]) + 1,max(in[x],in[y])));
}
int ask_min(int x,int y){
    int res = INT_MAX;
    while (up[x] != up[y]){
        if (dep[up[x]] < dep[up[y]]) swap(x,y);
        res = min(res,tree.query_min(1,in[up[x]],in[x]));
        x = fa[up[x]];
    }
    return min(res,tree.query_min(1,min(in[x],in[y]) + 1,max(in[x],in[y])));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    tree.build(1,1,n);
    for (int i = 1; i < n; i++){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        g[a[i][0]].push_back(a[i][1]);
        g[a[i][1]].push_back(a[i][0]);
    }
    dfs1(1,0);
    dfs2(1,1);
    for (int i = 1; i < n; i++) tree.change(1,max(in[a[i][0]],in[a[i][1]]),a[i][2]);
    for (cin >> m; m--; ){
        string op;
        int x,y;
        cin >> op >> x >> y;
        if (op == "C") tree.change(1,max(in[a[x][0]],in[a[x][1]]),y);
        else if (op == "N") modify(x,y);
        else if (op == "SUM") cout << ask_sum(x,y) << '\n';
        else if (op == "MAX") cout << ask_max(x,y) << '\n';
        else cout << ask_min(x,y) << '\n';
    }
    return 0;
}