首页 > 其他分享 >树链剖分总结

树链剖分总结

时间：2024-05-21 12:29:33浏览次数：21  
标签：总结 lid 剖分 int top 树链 ans rid id

本博客为本人对树剖可解决题目的总结。。。

概念

  • 1：\(fa[u]\) : \(u\) 的父亲
  • 2：\(size[u]\) : \(u\) 节点 \(u\) 为子树的节点个数
  • 3：\(dep[u]\) : \(u\) 节点的深度
  • 4：\(wson[u]\) : \(u\) 节点的重儿子编号
  • 5：\(top[u]\) : \(u\) 节点所在重链的顶部端点
  • 6：\(dfn[u]\) : \(u\) 节点的 \(dfs\) 序
  • 7：\(pre[u]\) : \(dfs\) 序 为 \(u\) 的对应的节点的编号

板子

两次 $dfs$ 
void dfs1(int u,int f)
{
    size[u]=1;
    for (int i=head[u];i;i=e[i].next)
	{
        int y=e[i].to;
		if(y==f)continue;
        dep[y]=dep[u]+1;
		fa[y]=u;
        dfs1(y,u);
        size[u]+=size[y];
        if(size[y]>size[wson[u]])wson[u]=y;
    }
}
void dfs2(int u,int topfa)
{
    dfn[u]=++cnt;
	pre[cnt]=u;
	top[u]=topfa;
    if(wson[u]) dfs2(wson[u],topfa);
    for (int i=head[u];i;i=e[i].next)
	{
        int y=e[i].to;
        if(y==fa[u]||y==wson[u]) continue;
        dfs2(y,y);
    }
}
$lca$ 
int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
链上修改，其他操作类比 
void qup(int x,int y,int z)
{ 
    while(top[x]!=top[y])
	{
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    update(1,dfn[y],dfn[x],z);
	//update(1,dfn[y]+1,dfn[x],z);如果题目给的是边权则改为这个
}

线段树维护的各种操作

常见的操作不过多叙述了

1 换根

题目

正常换就行 
#include<bits/stdc++.h>
#define int long long
#define lid id<<1
#define rid id<<1|1
const int maxn=1e6+10;
const int inf=2e9;
using namespace std;
int n,t,a[maxn<<2];
struct node{int to,next;}e[maxn<<2];
struct tree{int l,r,lazy,minn;}m[maxn<<4]; 
int tot,head[maxn<<1];
int size[maxn],wson[maxn],fa[maxn],dep[maxn],top[maxn];
int dfn[maxn],pre[maxn],cnt=0;
inline void add(int x,int y)
{
    e[++tot].to=y;e[tot].next=head[x];head[x]=tot;
}
void addm(int x,int y)
{
	add(x,y);add(y,x);
}
void dfs1(int u,int f)
{
    size[u]=1;
    for (int i=head[u];i;i=e[i].next)
	{
        int y=e[i].to;
		if(y==f)continue;
        dep[y]=dep[u]+1;
		fa[y]=u;
        dfs1(y,u);
        size[u]+=size[y];
        if(size[y]>size[wson[u]])wson[u]=y;
    }
}
void dfs2(int u,int topfa)
{
    dfn[u]=++cnt;
	pre[cnt]=u;
	top[u]=topfa;
    if(wson[u]) dfs2(wson[u],topfa);
    for (int i=head[u];i;i=e[i].next)
	{
        int y=e[i].to;
        if(y==fa[u]||y==wson[u]) continue;
        dfs2(y,y);
    }
}
inline void up(int id)
{
    m[id].minn=min(m[lid].minn,m[rid].minn);
}
inline void down(int id)
{
	if(m[id].lazy==-1||m[id].l==m[id].r)return ;
	m[lid].minn=m[lid].lazy=m[id].lazy; 
	m[rid].minn=m[rid].lazy=m[id].lazy;
	m[id].lazy=-1; 
} 
void build(int id,int l,int r)
{
	m[id].l=l;
	m[id].r=r;
	m[id].lazy=-1;
    int mid=(l+r)>>1;
    if(l==r)
	{
		m[id].minn=a[pre[l]];
		return;
	}
    build(lid,l,mid);
	build(rid,mid+1,r);
    up(id);
}
void update(int id,int s,int tt,int y)
{
	int l=m[id].l,r=m[id].r;
    if(l>=s&&r<=tt)
	{
		m[id].lazy=m[id].minn=y;
		return;
	}    
	down(id);
	int mid=(l+r)>>1;
    if(s<=mid)update(lid,s,tt,y);
    if(tt>mid) update(rid,s,tt,y);
    up(id);
}
void qup(int x,int y,int z)
{ 
    while(top[x]!=top[y])
	{
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    update(1,dfn[y],dfn[x],z);
}
int query(int id,int s,int tt)
{
	int l=m[id].l,r=m[id].r;
	int ans=inf;
	if(l>=s&&r<=tt)
	{
		return m[id].minn;
	}
	down(id);
	int mid=(l+r)>>1;
	if(s<=mid)ans=min(ans,query(lid,s,tt));
	if(tt>mid)ans=min(ans,query(rid,s,tt));
	return ans; 
}
int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
signed main(){
//	freopen("aa.in","r",stdin);
    scanf("%lld%lld",&n,&t);
    for(int i=1;i<n;i++)
	{
        int x,y;
        scanf("%lld%lld",&x,&y);
        addm(x,y);
    }
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	int root=1;
	scanf("%lld",&root);
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
    while (t--)
	{
        int x,y,z,k;
        scanf("%lld%lld",&z,&x);
        if(z==1)root=x;
        if(z==2)scanf("%lld%lld",&y,&k),qup(x,y,k);
        if(z==3)
        {
        	if(x==root) 
			{
				printf("%lld\n",query(1,1,n));
			}
        	else
        	{
        		int w=lca(x,root);
        		if(w==x)
        		{
        			int k;
        			for(int i=head[x];i;i=e[i].next)
        			{
        				int ll=e[i].to;
        				if(dfn[ll]<=dfn[root]&&dfn[ll]+size[ll]-1>=dfn[root])
        				{
        					k=ll;break;
						}
					}
					int ans=min(query(1,1,dfn[k]-1),query(1,dfn[k]+size[k],n));
					printf("%lld\n",ans);
				}
				else printf("%lld\n",query(1,dfn[x],dfn[x]+size[x]-1)); 
			}
		}
    }
    return 0;
}

2 求节点到根的 1 的个数——区间覆盖

题目

把 += 改为 = 即可 
#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1 
const int maxn=1e6+10;
const int inf=0x7f7f7f7f;
using namespace std;
int n,t,a[maxn<<2];
struct tree{int l,r,lazy,sum;}m[maxn<<4]; 
int tot,head[maxn<<1],to[maxn<<2],nxt[maxn<<2];
int size[maxn],wson[maxn],fa[maxn],dep[maxn],top[maxn];
int dfn[maxn],pre[maxn],cnt=0;
int mod,root;
void add(int x,int y)
{
	to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}
void addm(int x,int y)
{
	add(x,y),add(y,x);
}
void dfs1(int u,int f)
{
	size[u]=1;
	for(int i=head[u];i;i=nxt[i])
	{
		int y=to[i];
		if(y==f)continue;
		dep[y]=dep[u]+1;
		fa[y]=u;
		dfs1(y,u);
		size[u]+=size[y];
		if(size[y]>size[wson[u]])wson[u]=y;
	}
}
void dfs2(int u,int topfa)
{
	dfn[u]=++cnt;
	pre[cnt]=u;
	top[u]=topfa;
	if(wson[u])dfs2(wson[u],topfa);
	for(int i=head[u];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa[u]||y==wson[u])continue;
		dfs2(y,y);	
	}
}
inline void up(int id)
{
	m[id].sum=m[lid].sum+m[rid].sum;
}
inline void down(int id,int l,int r,int mid)
{
	if(m[id].lazy<0)return ;	
	m[lid].lazy=m[rid].lazy=m[id].lazy;
	if(m[id].lazy==0) m[lid].sum=m[rid].sum=0;
	else m[lid].sum=mid-l+1,m[rid].sum=r-mid;
	m[id].lazy=-1;
}
void build(int id,int l,int r)
{
	m[id].l=l;
	m[id].r=r;
	if(l==r){m[id].lazy=-1;return;};	
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
} 
int querysum(int id,int s,int tt,int y)
{
	int l=m[id].l,r=m[id].r,ans=0;
//	cout<<id<<" "<<l<<" "<<r<<" "<<m[id].sum<<endl; 
	if(s<=l&&r<=tt)
	{
		ans=m[id].sum;
		m[id].lazy=y;
		m[id].sum=(r-l+1)*y;
		return ans;
	}
	int mid=(l+r)>>1;
	down(id,l,r,mid);
	if(s<=mid)ans+=querysum(lid,s,tt,y);
	if(tt>mid)ans+=querysum(rid,s,tt,y);
	up(id);
//	cout<<"up: "<<id<<" "<<l<<" "<<r<<" "<<m[id].sum<<endl;
	return ans;
} 
int qsum(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans+=querysum(1,dfn[top[x]],dfn[x],1);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	ans+=querysum(1,dfn[y],dfn[x],1);
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		x++;
		addm(i,x);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	scanf("%d",&t);
	char ss[10];
	int x,y,z;
//	for(int i=1;i<=n;i++)
//		cout<<dfn[i]<<" "; 
	while(t--)
	{
		cin>>ss+1;
		if(ss[1]=='i')
		{
			scanf("%d",&x);
			x++;
			int ans=qsum(1,x);
//			cout<<ans<<endl;
			printf("%d\n",dep[x]+1-ans);
		}
		else
		{
			scanf("%d",&x);
			x++;
			printf("%d\n",querysum(1,dfn[x],dfn[x]+size[x]-1,0));
		}
	}
	return 0;
}

3 动态开点线段树维护树剖

题目

适用于维护多棵线段树，要加一个 $root$ 数组存根 
#include<bits/stdc++.h>
const int maxn=1e5+10;
using namespace std;
int n,t,a[maxn<<2];
struct node{int to,next;}e[maxn<<4];
struct tree{int maxx,sum,l,r;}m[maxn<<8];
int tot,head[maxn],temp;
int size[maxn],wson[maxn],fa[maxn],dep[maxn],top[maxn];
int root[maxn],zj[maxn];
int dfn[maxn],pre[maxn],cnt;
void add(int x,int y)
{
	e[++tot].to=y;
	e[tot].next=head[x];
	head[x]=tot;
}
void addm(int x,int y)
{
	add(x,y),add(y,x);
}
void dfs1(int u,int f)
{
	size[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int y=e[i].to;
		if(y==f)continue;
		dep[y]=dep[u]+1;
		fa[y]=u;
		dfs1(y,u);
		size[u]+=size[y];
		if(size[y]>size[wson[u]])wson[u]=y; 
	}
}
void dfs2(int u,int topfa)
{
	dfn[u]=++cnt;
	pre[cnt]=u;
	top[u]=topfa;
	if(wson[u])dfs2(wson[u],topfa);
	for(int i=head[u];i;i=e[i].next)
	{
		int y=e[i].to;
		if(y==fa[u]||y==wson[u])continue;
		dfs2(y,y);
	}
}
void up(int id)
{
	int lid=m[id].l,rid=m[id].r;
	m[id].maxx=max(m[lid].maxx,m[rid].maxx);
	m[id].sum=m[lid].sum+m[rid].sum;
}
void update(int &id,int l,int r,int pos,int y)
{
	if(!id)id=++temp;
	m[id].maxx=max(m[id].maxx,y);
	m[id].sum+=y; 
	if(l==r)return;
	int mid=(l+r)>>1;
	if(pos<=mid)update(m[id].l,l,mid,pos,y);
	else update(m[id].r,mid+1,r,pos,y);
}
void del(int &id,int l,int r,int pos)
{
	if(l==r)
	{
		m[id].maxx=m[id].sum=0;
		return ;
	}
	int mid=(l+r)>>1;
	if(mid>=pos)del(m[id].l,l,mid,pos);
	else del(m[id].r,mid+1,r,pos);
	up(id);
}
int querymax(int id,int l,int r,int x,int y)
{
	int mid=(l+r)>>1,ans=0;
	if(x<=l&&r<=y)return m[id].maxx;
	if(x<=mid)ans=max(ans,querymax(m[id].l,l,mid,x,y));
	if(y>mid)ans=max(ans,querymax(m[id].r,mid+1,r,x,y));
	return ans;
}
int qmax(int x,int y,int zj)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,querymax(root[zj],1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]]; 
	}
	if(dep[x]<dep[y])swap(x,y);
	ans=max(ans,querymax(root[zj],1,n,dfn[y],dfn[x]));
	return ans;
}
int querysum(int id,int l,int r,int x,int y)
{
	int mid=(l+r)>>1,ans=0;
	if(x<=l&&r<=y)return m[id].sum;
	if(x<=mid)ans+=querysum(m[id].l,l,mid,x,y);
	if(y>mid)ans+=querysum(m[id].r,mid+1,r,x,y);
	return ans;
}
int qsum(int x,int y,int zj)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans+=querysum(root[zj],1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]]; 
	}
	if(dep[x]<dep[y])swap(x,y);
	ans+=querysum(root[zj],1,n,dfn[y],dfn[x]);
	return ans;
}
int main()
{
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&zj[i]);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d%d",&x,&y);
		addm(x,y);
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<=n;i++)
		update(root[zj[i]],1,n,dfn[i],a[i]);
	char ss[10];
	int x,y;
	while(t--)
	{
		scanf("%s",ss);
		scanf("%d%d",&x,&y);
		if(ss[1]=='C')
		{
			del(root[zj[x]],1,n,dfn[x]);
			update(root[y],1,n,dfn[x],a[x]);
			zj[x]=y;
		}
		else if(ss[1]=='W')
		{
			del(root[zj[x]],1,n,dfn[x]);
			update(root[zj[x]],1,n,dfn[x],y);
			a[x]=y;
		}
		else if(ss[1]=='S')
		{
			printf("%d\n",qsum(x,y,zj[x]));
		}
		else printf("%d\n",qmax(x,y,zj[x]));
	}
	
	return 0;
}

4 树上修改值带增加值

题目

加一个 $flag$ 记录修改，要把 $lazy$ 清空 
#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
const int maxn=1e5+10;
const int inf=0x7f7f7f7f;
using namespace std;
int n,t,a[maxn<<2];
struct node{int to,next,val,id;}e[maxn<<2];
struct tree{int maxx,lazy,flag,l,r;}m[maxn<<4];
int tot,head[maxn];
int size[maxn],wson[maxn],fa[maxn],dep[maxn],top[maxn],dian[maxn];
int dfn[maxn],pre[maxn],cnt=0;
void add(int x,int y,int z,int i)
{
	e[++tot].to=y;
	e[tot].val=z;
	e[tot].id=i;
	e[tot].next=head[x];
	head[x]=tot;
}
void addm(int x,int y,int z,int i)
{
	add(x,y,z,i),add(y,x,z,i);
}
void dfs1(int u,int f)
{
	size[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int y=e[i].to;
		if(y==f)continue;
		dep[y]=dep[u]+1;
		dian[e[i].id]=y;
		a[y]=e[i].val;
		fa[y]=u;
		dfs1(y,u);
		size[u]+=size[y];
		if(size[y]>size[wson[u]])wson[u]=y; 
	}
}
void dfs2(int u,int topfa)
{
	dfn[u]=++cnt;
	pre[cnt]=u;
	top[u]=topfa;
	if(wson[u])dfs2(wson[u],topfa);
	for(int i=head[u];i;i=e[i].next)
	{
		int y=e[i].to;
		if(y==fa[u]||y==wson[u])continue;
		dfs2(y,y);
	}
}
void up(int id)
{
	m[id].maxx=max(m[lid].maxx,m[rid].maxx);
}
inline void down(int id)
{
	if(m[id].flag)
	{
		m[lid].lazy=m[rid].lazy=0;
		m[lid].maxx=m[rid].maxx=m[lid].flag=m[rid].flag=m[id].flag;
		m[id].flag=0;
	}
	if(m[id].lazy)
	{
		m[lid].maxx+=m[id].lazy;
		m[rid].maxx+=m[id].lazy;
		m[lid].lazy+=m[id].lazy;
		m[rid].lazy+=m[id].lazy;
		m[id].lazy=0;
	}	
}
void build(int id,int l,int r)
{
	m[id].l=l;
	m[id].r=r;
	int mid=(l+r)>>1;
	if(l==r)
	{
		m[id].maxx=a[pre[l]];
		return ;
	}
	build(lid,l,mid);
	build(rid,mid+1,r);
	up(id);
}
void update(int id,int x,int y)
{
	int l=m[id].l,r=m[id].r;
	if(l==r)
	{
		m[id].maxx=m[id].flag=y;
		m[id].lazy=0;
		return ;
	}
	down(id);
	int mid=(l+r)>>1;
	if(x<=mid)update(lid,x,y);
	else update(rid,x,y);
	up(id);
}
void updatex(int id,int s,int tt,int y)
{
	int l=m[id].l,r=m[id].r;
	if(l>tt||r<s)return;
	if(l>=s&&r<=tt)
	{
		m[id].lazy=0;
		m[id].maxx=m[id].flag=y;
		return ;
	}
	down(id);
	int mid=(l+r)>>1;
	if(s<=mid)updatex(lid,s,tt,y);
	if(tt>mid)updatex(rid,s,tt,y);
	up(id);
}
void updatey(int id,int s,int tt,int y)
{
	int l=m[id].l,r=m[id].r;
	if(l>tt||r<s)return;
	if(l>=s&&r<=tt)
	{
		m[id].lazy+=y;
		m[id].maxx+=y;
		return ;
	}
	down(id);
	int mid=(l+r)>>1;
	if(s<=mid)updatey(lid,s,tt,y);
	if(tt>mid)updatey(rid,s,tt,y);
	up(id);
}
void qup(int x,int y,int z,int f)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		if(f==1)updatey(1,dfn[top[x]],dfn[x],z);
		else updatex(1,dfn[top[x]],dfn[x],z);
		x=fa[top[x]]; 
	}
	if(dep[x]<dep[y])swap(x,y);
	if(f==1)updatey(1,dfn[y]+1,dfn[x],z);
	else updatex(1,dfn[y]+1,dfn[x],z);
}
int querymax(int id,int x,int y)
{
	int l=m[id].l,r=m[id].r;
	int mid=(l+r)>>1,ans=-inf;
	if(x<=l&&r<=y)return m[id].maxx;
	down(id);
	if(x<=mid)ans=max(ans,querymax(lid,x,y));
	if(y>mid)ans=max(ans,querymax(rid,x,y));
	return ans;
}
int qmax(int x,int y)
{
	int ans=-inf;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,querymax(1,dfn[top[x]],dfn[x]));
		x=fa[top[x]]; 
	}
	if(dep[x]<dep[y])swap(x,y);
	ans=max(ans,querymax(1,dfn[y]+1,dfn[x]));
	return ans;
}

int main()
{
//	freopen("asa.in","r",stdin);
//	freopen("123.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		addm(x,y,z,i);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	char ss[10];
	while(1)
	{
		int x,y,z;
		scanf("%s",ss+1);
		if(ss[1]=='S')break;
		scanf("%d%d",&x,&y);
		if(ss[1]=='M')
		{
			printf("%d\n",qmax(x,y));
		}
		else if(ss[2]=='h')
		{
			update(1,dfn[dian[x]],y);
		}
		else if(ss[2]=='o')
		{
			scanf("%d",&z);
			qup(x,y,z,0);
		}
		else 
		{
			scanf("%d",&z);
			qup(x,y,z,1);
		}
	}
	
	return 0;
}

5链上权值改为相反数

题目

相反，交换最大值和最小值 
#include<bits/stdc++.h>
#define int long long
#define lid id<<1
#define rid id<<1|1
const int maxn=2e5+10;
const int inf=0x7f7f7f7f;
using namespace std;
int n,t,a[maxn];
struct node{int to,next,val,id;}e[maxn<<2];
struct tree{int maxx,minn,sum,lazy,l,r;}m[maxn<<2];
int tot,head[maxn];
int size[maxn],wson[maxn],fa[maxn],dep[maxn],top[maxn],dian[maxn];
int dfn[maxn],pre[maxn],cnt=0;
void add(int x,int y,int z,int i)
{
	e[++tot].to=y;
	e[tot].val=z;
	e[tot].id=i;
	e[tot].next=head[x];
	head[x]=tot;
}
void addm(int x,int y,int z,int i)
{
	add(x,y,z,i),add(y,x,z,i);
}
void dfs1(int u,int f)
{
	size[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int y=e[i].to;
		if(y==f)continue;
		dep[y]=dep[u]+1;
		dian[e[i].id]=y;
		a[y]=e[i].val;
		fa[y]=u;
		dfs1(y,u);
		size[u]+=size[y];
		if(size[y]>size[wson[u]])wson[u]=y; 
	}
}
void dfs2(int u,int topfa)
{
	dfn[u]=++cnt;
	pre[cnt]=u;
	top[u]=topfa;
	if(wson[u])dfs2(wson[u],topfa);
	for(int i=head[u];i;i=e[i].next)
	{
		int y=e[i].to;
		if(y==fa[u]||y==wson[u])continue;
		dfs2(y,y);
	}
}
void up(int id)
{
	m[id].maxx=max(m[lid].maxx,m[rid].maxx);
	m[id].minn=min(m[lid].minn,m[rid].minn);
	m[id].sum=m[lid].sum+m[rid].sum; 
}
inline void down(int id)
{
	if(!m[id].lazy)return ;
	m[lid].maxx=-m[lid].maxx;
	m[lid].minn=-m[lid].minn;
	m[lid].sum=-m[lid].sum;
	swap(m[lid].maxx,m[lid].minn);
	m[rid].maxx=-m[rid].maxx;
	m[rid].minn=-m[rid].minn;
	m[rid].sum=-m[rid].sum;
	swap(m[rid].maxx,m[rid].minn);
	m[lid].lazy^=1;
	m[rid].lazy^=1;
	m[id].lazy=0;
}
void build(int id,int l,int r)
{
	m[id].l=l;
	m[id].r=r;
	int mid=(l+r)>>1;
	if(l==r)
	{
		m[id].sum=m[id].minn=m[id].maxx=a[pre[l]];
		return ;
	}
	build(lid,l,mid);
	build(rid,mid+1,r);
	up(id);
}
void update(int id,int x,int y)
{
	int l=m[id].l,r=m[id].r;
	if(l==r)
	{
		m[id].sum=m[id].maxx=m[id].minn=y;
		return ;
	}
	down(id);
	int mid=(l+r)>>1;
	if(x<=mid)update(lid,x,y);
	else update(rid,x,y);
	up(id);
}

void xiangfan(int id,int x,int y)
{
	int l=m[id].l,r=m[id].r;
	if(l>=x&&r<=y)
	{
		m[id].maxx=-m[id].maxx;
		m[id].minn=-m[id].minn;
		m[id].sum=-m[id].sum;
		swap(m[id].maxx,m[id].minn);
		m[id].lazy^=1;
		return;
	}
	down(id);
	int mid=(l+r)>>1;
	if(x<=mid)xiangfan(lid,x,y);
	if(y>mid)xiangfan(rid,x,y);
	up(id);
}
void qfan(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		xiangfan(1,dfn[top[x]],dfn[x]);
		x=fa[top[x]]; 
	}
	if(dep[x]<dep[y])swap(x,y);
	xiangfan(1,dfn[y]+1,dfn[x]);
}
int querysum(int id,int x,int y)
{
	int l=m[id].l,r=m[id].r;
	int mid=(l+r)>>1,ans=0;
	if(x<=l&&r<=y)return m[id].sum;
	down(id);
	if(x<=mid)ans+=querysum(lid,x,y);
	if(y>mid)ans+=querysum(rid,x,y);
	up(id);
	return ans;
}
int qsum(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans+=querysum(1,dfn[top[x]],dfn[x]);
		x=fa[top[x]]; 
	}
	if(dep[x]<dep[y])swap(x,y);
	ans+=querysum(1,dfn[y]+1,dfn[x]);
	return ans;
}
int querymax(int id,int x,int y)
{
	int l=m[id].l,r=m[id].r;
	int mid=(l+r)>>1,ans=-inf;
	if(x<=l&&r<=y)return m[id].maxx;
	down(id);
	if(x<=mid)ans=max(ans,querymax(lid,x,y));
	if(y>mid)ans=max(ans,querymax(rid,x,y));
	up(id);
	return ans;
}
int qmax(int x,int y)
{
	int ans=-inf;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,querymax(1,dfn[top[x]],dfn[x]));
		x=fa[top[x]]; 
	}
	if(dep[x]<dep[y])swap(x,y);
	ans=max(ans,querymax(1,dfn[y]+1,dfn[x]));
	return ans;
}
int querymin(int id,int x,int y)
{
	int l=m[id].l,r=m[id].r;
	int mid=(l+r)>>1,ans=inf;
	if(x<=l&&r<=y)return m[id].minn;
	down(id);
	if(x<=mid)ans=min(ans,querymin(lid,x,y));
	if(y>mid)ans=min(ans,querymin(rid,x,y));
	up(id);
	return ans;
}
int qmin(int x,int y)
{
	int ans=inf;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=min(ans,querymin(1,dfn[top[x]],dfn[x]));
		x=fa[top[x]]; 
	}
	if(dep[x]<dep[y])swap(x,y);
	ans=min(ans,querymin(1,dfn[y]+1,dfn[x]));
	return ans;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		x++,y++;
		addm(x,y,z,i);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	char ss[10];
	scanf("%lld",&t);
	while(t--)
	{
		int x,y,z;
		scanf("%s",ss);
		scanf("%lld%lld",&x,&y);
		x++,y++;
		if(ss[0]=='C')
		{
			x--,y--;
			update(1,dfn[dian[x]],y);
		}
		else if(ss[0]=='N')
		{
			qfan(x,y);
		}
		else if(ss[1]=='U')
		{
			
			printf("%lld\n",qsum(x,y));
		}
		else if(ss[1]=='A')
		{
			printf("%lld\n",qmax(x,y));
		}
		else printf("%lld\n",qmin(x,y));
	}
	
	return 0;
}

标签：总结,lid,剖分,int,top,树链,ans,rid,id
From： https://www.cnblogs.com/oceansofstars/p/18203682

相关文章

  • 树链剖分
    树链剖分把一棵树剖分成若干条链，然后对链进行操作，维护路径上的信息。有点像分块，也是暴力做法，单个操作太慢就整个操作。我们一般用重链剖分，也就是根据子树大小把边分成轻重边。重链剖分定义重儿子：所有子节点中子树最大的节点，多个一样的取任意。轻儿子：不是重儿子的就是轻儿......
  • 2020年迟到的年终总结
    Tips：当你看到这个提示的时候，说明当前的文章是由原emlog博客系统搬迁至此的，文章发布时间已过于久远，编排和内容不一定完整，还请谅解`2020年迟到的年终总结日期：2021-1-26阿珏谈天说地浏览：545次评论：7条我一直在想究竟要不要写年终总结，又该写点什么好呢纠结了一个多月，这......
  • 树链剖分
    树链剖分额一个怎么说感觉很鸡肋的东西，它似乎就是普通线段树加上了个路径上的修改和查询（暂时所学），但是肯定比线段树灵活。不多说，先看成果：：：如何处理树上一个点到另一个点链上的操作？如果考虑暴力的话，肯定是不可行的，因为当这个树变成类似一条链的时候，我们的复杂度就可能被卡到惊人......
  • Stream流常用方法总结
    Stream流思想：先得到集合或者数组的Stream流（就是一根传送带）；把元素放上去；然后就用这个Stream流简化的API来方便的操作元素。 Stream流的三类方法：1、获取Stream流：创建一条流水线，并把数据流放到流水线上准备进行操作；2、中间方法：流水线上的操作，一次操作完毕之后，还可以继续进行其......
  • 20240520刷题总结
    T1(状态置换，搜索与dp,dp存值结构体)T376。还是从搜索角度去考虑：时间，前i物品，最多拿多少。这样我们去设计状态，我一开始设置：时间，前i，值是拿多少。会发现这样会爆。其实换一下，优化效果更好。前i物品，最多拿j，用的最少时间。实际转移就是背包。存值就存结构体。#include<iostream>......
  • 登录页面漏洞总结
    汇总一些项目中挖到过的，和做项目的时候会用到的测试方法，最近也是疲于面试，讲的是时候总是一时想不起来，所以决定还是总结一下吧，以后我还是要多放网络安全相关的，面试官看时候也知道我了解哪些点，但奈何笔记太多需要整理一下再放出来，以前不敢放是因为确实一直觉得自己太菜了。如果后面......
  • 5_20总结
    tomcat设置①On'Update'action:从字面上理解就是手工触发update动作的时候做什么updateresources ----更新静态的资源，比如html,js,css等运行模式和调试模式都是立即生效。updateclassesandresources ----更新java,jsp和静态资源java修改后，会被编译成.cla......
  • 应用层总结笔记2
    1.HTTP是什么超文本传输协议用于主机之间传输文字、图片、视频等超文本数据的规范协议HTTP不限于服务器向客户端发送超文本，服务器之间也可能进行超文本的传输2.******HTTP的状态码除了不常见的1类提示信息还有2类的报文成功收到状态信息3类的重定向信息，表示客户端申请访问......
  • 网络层总结比较4
    1.网络层的IP协议包含哪些内容（1）IP基础知识：IP作用：实现源主机与目标主机之间的通信，是点对点的通信IP和MAC的关系：IP属于网络层、MAC属于数据链路层，IP可以实现复杂网络里两个主机的通信，MAC只用于具有直接链路连接的两个设备之间的通信（2）IP地址相关知识：IP地址定义：表示每个主机或者......
  • 传输层总结笔记3
    1.TCP头格式有源、目的端口号，指示进行通信的两个应用进程；首部长度；序列号，表示数据部分的第一个字节的编号；确认号，表示希望接收到的下一个字节的编号，表明该编号之前的数据都已经被确认接收了；控制位，ACK表示确认号有效性RST表示强制断开连接SYN、FIN方别表示报文属于TCP连接建立......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99