P1505 [国家集训队] 旅游

[国家集训队] 旅游 - 洛谷

相反数，本来想维护相反数的，发现好像直接变相反数就好了

取反后，最大值变成最小值，最小值变成最大值

维护如果写3个query ,就比较麻烦

可以写结构体函数，一个query解决问题

挺好写的

一开始wa，看到标记没下传，后面wa，调了3个点，发现是边权赋值错误

中午12->下午3，因此，中午该吃饭，吃饭，写什么破题，后面码都没仔细看了

code

// Problem: P1505 [国家集训队] 旅游
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1505
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<vector>
using namespace std;
const int N=2e5+9;
int n;
int a[N];
struct edge{
	int u,v,w;	
}ee[N];
//树剖
//1.转成线性部分
vector<edge> e[N];
void add(int u,int v,int w){
    e[u].push_back({v,u,w});
    e[v].push_back({u,v,w});
}
int fa[N],dep[N],sz[N],wc[N],dis[N];
void dfs1(int u,int f){//fa dep sz wc
    fa[u]=f;
    sz[u]=1;
    dep[u]=dep[f]+1;
    for(auto & [x,y,z] : e[u]){
        if(x==f){
            dis[u]=z;//边权给儿子
        }
        if(x!=f){
            dfs1(x,u);
            sz[u]+=sz[x];
            if(sz[x]>sz[wc[u]]){
                wc[u]=x;
            }
        }
    }
}
int dfn[N],rdfn[N],top[N],vistime;
void dfs2(int u,int Top){//dfn rdfn top
    dfn[u]=++vistime;
    a[vistime]=dis[u];//
    top[u]=Top;
    if(wc[u]){
        dfs2(wc[u],Top);
        for(auto & [x,y,z] : e[u]){
            if(x!=wc[u] && x!=fa[u]){
                dfs2(x,x);
            }
        }
    }
}
//2.线段树维护
struct SEG{
    #define INF (1ll<<62)
    #define ll long long
    #define tl(id) (id<<1)
    #define tr(id) (id<<1|1)
    #define li inline
    struct node{
    	int l,r;
    	ll val,mx,mn;
        int rev;
    }seg[N<<2];
    li void pushup(node &id,node &l,node &r){
    	id.val=l.val+r.val;
    	id.mx=max(l.mx,r.mx);
    	id.mn=min(l.mn,r.mn);
    }
	li void pushup(int id){
    	pushup(seg[id],seg[tl(id)],seg[tr(id)]);
    }
    li int inrange(int L,int R,int l,int r){return l<=L && R<=r;}
    li int outofrange(int L,int R,int l,int r){return L>r || R<l;}
    li void build(const int id,int l,int r){
        seg[id].l=l,seg[id].r=r;
        if(l==r){
            seg[id]={l,r,a[l],a[l],a[l],0};
            return;
        }
        int mid=(l+r)>>1;
        build(tl(id),l,mid);
        build(tr(id),mid+1,r);
        pushup(id);
    }
    li void maketag(int id){
        seg[id].rev^=1;
    	seg[id].val*=-1;
    	seg[id].mx*=-1;
    	seg[id].mn*=-1;
    	swap(seg[id].mx,seg[id].mn);
    }
    li void pushdown(int id){
        if(!seg[id].rev){return;}
        maketag(tl(id));
        maketag(tr(id));
        seg[id].rev=0;
    }
    li node query(int id,int l,int r){
       if(seg[id].l>=l && seg[id].r<=r){
       		return seg[id];
       }else{
       		int mid=(seg[id].l+seg[id].r)>>1;
       		pushdown(id);
       		if(mid>=r){
       			return query(tl(id),l,r);
       		}else if(mid<l){
       			return query(tr(id),l,r);
       		}else{
       			node res;
       			node left=query(tl(id),l,r);
       			node right=query(tr(id),l,r);
       			pushup(res,left,right);
       			return res;
       		}
       }
    }
    li void modify(int id,int L,int R,int l,int r){
        if(inrange(L,R,l,r)){
            maketag(id);
        }else if(!outofrange(L,R,l,r)){
            int mid=(L+R)>>1;
            pushdown(id);
            modify(tl(id),L,mid,l,r);
            modify(tr(id),mid+1,R,l,r);
            pushup(id);
        }
    }  
    li void update(int id,int l,int r,int pos,int v){
    	if(l==r){
    		seg[id]={l,r,v,v,v,0};
    		return;
    	}
    	int mid=(l+r)>>1;
    	pushdown(id);
    	if(mid>=pos){
    		update(tl(id),l,mid,pos,v);
    	}else{
    		update(tr(id),mid+1,r,pos,v);
    	}
    	pushup(id);
    }
}t;
#define node SEG::node
node merge(node l,node r){
	node id={0,0,0,-INF,INF,0};
	id.val=l.val+r.val;
	id.mx=max(l.mx,r.mx);
	id.mn=min(l.mn,r.mn);
	return id;	
}
//3.找LCA，同时完成操作
void update(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]){//
            swap(u,v);
        }
        t.modify(1,1,n,dfn[top[u]],dfn[u]);//深度越小，dfs序号越小
        u=fa[top[u]];//处理完上移动
    }
    if(dfn[u]>dfn[v]){
        swap(u,v);
    }
    if(dfn[u]+1<=dfn[v]){
        t.modify(1,1,n,dfn[u]+1,dfn[v]);
    }
}
node ask(int u,int v){
	node res={0,0,0,-INF,INF,0};
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]){
            swap(u,v);
        }
    	res=merge(res,t.query(1,dfn[top[u]],dfn[u]));
        u=fa[top[u]];
    }
    if(dfn[u]>dfn[v]){
        swap(u,v);
    }
    if(dfn[u]+1<=dfn[v]){
        res=merge(res,t.query(1,dfn[u]+1,dfn[v]));//去除公共祖先
    }
    return res;
}
int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v,w;
		cin>>u>>v>>w;
		u++,v++;
		ee[i]={u,v,w};
		add(u,v,w);
	}
	dfs1(1,0);
	dfs2(1,1);
	t.build(1,1,n);
	int m;
	cin>>m;
	for(int i=1;i<=m;i++){
		string op;
		cin>>op;
		if(op=="C"){//
			int x,w;
			cin>>x>>w;
			int u=ee[x].u;
			int v=ee[x].v;
			if(dep[u]<dep[v]){
				swap(u,v);
			}
			t.update(1,1,n,dfn[u],w);
		}else if(op=="N"){
			int u,v;
			cin>>u>>v;
			u++,v++;
			update(u,v);
		}else if(op=="SUM"){
			int u,v;
			cin>>u>>v;
			u++,v++;
			cout<<ask(u,v).val<<'\n';
		}else if(op=="MAX"){
			int u,v;
			cin>>u>>v;
			u++,v++;
			cout<<ask(u,v).mx<<'\n';
		}else if(op=="MIN"){
			int u,v;
			cin>>u>>v;
			u++,v++;
			cout<<ask(u,v).mn<<'\n';
		}
	}
}