这个题我调了两个小时了，目前只通过了第 9 个测试点，我太⑨了……

请求大佬帮我把这道题调出来，无比感谢！！

Code:

#include<iostream>
#include<vector>
#include<string>
using namespace std;
#define int long long
const int N=5e5;
int tree[4*N];
int lazy[4*N];
int tmax[4*N];
int tmin[4*N];
struct side{
    int t,n,w,id;
}ss[N];
int head[N];
int pcnt=0;
void add(int f,int t,int w,int id){
    ss[++pcnt].t=t;
    ss[pcnt].w=w;
    ss[pcnt].id=id;
    ss[pcnt].n=head[f];
    head[f]=pcnt;
}
#define FOR(x) for(int nxt=head[x];nxt;nxt=ss[nxt].n)
#define TP ss[nxt].t
#define TW ss[nxt].w
#define lson ((root)<<1)
#define rson ((root<<1)+1)
#define mid ((l+r)>>1)
int dep[N],siz[N],son[N],top[N],fa[N],seg[N],rev[N];
int a[N];
int mapp[N];
void dfs1(int x,int fat){
    fa[x]=fat;
    siz[x]=1;
    dep[x]=dep[fat]+1;
    FOR(x){
        if(TP!=fat){
            mapp[ss[nxt].id]=TP;
            a[TP]=TW;
            dfs1(TP,x);
            siz[x]+=siz[TP];
            if(siz[TP]>siz[son[x]])
                son[x]=TP;
        }
    }
}
int cnt=0;
void dfs2(int x){
    if(son[x]!=0){
        top[son[x]]=top[x];
        seg[son[x]]=++cnt;
        rev[cnt]=son[x];
        dfs2(son[x]);
    }
    FOR(x){
        if(top[TP]==0){
            top[TP]=TP;
            seg[TP]=++cnt;
            rev[cnt]=TP;
            dfs2(TP);
        }
    }
}
void unitupdate(int root,int l,int r){
    tmax[root]=max(tmax[lson],tmax[rson]);
    tmin[root]=min(tmin[lson],tmin[rson]);
    tree[root]=tree[lson]+tree[rson];
}
void pushup(int root,int l,int r){
    tree[root]=-tree[root];
    swap(tmax[root],tmin[root]);
    tmax[root]=-tmax[root];
    tmin[root]=-tmin[root];
    lazy[root]=1-lazy[root];
}
void pushdown(int root,int l,int r){
    if(lazy[root]==0)
        return;
    pushup(lson,l,mid);
    pushup(rson,mid+1,r);
    lazy[root]=0;
}
void build(int root,int l,int r){
    if(l==r){
        tree[root]=a[rev[l]];
        tmin[root]=tmax[root]=tree[root];
        lazy[root]=0;
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    unitupdate(root,l,r);
}
void updateN(int root,int l,int r,int lr,int rr){
    if(lr<=l&&r<=rr){
        pushup(root,l,r);
        return;
    }
    if(r<lr||rr<l)
        return;
    pushdown(root,l,r);
    updateN(lson,l,mid,lr,rr);
    updateN(rson,mid+1,r,lr,rr);
    unitupdate(root,l,r);
}
void updateC(int root,int l,int r,int pos,int val){
    if(l==r){
        lazy[root]=0;
        tmin[root]=tmax[root]=tree[root]=val;
        return;
    }
    pushdown(root,l,r);
    if(pos<=mid)
        updateC(lson,l,mid,pos,val);
    else updateC(rson,mid+1,r,pos,val);
    unitupdate(root,l,r);
}
int querySum(int root,int l,int r,int lr,int rr){
    if(lr<=l&&r<=rr)
        return tree[root];
    if(r<lr||rr<l)
        return 0;
    pushdown(root,l,r);
    return querySum(lson,l,mid,lr,rr)+querySum(rson,mid+1,r,lr,rr);
}
const int INF=0x7ffffff;
int queryMin(int root,int l,int r,int lr,int rr){
    if(lr<=l&&r<=rr)
        return tmin[root];
    if(r<lr||rr<l)
        return INF;
    pushdown(root,l,r);
    return min(queryMin(lson,l,mid,lr,rr),queryMin(rson,mid+1,r,lr,rr));
}
int queryMax(int root,int l,int r,int lr,int rr){
    if(lr<=r&&r<=rr)
        return tmax[root];
    if(r<lr||rr<l)
        return -INF;
    pushdown(root,l,r);
    return max(queryMax(lson,l,mid,lr,rr),queryMax(rson,mid+1,r,lr,rr));
}
void Update(int x,int y){
    int tx=top[x],ty=top[y];
    while(tx!=ty){
        if(dep[tx]<dep[ty])
            swap(tx,ty),swap(x,y);
        updateN(1,1,cnt,seg[tx],seg[x]);
        x=fa[tx];
        tx=top[x];
    }
    if(x==y)
        return;
    if(seg[x]>seg[y])
        swap(x,y);
    updateN(1,1,cnt,seg[x]+1,seg[y]);
}
int QuerySum(int x,int y){
    int ans=0;
    int tx=top[x],ty=top[y];
    while(tx!=ty){
        if(dep[tx]<dep[ty])
            swap(tx,ty),swap(x,y);
        ans+=querySum(1,1,cnt,seg[tx],seg[x]);
        x=fa[tx];
        tx=top[x];
    }
    if(x==y)
        return ans;
    if(seg[x]>seg[y])
        swap(x,y);
    ans+=querySum(1,1,cnt,seg[x]+1,seg[y]);
    return ans;
}
int QueryMax(int x,int y){
    int ans=-INF;
    int tx=top[x],ty=top[y];
    while(tx!=ty){
        if(dep[tx]<dep[ty])
            swap(tx,ty),swap(x,y);
        ans=max(ans,queryMax(1,1,cnt,seg[tx],seg[x]));
        x=fa[tx];
        tx=top[x];
    }
    if(x==y)
        return ans;
    if(seg[x]>seg[y])
        swap(x,y);
    ans=max(ans,queryMax(1,1,cnt,seg[x]+1,seg[y]));
    return ans;
}
int QueryMin(int x,int y){
    int ans=INF;
    int tx=top[x],ty=top[y];
    while(tx!=ty){
        if(dep[tx]<dep[ty])
            swap(tx,ty),swap(x,y);
        ans=min(ans,queryMin(1,1,cnt,seg[tx],seg[x]));
        x=fa[tx];
        tx=top[x];
    }
    if(x==y)
        return ans;
    if(seg[x]>seg[y])
        swap(x,y);
    ans=min(ans,queryMin(1,1,cnt,seg[x]+1,seg[y]));
    return ans;
}
int n,m;
signed main(){
    cin>>n;
    cnt=0;
    for(int x,y,w,i=1;i<n;i++){
        cin>>x>>y>>w;
        x++,y++;
        add(x,y,w,i);
        add(y,x,w,i);
    }
    dfs1(1,0);
    top[1]=1;
    seg[1]=++cnt;
    rev[cnt]=1;
    dfs2(1);
    build(1,1,cnt);
    cin>>m;
    for(int x,y,i=1;i<=m;i++){
        string s;
        cin>>s>>x>>y;
        if(s[0]=='S'){
            x++,y++;
            cout<<QuerySum(x,y)<<endl;
        }else if(s[0]=='M'&&s[1]=='A'){
            x++,y++;
            cout<<QueryMax(x,y)<<endl;
        }else if(s[0]=='M'&&s[1]=='I'){
            x++,y++;
            cout<<QueryMin(x,y)<<endl;
        }else if(s[0]=='N'){
            x++,y++;
            Update(x,y);
        }else{
            updateC(1,1,cnt,seg[mapp[x]],y);
        }
    }
}