RT

输出和测试点归并了一下，发现都是max和min处理问题，sum没有，害

希望钓上一个大佬

#include<iostream>
using namespace std;

const int N=6e5+10;
const int INF=6e5;
typedef pair<int,int> PII;

int n,q;
int a[N];

struct yq{
    int to,Next;
}edge[N];
int head[N],cnt_edge;

void add(int from,int to){
    edge[++cnt_edge].to=to;
    edge[cnt_edge].Next=head[from];
    head[from]=cnt_edge;
}

int size[N],depth[N],fa[N],heavy_son[N];

void dfs1(int father,int son){
    size[son]++;
    depth[son]=depth[father]+1;
    fa[son]=father;
    for(int i=head[son];i;i=edge[i].Next){
        int to=edge[i].to;
        if(to==father) continue;
        //cout<<son<<" "<<to<<endl;
        dfs1(son,to);
        size[son]+=size[to];
        if(size[to]>size[heavy_son[son]]) heavy_son[son]=to;
    }
    //cout<<"ji"<<son<<" "<<heavy_son[son]<<endl;
}

int top[N],new_idx[N],new_point_min[N],new_point_max[N],new_point[N],point;

void dfs2(int father,int son,int k){
    top[son]=k;
    new_idx[son]=++point;
    if(son<=n){
        new_point_max[point]=-INF;
        new_point_min[point]=INF;
        new_point[point]=0;
    }
    else{
        new_point_max[point]=new_point_min[point]=new_point[point]=a[son];
    }
    if(heavy_son[son]) dfs2(son,heavy_son[son],k);
    for(int i=head[son];i;i=edge[i].Next){
        int to=edge[i].to;
        if(to==father) continue;
        if(to==heavy_son[son]) continue;
        dfs2(son,to,to);
    }
}

int sum[N*4],lazy[N*4],maxn[N*4],minn[N*4];

void build(int idx,int l,int r){
    if(l==r){
        sum[idx]=new_point[l];
        maxn[idx]=new_point_max[l];
        minn[idx]=new_point_min[l];
        return;
    }
    int mid=(l+r)/2;
    build(idx*2,l,mid);
    build(idx*2+1,mid+1,r);
    sum[idx]=sum[idx*2]+sum[idx*2+1];
    maxn[idx]=max(maxn[idx*2],maxn[idx*2+1]);
    minn[idx]=min(minn[idx*2],minn[idx*2+1]);
}

void Change(int idx,int l,int r){
    lazy[idx]*=(-1);
    sum[idx]=(-1)*sum[idx];
    swap(maxn[idx],minn[idx]);
    maxn[idx]*=-1;
    minn[idx]*=-1;
}

void push_down(int idx,int l,int r){
    if(lazy[idx]==1) return;
    int mid=(l+r)/2;
    Change(idx*2,l,mid);
    Change(idx*2+1,mid+1,r);
    lazy[idx]=1;
}

void change(int idx,int l,int r,int dl,int dr,int k,int op){
    //cout<<l<<" "<<r<<" "<<dl<<" "<<dr<<endl;
    if(l==dl&&r==dr){
        if(op==1){
            sum[idx]=k;
            maxn[idx]=max(k,maxn[idx]);
            minn[idx]=min(k,minn[idx]);
        }
        else Change(idx,l,r);
        return;
    }
    push_down(idx,l,r);
    int mid=(l+r)/2;
    if(dr<=mid) change(idx*2,l,mid,dl,dr,k,op);
    else if(dl>mid) change(idx*2+1,mid+1,r,dl,dr,k,op);
    else{
        change(idx*2,l,mid,dl,mid,k,op);
        change(idx*2+1,mid+1,r,mid+1,dr,k,op);
    }
    sum[idx]=sum[idx*2]+sum[idx*2+1];
    maxn[idx]=max(maxn[idx*2],maxn[idx*2+1]);
    minn[idx]=min(minn[idx*2],minn[idx*2+1]);
}

int check(int idx,int l,int r,int dl,int dr,int op){
    //cout<<l<<" "<<r<<" "<<dl<<" "<<dr<<" "<<op<<"ji"<<endl;
    if(l==dl&&r==dr){
        if(op==1) return sum[idx];
        else if(op==2) return maxn[idx];
        else return minn[idx];
    }
    push_down(idx,l,r);
    int mid=(l+r)/2;
    if(op==1){
        int ans=0;
        if(dr<=mid) ans+=check(idx*2,l,mid,dl,dr,op);
        else if(dl>mid) ans+=check(idx*2+1,mid+1,r,dl,dr,op);
        else{
           ans+=check(idx*2,l,mid,dl,mid,op);
           ans+=check(idx*2+1,mid+1,r,mid+1,dr,op);   
        }
        return ans;
    }
    else if(op==2){
        int MAX=-INF;
        if(dr<=mid) MAX=max(check(idx*2,l,mid,dl,dr,op),MAX);
        else if(dl>mid) MAX=max(check(idx*2+1,mid+1,r,dl,dr,op),MAX);
        else{
            MAX=max(check(idx*2,l,mid,dl,mid,op),MAX);
            MAX=max(check(idx*2+1,mid+1,r,mid+1,dr,op),MAX);
        }
        return MAX;
    }
    else{
        int MIN=INF;
        if(dr<=mid) MIN=min(check(idx*2,l,mid,dl,dr,op),MIN);
        else if(dl>mid) MIN=min(check(idx*2+1,mid+1,r,dl,dr,op),MIN);
        else{
            MIN=min(check(idx*2,l,mid,dl,mid,op),MIN);
            MIN=min(check(idx*2+1,mid+1,r,mid+1,dr,op),MIN);
        }
        return MIN;
    }
}

PII stk[N];
int cnt_top;

void find_path(int x,int y){
    while(top[x]!=top[y]){
        if(depth[top[x]]<depth[top[y]]) swap(x,y);
        stk[++cnt_top]={new_idx[top[x]],new_idx[x]};
        x=fa[top[x]];
    }
    if(new_idx[x]>new_idx[y]) swap(x,y);
    //cout<<x<<" "<<new_idx[x]<<" "<<y<<" "<<new_idx[y]<<endl;
    stk[++cnt_top]={new_idx[x],new_idx[y]};
}

void change_path(int x,int y){
    find_path(x,y);
    for(int i=1;i<=cnt_top;i++){
        change(1,1,point,stk[i].first,stk[i].second,0,2);
    }
    cnt_top=0;
}

int check_path(int x,int y,int op){
    find_path(x,y);
    int ANS=0,MAXN=-INF,MINN=INF;
    for(int i=1;i<=cnt_top;i++){
        //cout<<"jijiji"<<stk[i].first<<" "<<stk[i].second<<endl;
        if(op==1) ANS+=check(1,1,point,stk[i].first,stk[i].second,op);
        else if(op==2) MAXN=max(MAXN,check(1,1,point,stk[i].first,stk[i].second,op));
        else MINN=min(MINN,check(1,1,point,stk[i].first,stk[i].second,op));
    }
    cnt_top=0;
    if(op==1) return ANS;
    else if(op==2) return MAXN;
    else return MINN;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int from,to,w;
        cin>>from>>to>>w;
        from++;
        to++;
        a[i+n]=w;
        add(from,n+i);
        add(n+i,from);
        add(to,n+i);
        add(n+i,to);
    }
    for(int i=1;i<N;i++) lazy[i]=1;
    dfs1(0,1);
    dfs2(0,1,1);
    build(1,1,point);
    // for(int i=1;i<=n+n-1;i++) cout<<new_idx[i]<<" ";
    // cout<<endl;
    // for(int i=1;i<=n+n-1;i++) cout<<new_point_min[i]<<" ";
    // cout<<endl;
    // for(int i=1;i<=n+n-1;i++) cout<<new_point_max[i]<<" ";
    // cout<<endl;
    cin>>q;
    while(q--){
        string op;
        cin>>op;
        if(op=="C"){
            int x,w;
            cin>>x>>w;
            change(1,1,point,new_idx[x+n],new_idx[x+n],w,1);
        }
        else if(op=="N"){
            int x,y;
            cin>>x>>y;
            x++;
            y++;
            change_path(x,y);
        }
        else if(op=="SUM"){
            int x,y;
            cin>>x>>y;
            x++;
            y++;
            //cout<<x<<" "<<y<<"ji"<<endl;
            cout<<check_path(x,y,1)<<endl;
        }
        else if(op=="MAX"){
            int x,y;
            cin>>x>>y;
            x++;
            y++;
            cout<<check_path(x,y,2)<<endl;
        }
        else{
            int x,y;
            cin>>x>>y;
            x++;
            y++;
            cout<<check_path(x,y,3)<<endl;
        }
    }
    return 0;
}

居命！！！（555）