Steven_Meng's Blog

传送门

树链剖分模板题，用支持区间加，区间覆盖，查询区间最大的线段树实现。

注意覆盖标记$cotag$优先级比加标记$tag$要高，所以覆盖时直接设$tag=0$

需要把$Change$操作转化为顶点$U[k]$和$V[k]$的覆盖操作

其他没什么好说的，注意细节即可

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 2000005
#define HA 19260817
#define INF 0x3f3f3f3f
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
struct Edge{
	int to,len;
};
vector<Edge>G[MAXN];
inline void AddEdge(int u,int v,int w){
	G[u].push_back(Edge{v,w});
}
int sz[MAXN],big[MAXN],fa[MAXN],top[MAXN],dep[MAXN],tofa[MAXN];
void dfs1(int u,int father){
    fa[u]=father;sz[u]=1;
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if (v!=father){
            dep[v]=dep[u]+1;
            tofa[v]=G[u][i].len;
            dfs1(v,u);
            sz[u]+=sz[v];
            if (sz[big[u]]<sz[v]) big[u]=v;
        }
    }
}
int ql[MAXN],alb[MAXN],cnt;
void dfs2(int u,int t){
	alb[ql[u]=++cnt]=u;
    top[u]=t;
    if (big[u]) dfs2(big[u],t);
    for (register int i=0;i<(int)G[u].size();++i){
        int v=G[u][i].to;
        if (v!=fa[u]&&v!=big[u]){
            dfs2(v,v);
        }
    }
}
namespace SegmentTree{
    struct node{
    	int l,r;
    	int maxn,tag,cotag;
	}tree[MAXN<<2];
	#define lc i<<1
	#define rc i<<1|1
	inline void pushup(int i){
		tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn);
	}
	inline void Add(int i,int val){
		tree[i].maxn+=val;
		tree[i].tag+=val;
	}
	inline void Cover(int i,int val){
		tree[i].maxn=val;
		tree[i].cotag=val;
		tree[i].tag=0;
	}
	inline void pushdown(int i){
		if (tree[i].cotag!=HA){
			Cover(lc,tree[i].cotag);
			Cover(rc,tree[i].cotag);
			tree[i].cotag=HA;
		}
		if (tree[i].tag){
			Add(lc,tree[i].tag);
			Add(rc,tree[i].tag);
			tree[i].tag=0;
		}
	}
	void Build(int i,int l,int r){
		tree[i].l=l,tree[i].r=r;
		tree[i].cotag=HA,tree[i].tag=0;
		if (l==r){
			tree[i].maxn=tofa[alb[l]];
			return ;
		}
		int mid=(l+r)>>1;
		Build(lc,l,mid);
		Build(rc,mid+1,r);
		pushup(i);
	}
	int Query(int i,int L,int R){
		if (L<=tree[i].l&&tree[i].r<=R){
			return tree[i].maxn;
		}
		int mid=(tree[i].l+tree[i].r)>>1,ans=-INF;
		pushdown(i);
		if (L<=mid) ans=max(ans,Query(lc,L,R));
		if (mid<R) ans=max(ans,Query(rc,L,R));
		return ans;
	}
	void CoverInterval(int i,int L,int R,int val){
		if (L<=tree[i].l&&tree[i].r<=R){
			Cover(i,val);
			return ;
		}
		int mid=(tree[i].l+tree[i].r)>>1;
		pushdown(i);
		if (L<=mid) CoverInterval(lc,L,R,val);
		if (mid<R) CoverInterval(rc,L,R,val);
		pushup(i);
	}
	void AddInterval(int i,int L,int R,int val){
		if (L<=tree[i].l&&tree[i].r<=R){
			Add(i,val);
			return ;
		}
		int mid=(tree[i].l+tree[i].r)>>1;
		pushdown(i);
		if (L<=mid) AddInterval(lc,L,R,val);
		if (mid<R) AddInterval(rc,L,R,val);
		pushup(i);
	}
}
using namespace SegmentTree;
inline void Add_Chain(int u,int v,int w){
    while (top[u]!=top[v]){
        if (dep[top[u]]<dep[top[v]]){
            swap(u,v);
        }
        AddInterval(1,ql[top[u]],ql[u],w);
        u=fa[top[u]];
    }
    if (dep[u]>dep[v]) swap(u,v);
    AddInterval(1,ql[u]+1,ql[v],w);
}
inline void Cover_Chain(int u,int v,int w){
	while (top[u]!=top[v]){
		if (dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		CoverInterval(1,ql[top[u]],ql[u],w);
		u=fa[top[u]];
	}
	if (dep[u]>dep[v]) swap(u,v);
	CoverInterval(1,ql[u]+1,ql[v],w);
}
inline int Query_Chain(int u,int v){
	int ans=-INF;
	while (top[u]!=top[v]){
		if (dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		ans=max(ans,Query(1,ql[top[u]],ql[u]));
		u=fa[top[u]];
	}
	if (dep[u]>dep[v]) swap(u,v);
	return max(ans,Query(1,ql[u]+1,ql[v]));
}
int U[MAXN],V[MAXN];
inline void Init(){
    dfs1(1,0);
    dfs2(1,1);
}
int main(){
    int n=read();
    for (register int i=1;i<n;++i){
        int u=read(),v=read(),w=read();
        AddEdge(u,v,w);
        AddEdge(v,u,w);
        U[i]=u,V[i]=v;
    }
    Init();
    Build(1,1,n);
    while (true){
        char ch[10];
        scanf("%s",ch);
        if (ch[0]=='C'&&ch[1]=='h'){
        	int k=read(),w=read();
        	Cover_Chain(U[k],V[k],w);
		}
		else if (ch[0]=='C'&&ch[1]=='o'){
			int u=read(),v=read(),w=read();
			Cover_Chain(u,v,w);
		}
		else if (ch[0]=='A'){
			int u=read(),v=read(),w=read();
			Add_Chain(u,v,w);
		}
		else if (ch[0]=='M'){
			int u=read(),v=read();
			printf("%d\n",Query_Chain(u,v));
		}
		else {
			break;
		}
    }
}