https://www.luogu.com.cn/record/111889131

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct edge{int fr,ed,w,nxt;}e[N<<1];
struct node{int sum,Mx,Mn,l,r,op;}t[N<<2];
int n,m,tot,nbs[N],fa[N],dfn[N],nfd[N],top[N],ct[N],hs[N],dep[N],key[N];
void add(int x,int y,int z)
{
    e[++tot].nxt=nbs[x];
    e[tot].fr=x;e[tot].ed=y;e[tot].w=z;nbs[x]=tot;
    return;
}
//预处理
void dfs1(int u)
{
    ct[u]=1;dep[u]=dep[fa[u]]+1;
    for(int x=nbs[u];x;x=e[x].nxt)
        if(e[x].ed!=fa[u]){
            int v;
            fa[v=e[x].ed]=u;key[v]=e[x].w;
            dfs1(v);
            ct[u]+=ct[v];hs[u]=ct[v]>ct[hs[u]]?v:hs[u];
        }
    return;
}
void dfs2(int u,int T)
{
    top[u]=T;dfn[u]=++dfn[0];nfd[dfn[0]]=u;
    if(hs[u])dfs2(hs[u],T);
    for(int x=nbs[u];x;x=e[x].nxt)if(e[x].ed!=fa[u]&&e[x].ed!=hs[u])dfs2(e[x].ed,e[x].ed);
    return;
}
//线段树
void Opp(int u)//取反
{
    t[u].Mx=-t[u].Mx;t[u].Mn=-t[u].Mn;
    swap(t[u].Mx,t[u].Mn);t[u].sum=-t[u].sum;
    t[u].op++;return;
}
void pushup(int u)//上传重置
{
    t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
    t[u].Mx=max(t[u<<1].Mx,t[u<<1|1].Mx);
    t[u].Mn=min(t[u<<1].Mn,t[u<<1|1].Mn);
    return;
}
void pushdown(int u)//下传取反
{
    if((t[u<<1].op&1)!=(t[u].op&1)&&t[u<<1].op<t[u].op)Opp(u<<1);
    if((t[u<<1|1].op&1)!=(t[u].op&1)&&t[u<<1|1].op<t[u].op)Opp(u<<1|1);
    return;
}
void Build(int u,int L,int R)//建树
{
    t[u].l=L;t[u].r=R;
    if(L==R){t[u].sum=t[u].Mn=t[u].Mx=key[nfd[L]];return;}
    int mid=L+R>>1;
    Build(u<<1,L,mid);Build(u<<1|1,mid+1,R);
    pushup(u);
    return;
}
void Mdf(int u,int aim,int val)//单点赋值
{
    if(t[u].l==aim&&t[u].r==aim){t[u].sum=t[u].Mn=t[u].Mx=val;return;}
    pushdown(u);
    int mid=t[u].l+t[u].r>>1;
    if(mid>=aim)Mdf(u<<1,aim,val);else Mdf(u<<1|1,aim,val);
    pushup(u);
    return;
}
void Oppst(int u,int L,int R)//区间取反
{
    if(t[u].l>R||t[u].r<L)return;
    if(t[u].l>=L&&t[u].r<=R){Opp(u);return;}
    pushdown(u);
    int mid=t[u].l+t[u].r>>1;
    if(mid>=L)Oppst(u<<1,L,R);if(mid+1<=R)Oppst(u<<1|1,L,R);
    pushup(u);
    return;
}
int Sqry(int u,int L,int R)//区间求和
{
    if(t[u].l>R||t[u].r<L)return 0;
    if(t[u].l>=L&&t[u].r<=R)return t[u].sum;
    pushdown(u);
    int mid=t[u].l+t[u].r>>1,ret=0;
    if(mid>=L)ret+=Sqry(u<<1,L,R);if(mid+1<=R)ret+=Sqry(u<<1|1,L,R);
    pushup(u);
    return ret;
}
int MXqry(int u,int L,int R)//区间最大值
{
    if(t[u].l>R||t[u].r<L)return -1e9;
    if(t[u].l>=L&&t[u].r<=R)return t[u].Mx;
    pushdown(u);
    int mid=t[u].l+t[u].r>>1,ret=-1e9;
    if(mid>=L)ret=max(ret,MXqry(u<<1,L,R));if(mid+1<=R)ret=max(ret,MXqry(u<<1|1,L,R));
    pushup(u);
    return ret;
}
int MNqry(int u,int L,int R)//区间最小值
{
    if(t[u].l>R||t[u].r<L)return 1e9;
    if(t[u].l>=L&&t[u].r<=R)return t[u].Mn;
    pushdown(u);
    int mid=t[u].l+t[u].r>>1,ret=1e9;
    if(mid>=L)ret=min(ret,MNqry(u<<1,L,R));if(mid+1<=R)ret=min(ret,MNqry(u<<1|1,L,R));
    pushup(u);
    return ret;
}
//树剖
void Modify(int x,int y)//路径取反
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        Oppst(1,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    Oppst(1,dfn[hs[y]],dfn[x]);
    return;
}
int Squery(int x,int y)//路径求和
{
    int ret=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ret+=Sqry(1,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    return ret+Sqry(1,dfn[hs[y]],dfn[x]);
}
int MXquery(int x,int y)//路径最大值
{
    int ret=-1e9;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ret=max(ret,MXqry(1,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    ret=max(ret,MXqry(1,dfn[hs[y]],dfn[x]));
    return ret;
}
int MNquery(int x,int y)//路径最小值
{
    int ret=1e9;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ret=min(ret,MNqry(1,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    ret=min(ret,MNqry(1,dfn[hs[y]],dfn[x]));
    return ret;
}
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);x++,y++;
        add(x,y,z);add(y,x,z);
    }
    dfs1(1);dfs2(1,1);Build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        string opt;int x,y;
        cin>>opt;scanf("%d%d",&x,&y);if(opt!="C")x++,y++;
        if(opt=="C")Mdf(1,max(dfn[e[(x<<1)-1].fr],dfn[e[(x<<1)-1].ed]),y);
        else if(opt=="N")Modify(x,y);
        else if(opt=="SUM")printf("%d\n",Squery(x,y));
        else if(opt=="MAX")printf("%d\n",MXquery(x,y));
        else if(opt=="MIN")printf("%d\n",MNquery(x,y));
    }
    return 0;
}