题目描述
毛毛虫经过及时的变形,最终逃过的一劫,离开了菜妈的菜园。 毛毛虫经过千山万水,历尽千辛万苦,最后来到了小小的绍兴一中的校园里。

爬啊爬爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面,发现树上长着他最爱吃的毛毛果 “毛景树”上有N个节点和N-1条树枝,但节点上是没有毛毛果的,毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力,他能改变树枝上毛毛果的个数:

Change k w:将第k条树枝上毛毛果的个数改变为w个。

Cover u v w:将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。

Add u v w:将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪,于是他会有如下询问:

Max u v:询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

输入格式
第一行一个正整数N。

接下来N-1行,每行三个正整数Ui,Vi和Wi,第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi,树枝上有Wi个毛毛果。 接下来是操作和询问,以“Stop”结束。

输出格式
对于毛毛虫的每个询问操作,输出一个答案。

输入输出样例
输入 #1复制

4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop
输出 #1复制
9
16
说明/提示
1<=N<=100,000,操作+询问数目不超过100,000。

保证在任意时刻,所有树枝上毛毛果的个数都不会超过10^9个。


就是把边权给到边下面那个点之后就是树剖的板子题了。

线段树的两个lazy互相维护一下即可。


AC代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,u[N],v[N],w[N],vis[N];
int head[N],nex[N<<1],to[N<<1],tot;
int pos[N],bl[N],f[N],h[N],sz[N],son[N],cnt;
struct node{
	int l,r,lazy,add,mx;
}t[N<<2];
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
inline void push_up(int p){
	t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
}
inline void push_down(int p){
	if(t[p].lazy){
		t[p<<1].mx=t[p].lazy; t[p<<1|1].mx=t[p].lazy;
		t[p<<1].add=t[p<<1|1].add=0;
		t[p<<1].lazy=t[p].lazy; t[p<<1|1].lazy=t[p].lazy;
		t[p].lazy=0;
	}
	if(t[p].add){
		t[p<<1].add+=t[p].add; t[p<<1|1].add+=t[p].add;
		t[p<<1].mx+=t[p].add; t[p<<1|1].mx+=t[p].add;
		t[p].add=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r;
	if(l==r)	return ; int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r,int v){
	if(t[p].l==l&&t[p].r==r){
		t[p].mx=t[p].lazy=v; t[p].add=0; return ;
	}
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	change(p<<1,l,r,v);
	else if(l>mid)	change(p<<1|1,l,r,v);
	else	change(p<<1,l,mid,v),change(p<<1|1,mid+1,r,v);
	push_up(p);
}
void addsum(int p,int l,int r,int v){
	if(t[p].l==l&&t[p].r==r){
		t[p].mx+=v; t[p].add+=v; return ;
	}
	push_down(p); int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	addsum(p<<1,l,r,v);
	else if(l>mid)	addsum(p<<1|1,l,r,v);
	else	addsum(p<<1,l,mid,v),addsum(p<<1|1,mid+1,r,v);
	push_up(p);
}
int ask(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].mx;
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return max(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r));
}
void dfs1(int x){
	sz[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(f[x]==to[i])	continue;
		f[to[i]]=x; h[to[i]]=h[x]+1;
		dfs1(to[i]);	sz[x]+=sz[to[i]];
		if(sz[to[i]]>sz[son[x]])	son[x]=to[i];
	}
}
void dfs2(int x,int belong){
	pos[x]=++cnt; bl[x]=belong;
	if(son[x])	dfs2(son[x],belong);
	for(int i=head[x];i;i=nex[i])
		if(h[to[i]]>h[x]&&to[i]!=son[x])	dfs2(to[i],to[i]);
}
void cover(int x,int y,int z){
	while(bl[x]!=bl[y]){
		if(h[bl[x]]<h[bl[y]])	swap(x,y);
		change(1,pos[bl[x]],pos[x],z);	x=f[bl[x]];
	}
	if(pos[x]==pos[y])	return ;
	if(pos[x]>pos[y])	swap(x,y);
	change(1,pos[x]+1,pos[y],z);
}
void updata(int x,int y,int z){
	while(bl[x]!=bl[y]){
		if(h[bl[x]]<h[bl[y]])	swap(x,y);
		addsum(1,pos[bl[x]],pos[x],z);	x=f[bl[x]];
	}
	if(pos[x]==pos[y])	return ;
	if(pos[x]>pos[y])	swap(x,y);
	addsum(1,pos[x]+1,pos[y],z);
}
int querymax(int x,int y){
	int res=0;
	while(bl[x]!=bl[y]){
		if(h[bl[x]]<h[bl[y]])	swap(x,y);
		res=max(res,ask(1,pos[bl[x]],pos[x])); x=f[bl[x]];
	}
	if(pos[x]==pos[y])	return res;
	if(pos[x]>pos[y])	swap(x,y);
	res=max(res,ask(1,pos[x]+1,pos[y]));
	return res;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d %d %d",&u[i],&v[i],&w[i]);	
		add(u[i],v[i]);	add(v[i],u[i]);
	}
	dfs1(1);	dfs2(1,1);	build(1,1,n);
	for(int i=1;i<n;i++){
		if(f[u[i]]==v[i])	vis[i]=u[i];
		else	vis[i]=v[i];
	}
	for(int i=1;i<n;i++)	change(1,pos[vis[i]],pos[vis[i]],w[i]);
	char op[10];
	while(scanf("%s",op),op[0]!='S'){
		int a,b,c;	scanf("%d %d",&a,&b);
		if(op[0]=='M')	printf("%d\n",querymax(a,b));
		else if(op[1]=='o')	scanf("%d",&c),cover(a,b,c);
		else if(op[0]=='A')	scanf("%d",&c),updata(a,b,c);
		else	change(1,pos[vis[a]],pos[vis[a]],b);
	}
	return 0;
}