洛谷P4315 月下“毛景树”

https://www.luogu.org/problemnew/show/P4315

题目描述
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。
$爬啊爬爬啊爬$ 毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有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之间树枝上毛毛果个数最多有多少个。

题意：给定一颗树，有4种操作：
1.查询两点间最大边权
2.两点间边权加v
3.两点间边赋值v
4.第i条边权值变成v
思路：第四种操作等价于第3种。难点在于线段树操作，想明白怎么同时维护setv和addv两个标记这道题就是水题了。
这道题就是同时维护两个标记的https://blog.csdn.net/Wen_Yongqi/article/details/90209453

#include<bits/stdc++.h>
using namespace std;
#define maxn (100000+100)

vector<int> G[maxn];
int dfs_clock;
int n,from[maxn],to[maxn],w[maxn],id[maxn],top[maxn],deep[maxn],sz[maxn],fa[maxn],son[maxn];
char cmd[20];
int op,ql,qr,val;
struct Edge{
	int u,v,w;
};
vector<Edge> edges;

int addv[maxn*4],setv[maxn*4],sumv[maxn*4],minv[maxn*4],maxv[maxn*4];
int _sum,_min,_max;

void maintain(int o,int l,int r)
{
	if(setv[o]!=-1)
	{
		sumv[o]=setv[o]*(r-l+1);
		minv[o]=maxv[o]=setv[o];
	}
	else
	{
		sumv[o]=sumv[o*2]+sumv[o*2+1];
		minv[o]=min(minv[o*2],minv[o*2+1]);
		maxv[o]=max(maxv[o*2],maxv[o*2+1]);
	}
	sumv[o]+=addv[o]*(r-l+1);
	minv[o]+=addv[o];
	maxv[o]+=addv[o];
}

void build(int o,int l,int r)
{
	if(l==r)setv[o]=w[l];
	else 
	{
		setv[o]=-1;
		int mid=(l+r)/2;
		build(o*2,l,mid);
		build(o*2+1,mid+1,r);
	}
	maintain(o,l,r);
}

void pushdown(int o)
{
	if(setv[o]!=-1)
	{
		setv[o*2]=setv[o*2+1]=setv[o];
		addv[o*2]=addv[o*2+1]=0;
		setv[o]=-1;
	}
	if(addv[o]!=0)
	{
		addv[o*2]+=addv[o];
		addv[o*2+1]+=addv[o];
		addv[o]=0;
	}
}

void update(int o,int l,int r)
{
	if(ql<=l&&qr>=r)
	{
		if(op==2){setv[o]=val;addv[o]=0;}
		else addv[o]+=val;
	}
	else
	{
		int mid=(l+r)/2;
		pushdown(o);
		if(ql<=mid)update(o*2,l,mid);else maintain(o*2,l,mid);
		if(qr>mid)update(o*2+1,mid+1,r);else maintain(o*2+1,mid+1,r);
	}
	maintain(o,l,r);
}

void query(int o,int l,int r)
{
	if(ql<=l&&qr>=r)
	{
		_sum+=sumv[o];	
		_min=min(_min,minv[o]);
		_max=max(_max,maxv[o]);		
	}
	else
	{
		int mid=(l+r)/2;
		pushdown(o);
		maintain(o*2,l,mid);maintain(o*2+1,mid+1,r);
		maintain(o,l,r);
		if(ql<=mid)query(o*2,l,mid);
		if(qr>mid)query(o*2+1,mid+1,r);
	}		
}

void dfs1(int u,int f)
{
	deep[u]=deep[f]+1;
	fa[u]=f;
	sz[u]=1;
	int maxx=0;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(v==f)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>maxx){maxx=sz[v];son[u]=v;}
	}
}

void dfs2(int u,int up)
{
	top[u]=up;
	id[u]=++dfs_clock;
	if(son[u])dfs2(son[u],up);
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}

void Update(int u,int v)
{
	int tp1=top[u],tp2=top[v];
	while(tp1!=tp2)
	{
		if(deep[tp1]<deep[tp2]){swap(tp1,tp2);swap(u,v);}
		ql=id[tp1],qr=id[u];
		update(1,1,n);
		u=fa[tp1];
		tp1=top[u];
	}
	if(u==v)return;
	if(deep[u]>deep[v])swap(u,v);
	ql=id[u]+1,qr=id[v];
	update(1,1,n);
}

int Query(int u,int v)
{	
	_max=0;
	int tp1=top[u],tp2=top[v];
	while(tp1!=tp2)
	{
		if(deep[tp1]<deep[tp2]){swap(tp1,tp2);swap(u,v);}
		ql=id[tp1],qr=id[u];	
		query(1,1,n);		
		u=fa[tp1];
		tp1=top[u];
	}
	if(u==v)return _max;
	if(deep[u]>deep[v])swap(u,v);
	ql=id[u]+1,qr=id[v];
	query(1,1,n);
	return _max;
}

int main()
{
	//freopen("input.in","r",stdin);
	int x,y,z;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back(y);
		G[y].push_back(x);
		edges.push_back((Edge){x,y,z});
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=0;i<edges.size();i++)
	{
		Edge &e=edges[i];
		if(deep[e.u]>deep[e.v])w[id[e.u]]=e.w;
		else w[id[e.v]]=e.w;	
	}	
	build(1,1,n);
	while(scanf("%s",cmd)&&cmd[0]!='S')
	{				//op:2-setv op:1-addv
		if(cmd[0]=='M')
		{
			scanf("%d%d",&x,&y);
			printf("%d\n",Query(x,y));
		}
		else if(cmd[0]=='A')
		{
			scanf("%d%d%d",&x,&y,&z);
			op=1;val=z;
			Update(x,y);
		}
		else if(cmd[1]=='o')
		{
			scanf("%d%d%d",&x,&y,&z);
			op=2;val=z;
			Update(x,y);
		}
		else
		{
			scanf("%d%d",&x,&z);
			op=2;val=z;
			y=edges[x-1].v;
			x=edges[x-1].u;
			Update(x,y);
		}
	}
	return 0;
}