本文共 4652 字，大约阅读时间需要 15 分钟。

$对应$

#include 
   
    using namespace std;#define GO std::ios::sync_with_stdio(false)const int maxn=4e5+10;int n,m,root,w[maxn],mod;struct edge{
   	int to,nxt;}d[maxn]; int head[maxn],k=1;void add(int u,int v){
   	d[k].to=v,d[k].nxt=head[u],head[u]=k++;}int deep[maxn],siz[maxn],fa[maxn], son[maxn];void dfs1(int u,int f,int depth){
   	deep[u]=depth, fa[u]=f, siz[u]=1;	int maxson=-1;	for(int i=head[u];i;i=d[i].nxt)	{
   		int v=d[i].to;		if( v==f )	continue;		dfs1(v,u,depth+1);		siz[u]+=siz[v];		if(siz[v]>maxson)	maxson=siz[v],son[u]=v;	}}int id[maxn],wn[maxn],top[maxn],cnt;void dfs2(int u,int ffa){
   	id[u]=++cnt, wn[cnt]=w[u], top[u]=ffa;	if( son[u]==0 )	return;	dfs2( son[u],ffa );	for(int i=head[u];i;i=d[i].nxt)	{
   		int v=d[i].to;		if( v==fa[u] || v==son[u] )	continue;		dfs2(v,v);	}}struct tree{
   	int v,l,r,lazy;}a[maxn];void push_down(int p){
   	if( !a[p].lazy )	return;	int len1=a[p<<1].r-a[p<<1].l+1, len2=a[p<<1|1].r-a[p<<1|1].l+1;	a[p<<1].lazy = (a[p<<1].lazy + a[p].lazy)%mod;	a[p<<1|1].lazy = (a[p<<1|1].lazy + a[p].lazy)%mod;	a[p<<1].v=(a[p<<1].v+a[p].lazy*len1%mod)%mod;	a[p<<1|1].v = (a[p<<1|1].v+a[p].lazy*len2%mod)%mod;	a[p].lazy=0;}void build(int p,int l,int r){
   	a[p].l=l,a[p].r=r,a[p].lazy=0;	if( l==r )	{
   		a[p].v=wn[l]%mod;		return;	}	int mid = l+r>>1;	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);	a[p].v = (a[p<<1].v+a[p<<1|1].v)%mod;}void tree_add(int p,int l,int r,int k){
   	if( l<=a[p].l&&a[p].r<=r)	{
   		a[p].v=( (a[p].r-a[p].l+1) *k+a[p].v)%mod;		a[p].lazy=(a[p].lazy+k)%mod;		return;	}	push_down(p);	int mid=a[p].l+a[p].r>>1;	if(l<=mid)	tree_add(p<<1,l,r,k);	if(r>mid)	tree_add(p<<1|1,l,r,k);	a[p].v = (a[p<<1].v+a[p<<1|1].v)%mod;}int tree_ask(int p,int l,int r){
   	if( l<=a[p].l&&a[p].r<=r)	return a[p].v;	push_down(p);	int mid=a[p].l+a[p].r>>1,ans=0;	if(l<=mid)	ans=(ans + tree_ask(p<<1,l,r) )%mod;	if(r>mid)	ans=(ans + tree_ask(p<<1|1,l,r) )%mod;	return ans;}void tree_addpath(int x,int y,int k)//x到y的路上加上k{
   	while(top[x] != top[y])	{
   		if( deep[ top[x] ]
    
     deep[y] )	swap(x,y);	tree_add(1,id[x],id[y],k);}int tree_asksum(int x,int y){
    	int ans=0; 	while( top[x]!=top[y] ) 	{
    		if( deep[ top[x] ]
     
      deep[y] )	swap(x,y);	ans= (ans+tree_ask(1,id[x],id[y]) )%mod;	return ans;}void tree_addroot(int root,int k){
   	tree_add(1,id[root],id[root]+siz[root]-1,k);}int tree_askrootsum(int root){
   	int ans=tree_ask(1,id[root],id[root]+siz[root]-1)%mod;	return ans;}int main(){
   	GO;	cin.tie(0); cout.tie(0);	cin >> n >> m >> root >> mod;	for(int i=1;i<=n;i++)	cin >> w[i];	for(int i=1, l, r;i
      
       > l >> r;		add(l,r); add(r,l);	}	dfs1(root,0,1);	dfs2(root,root);	build(1,1,n);	for(int i=1, a1, a2, a3, a4;i<=m;i++)	{
   		cin >> a1;		if( a1==1 )		{
   			cin >> a2 >> a3 >> a4;			tree_addpath(a2,a3,a4%mod);		}		else if( a1==2 )		{
   			cin >> a2 >> a3;			cout << tree_asksum(a2,a3) << "\n";		}		else if( a1==3 )		{
   			cin >> a2 >> a3;			tree_addroot(a2,a3);		}		else		{
   			cin >> a2;			cout << tree_askrootsum(a2) << "\n";		}	}	return 0;}
      
     
    
   

区间覆盖,区间加法

#include 
   
    using namespace std;#define ls (rt<<1)#define rs (rt<<1|1)#define mid (l+r>>1)#define lson ls,l,mid#define rson rs,mid+1,rconst int maxn=2e5+10;int uu[maxn],vv[maxn],son[maxn],n;struct edge{	int to,nxt,w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int w){d[++cnt] = (edge){v,head[u],w},head[u]=cnt;}int siz[maxn],fa[maxn],deep[maxn],wt[maxn];void dfs1(int u,int father){	siz[u]=1,fa[u]=father,deep[u]=deep[father]+1;	for(int i=head[u];i;i=d[i].nxt )	{		int v=d[i].to;		if( v==father )	continue;		wt[v]=d[i].w;	dfs1(v,u);		siz[u]+=siz[v];		if( siz[son[u]]
    
     =L&&r<=R )	{		if( type==1 )	laz1[rt] = a[rt] = val, laz2[rt]=0;//直接改变		else	laz2[rt]+=val,a[rt]+=val; 		return;	}	if( r
     
      R )	return;	push_down(rt,l,r);	update(lson,L,R,val,type); update(rson,L,R,val,type);	a[rt] = max( a[ls],a[rs] );}int ask(int rt,int l,int r,int L,int R){	if( l>=L&&r<=R )	return a[rt];	if( l>R||r
      
       deep[y] )	swap(x,y);	update(1,1,n,id[x]+1,id[y],val,type);}int askmax(int x,int y){	int ans=0;	while( top[x]!=top[y] )	{		if( deep[top[x]]
       
        deep[y] )	swap(x,y);	ans = max( ans,ask(1,1,n,id[x]+1,id[y] ));	return ans;}int main(){	scanf("%d",&n);	for(int i=1;i
        
         deep[uu[i]] ) swap(uu[i],vv[i] ); string type; while( cin >> type && type!="Stop" ) { int u,v,w; scanf("%d%d",&u,&v); if( type == "Change" ) { modify(uu[u],vv[u],v,1); // update( 1,1,n,id[uu[u]],id[uu[u]],v,1 ); } else if( type=="Cover" ) { scanf("%d",&w); modify(u,v,w,1); } else if( type=="Add" ) { scanf("%d",&w); modify(u,v,w,2); } else printf("%d\n",askmax(u,v)); }}
        
       
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/107297190 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！