关于根节点

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

#define inf 0x3f3f3f3f
#define ls (id<<1)
#define rs (id<<1|1)
#define mid ((l+r)>>1)

using namespace std;
const int maxn=2e5+5;

struct Segment_Tree{
    int maxd,mind,sum;
    bool lazy;
}tr[maxn<<2];
int n,m;
struct Edge{
    int v,w,next;
}e[maxn<<1];
int p[maxn],len;
int dfn[maxn],timestamp;
int top[maxn];
int siz[maxn],depth[maxn];
int son[maxn],fa[maxn];
int w[maxn],v[maxn];

void add(int u,int v,int w){
    e[len]=(Edge){v,w,p[u]},p[u]=len++;
}

void pushup(int id){
    tr[id].sum=tr[ls].sum+tr[rs].sum;
    tr[id].maxd=max(tr[ls].maxd,tr[rs].maxd);
    tr[id].mind=min(tr[ls].mind,tr[rs].mind);
}

void pushdown(int id){
    if (tr[id].lazy){
        tr[ls].lazy^=1;
        tr[rs].lazy^=1;
        tr[ls].sum*=-1,tr[rs].sum*=-1;
        tr[ls].maxd*=-1,tr[ls].mind*=-1,swap(tr[ls].maxd,tr[ls].mind);
        tr[rs].maxd*=-1,tr[rs].mind*=-1,swap(tr[rs].maxd,tr[rs].mind);
        tr[id].lazy=false;
    }
}

void build(int id,int l,int r){
    if (l==r){
        tr[id].sum=tr[id].maxd=tr[id].mind=w[l];
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(id);
}

void change(int id,int l,int r,int x,int v){//把这个数改掉
    if (l==r){
        tr[id].sum=tr[id].maxd=tr[id].mind=v;
        return;
    }
    pushdown(id);
    if (x<=mid) change(ls,l,mid,x,v);
    else change(rs,mid+1,r,x,v);
    pushup(id);
}

void update(int id,int l,int r,int a,int b){//变成相反数
    if (a<=l&&r<=b){
        tr[id].lazy^=1;
        tr[id].sum*=-1;
        tr[id].maxd*=-1,tr[id].mind*=-1;
        swap(tr[id].maxd,tr[id].mind);
        return;
    }
    pushdown(id);
    if (a<=mid) update(ls,l,mid,a,b);
    if (b>mid) update(rs,mid+1,r,a,b);
    pushup(id);
}

int query_sum(int id,int l,int r,int a,int b){//SUM
    if (a<=l&&r<=b){
        return tr[id].sum;
    }
    int res=0;
    pushdown(id);
    if (a<=mid) res+=query_sum(ls,l,mid,a,b);
    if (b>mid) res+=query_sum(rs,mid+1,r,a,b);
    return res;
}

int query_max(int id,int l,int r,int a,int b){
    if (a<=l&&r<=b){
        return tr[id].maxd;
    }
    int res=-inf;
    pushdown(id);
    if (a<=mid) res=max(res,query_max(ls,l,mid,a,b));
    if (b>mid) res=max(res,query_max(rs,mid+1,r,a,b));
    return res;
}

int query_min(int id,int l,int r,int a,int b){
    if (a<=l&&r<=b){
        return tr[id].mind;
    }
    int res=inf;
    pushdown(id);
    if (a<=mid) res=min(res,query_min(ls,l,mid,a,b));
    if (b>mid) res=min(res,query_min(rs,mid+1,r,a,b));
    return res;
}

void dfs1(int u,int f){
    fa[u]=f;
    depth[u]=depth[f]+1;
    siz[u]=1;
    int maxsize=-1;
    for (int i=p[u];~i;i=e[i].next){
        int vi=e[i].v,wi=e[i].w;
        if (vi==f) continue;
        v[vi]=wi;
        dfs1(vi,u);
        siz[u]+=siz[vi];
        if (maxsize<siz[vi]){
            maxsize=siz[vi];
            son[u]=vi;
        }
    }
}

void dfs2(int u,int t){
    dfn[u]=++timestamp;
    top[u]=t;
    w[timestamp]=v[u];
    if (!son[u]) return;
    dfs2(son[u],t);
    for (int i=p[u];~i;i=e[i].next){
        int v=e[i].v;
        if (v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

/* 注意！边权变成点权，不能算lca的权值 */
int qsum(int x,int y){
    int res=0;
    while (top[x]!=top[y]){
        if (depth[top[x]]<depth[top[y]]){
            swap(x,y);
        }
        res+=query_sum(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if (depth[x]>depth[y]) swap(x,y);
    if (x!=y) res+=query_sum(1,1,n,dfn[x]+1,dfn[y]);
    return res;
}

int qmax(int x,int y){
    int res=-inf;
    while (top[x]!=top[y]){
        if (depth[top[x]]<depth[top[y]]){
            swap(x,y);
        }
        res=max(res,query_max(1,1,n,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if (depth[x]>depth[y]) swap(x,y);
    if (x!=y) res=max(res,query_max(1,1,n,dfn[x]+1,dfn[y]));
    return res;
}

int qmin(int x,int y){
    int res=inf;
    while (top[x]!=top[y]){
        if (depth[top[x]]<depth[top[y]]){
            swap(x,y);
        }
        res=min(res,query_min(1,1,n,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if (depth[x]>depth[y]) swap(x,y);
    if (x!=y) res=min(res,query_min(1,1,n,dfn[x]+1,dfn[y]));
    return res;
}

void uchain(int x,int y){
    while (top[x]!=top[y]){
        if (depth[top[x]]<depth[top[y]]){
            swap(x,y);
        }
        update(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if (depth[x]>depth[y]) swap(x,y);
    if (x!=y) update(1,1,n,dfn[x]+1,dfn[y]);
}

void upoint(int x,int val){
    int p=x*2-1;
    int u=e[p].v,v=e[p^1].v;
    if (fa[u]==v) swap(u,v);
    change(1,1,n,dfn[v],val);
}

int main(){
    freopen("/Users/liyumei1973/Downloads/P1505_10.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(p,-1,sizeof p);

    cin >> n;
    for (int i=1,u,v,w;i<n;i++){
        cin >> u >> v >> w;
        add(u,v,w),add(v,u,w);
    }
    cin >> m;

    dfs1(0,-1);
    dfs2(0,0);
    build(1,1,n);
    string opt;
    int u,v,w,i;
    
    while (m--){
        cin >> opt;
        if (opt=="C"){
            cin >> i >> w;
            upoint(i,w);
        }
        else if (opt=="N"){
            cin >> u >> v;
            uchain(u,v);
        }
        else if (opt=="SUM"){
            cin >> u >> v;
            cout << qsum(u,v) << endl;
        }
        else if (opt=="MAX"){
            cin >> u >> v;
            cout << qmax(u,v) << endl;
        }
        else{
            cin >> u >> v;
            cout << qmin(u,v) << endl;
        }
    }

    return 0;
}

dfs1(1,-1);
dfs2(1,1);
build(1,1,n);