luoguP1505旅游（处理边权的树剖）

/*
    luogu1505
    非常简单的处理边权的树剖题。
    在树上将一条边定向，把这条边的权值赋给这条边的出点 
    树剖的时候不计算lca权值即可 
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int h=200010;
//线段树部分 
ll a[h];
struct node{
    int l,r;
    ll val,mx,mn;
    ll lz;
}tree[h*4];
void pushup(int root){
    tree[root].val=tree[root*2].val+tree[root*2+1].val;
    tree[root].mx=max(tree[root*2].mx,tree[root*2+1].mx);
    tree[root].mn=min(tree[root*2].mn,tree[root*2+1].mn);
}
void build(int root,int l,int r){
    tree[root].l=l,tree[root].r=r,tree[root].lz=1;
    tree[root].mx=-1010,tree[root].mn=1010;
    if(l==r){
        tree[root].mx=a[l];
        tree[root].mn=a[l];
        tree[root].val=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    pushup(root);
}
void pushdown(int root){//存储区间取反 
    if(tree[root].lz==1)
        return;
    tree[root*2].val*=tree[root].lz;
    tree[root*2+1].val*=tree[root].lz;
    
    swap(tree[root*2].mx,tree[root*2].mn);
    tree[root*2].mx*=-1;
    tree[root*2].mn*=-1;
    
    swap(tree[root*2+1].mx,tree[root*2+1].mn);
    tree[root*2+1].mx*=-1;
    tree[root*2+1].mn*=-1;
    
    tree[root*2].lz*=tree[root].lz;
    tree[root*2+1].lz*=tree[root].lz;
    
    tree[root].lz=1;
}
ll query_sum(int root,int l,int r){//区间和 
    if(tree[root].l>=l&&tree[root].r<=r)
        return tree[root].val;
    pushdown(root);
    int mid=(tree[root].l+tree[root].r)/2;
    ll ans=0;
    if(mid>=l)
        ans+=query_sum(root*2,l,r);
    if(mid<r)
        ans+=query_sum(root*2+1,l,r);
    return ans;
}
ll query_max(int root,int l,int r){//区间最大 
    if(tree[root].l>=l&&tree[root].r<=r)
        return tree[root].mx;
    pushdown(root);
    int mid=(tree[root].l+tree[root].r)/2;
    ll ans=-1010;//这里要设成负数，因为边的权值可能全是负数 
    if(mid>=l)
        ans=max(ans,query_max(root*2,l,r));
    if(mid<r)
        ans=max(ans,query_max(root*2+1,l,r));
    return ans;
}
ll query_min(int root,int l,int r){//区间最小 
    if(tree[root].l>=l&&tree[root].r<=r)
        return tree[root].mn;
    pushdown(root);
    int mid=(tree[root].l+tree[root].r)/2;
    ll ans=1010;
    if(mid>=l)
        ans=min(ans,query_min(root*2,l,r));
    if(mid<r)
        ans=min(ans,query_min(root*2+1,l,r));
    return ans;
}
void change(int root,int p,ll x){//单点修改 
    if(tree[root].l==tree[root].r){
        tree[root].mx=tree[root].mn=tree[root].val=x;
        return;
    }
    pushdown(root);
    int mid=(tree[root].l+tree[root].r)/2;
    if(mid>=p)
        change(root*2,p,x);
    else
        change(root*2+1,p,x);
    pushup(root);
}
void turn(int root,int l,int r){//区间取反 
    if(tree[root].l>=l&&tree[root].r<=r){
        tree[root].mx*=-1,tree[root].mn*=-1;
        swap(tree[root].mx,tree[root].mn);
        tree[root].val*=-1;
        tree[root].lz*=-1;
        return;
    }
    pushdown(root);
    int mid=(tree[root].l+tree[root].r)/2;
    if(mid>=l)
        turn(root*2,l,r);
    if(mid<r)
        turn(root*2+1,l,r);
    pushup(root);
}
int head[h],last[h],to[h],tot=0;
void add_edge(int x,int y){
    tot++;
    last[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
void add(int x,int y){
    add_edge(x,y);
    add_edge(y,x);
}
int n,m,roots;
//树剖部分 
ll w[h];
int fa[h],siz[h],dep[h],mxs[h],dfn[h],top[h],td=0;
void dfs1(int now,int f){
    fa[now]=f,siz[now]=1;
    for(int i=head[now];i;i=last[i]){
        int nex=to[i];
        if(nex==f)
            continue;
        dep[nex]=dep[now]+1;
        dfs1(nex,now);
        siz[now]+=siz[nex];
        if(siz[nex]>siz[mxs[now]]||!mxs[now])
            mxs[now]=nex;
    }
}
void dfs2(int now,int from){
    dfn[now]=++td,a[td]=w[now],top[now]=from;
    if(mxs[now])
        dfs2(mxs[now],from);
    for(int i=head[now];i;i=last[i]){
        int nex=to[i];
        if(nex==fa[now]||nex==mxs[now])
            continue;
        dfs2(nex,nex);
    }
}
void pturn(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        turn(1,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    if(x!=y)
        turn(1,dfn[x]+1,dfn[y]);//这一步操作左端是dfn[x]+1，因为lca的权值代表的边不在路径内 
}
ll pquery_sum(int x,int y){
    ll ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        ans+=query_sum(1,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    if(x!=y)
        ans+=query_sum(1,dfn[x]+1,dfn[y]);//同上 
    return ans;
}
ll pquery_min(int x,int y){
    ll ans=1010;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        ans=min(ans,query_min(1,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    if(x!=y)
        ans=min(ans,query_min(1,dfn[x]+1,dfn[y]));    
    return ans;
}
ll pquery_max(int x,int y){
    ll ans=-1010;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])//这里注意里面是top 
            swap(x,y);
        ans=max(ans,query_max(1,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    if(x!=y)
        ans=max(ans,query_max(1,dfn[x]+1,dfn[y]));
    return ans;    
}

struct edge{
    int p1,p2,out;
    ll len;
}e[h];
int main(){
    scanf("%d",&n);
    //题目里的点从0开始，我们为了方便操作，将所有点加1，从1开始 
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u+1,v+1);
        e[i].p1=u+1,e[i].p2=v+1;
        scanf("%lld",&e[i].len);
    }
    dfs1(1,0);
    for(int i=1;i<n;i++){//给边定向 
        if(fa[e[i].p2]==e[i].p1)
            e[i].out=e[i].p2,w[e[i].p2]=e[i].len;
        else
            e[i].out=e[i].p1,w[e[i].p1]=e[i].len;
    }
    dfs2(1,1);
    build(1,1,td);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        string op;
        cin>>op;    
        if(op=="C"){
            int ed;
            ll ch;
            scanf("%d%lld",&ed,&ch);
            change(1,dfn[e[ed].out],ch);
        }        
        if(op=="N"){
            int x,y;
            scanf("%d%d",&x,&y);
            pturn(x+1,y+1);
        }
        if(op=="SUM"){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",pquery_sum(x+1,y+1));
        }
        if(op=="MAX"){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",pquery_max(x+1,y+1));
        }
        if(op=="MIN"){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",pquery_min(x+1,y+1));
        }        
    }
    return 0;
}