23
2019
08

信息学奥赛一本通 树链剖分 1560:【例 1】树的统计

这题是模板题,先两个dfs把树剖开,重新编号,再借助线段树求解,求路径上的权值和还需要借助lca的思路先跳到同一条链上再利用区间求和。

#include <iostream>
#include <cstring>
#include <cstdio>
#define MIN -0x3f3f3f3f
#define mem(a,b) memset((a),(b),sizeof((a)))
using namespace std;
int mod=0x3f3f3f3f;
int n,m,r;
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f*x;
} 
struct Edge{
	int to;
	int next;
	int length;
};
Edge edge[400010];
int count[100010],head[100010],tot=0,heavy_son[100010];
void addedge(int u,int v){
	edge[++tot].to=v;
	edge[tot].length=1;
	edge[tot].next=head[u];
	head[u]=tot;
	return ;
}
int dep[100010],father[100010],child_tree[100010];
int a[400010];
//第一次dfs 记录每个点重儿子编号,子节点数目,父节点编号
void dfs1(int u,int fa){
	register int i;
	father[u]=fa;
	int maxson=-1;
	for(i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v!=fa){
			dep[v]=dep[u]+1;
			dfs1(v,u);
			if(child_tree[u]==0) child_tree[u]=1;
			if(child_tree[v]==0) child_tree[v]=1;
			child_tree[u]+=child_tree[v];
			if(child_tree[v]>maxson){
				maxson=child_tree[v];
				heavy_son[u]=v;
			}
		}
	}
	return ;
}
int id[100010],cnt=0,top_line[100010];


//第二次dfs,节点重新编号,先处理重儿子,在处理轻儿子,轻儿子自己成一条链
void dfs2(int u,int top){
	register int i;
	id[u]=++cnt;
	count[cnt]=a[u];
	top_line[u]=top;
	if(!heavy_son[u]) return;
	dfs2(heavy_son[u],top);
	for(i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v!=father[u]&&v!=heavy_son[u]) dfs2(v,v); 
	}
}
int maxn[100010];

//建线段树,跟普通线段上一模一样
void build(int root,int l,int r){
	if(l==r){
		maxn[root]=count[l];
		a[root]=count[l];
		a[root]%=mod;
		return ;
	}
	build(root<<1,l,(l+r)>>1);
	build(root<<1|1,((l+r)>>1)+1,r);
	a[root]=(a[root<<1]+a[root<<1|1])%mod;
	maxn[root]=max(maxn[root<<1],maxn[root<<1|1]);
}
int lazy[400010],len;

//下传lazy数组
void pushdown(int root,int len2){
    lazy[root<<1]+=lazy[root];
    lazy[root<<1|1]+=lazy[root];
    a[root<<1]+=lazy[root]*(len2-(len2>>1));
    a[root<<1|1]+=lazy[root]*(len2>>1);
    a[root<<1]%=mod;
    a[root<<1|1]%=mod;
    lazy[root]=0;
}

//区间更新
void update(int root,int l,int r,int left,int right,int add){
	if(left<=l&&r<=right){
		lazy[root]+=add;
		len=r-l+1;
		a[root]+=add*len;
		maxn[root]=a[root];//+add;
	}
	else{
		len=r-l+1;
		int mid=(l+r)>>1;
		if(lazy[root]) pushdown(root,len);
		if(left<=mid) update(root<<1,l,mid,left,right,add);
		if(right>mid) update(root<<1|1,mid+1,r,left,right,add);
		a[root]=(a[root<<1]+a[root<<1|1])%mod;
		maxn[root]=max(maxn[root<<1],maxn[root<<1|1]);
	}
	return ;
}

//路径区间修改,lca的思想,x,y不在一条链上,先将深度更深的x跳到链首,同时区间修改。不在一条链上,继续往上跳
//跳到一条连上了,就用区间修改就可以了。
void update_road(int x,int y,int add){
	add%=mod;
	while(top_line[x]!=top_line[y]){
		if(dep[top_line[x]]<dep[top_line[y]]) swap(x,y);
		update(1,1,n,id[top_line[x]],id[x],add);
		x=father[top_line[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
                update(1,1,n,id[x],id[y],add);
	return ;
}
int res=MIN;
int res2=MIN;

//区间求和
void query(int root,int l,int r,int left,int right){
	if(left<=l&&r<=right){res+=a[root];res2=max(res2,maxn[root]);res%=mod;return ;}
	else{
		len=(r-l)+1;
		int mid=(l+r)>>1;
		if(lazy[root]) pushdown(root,len);
		if(left<=mid) query(root<<1,l,mid,left,right);
		if(mid<right) query(root<<1|1,mid+1,r,left,right);
	}
	return ;
}

//路径区间求和,lca的思想,x,y不在一条链上,先将深度更深的x跳到链首,同时计算区间和。不在一条链上,继续往上跳
//跳到一条连上了,就用区间求和就可以了。
int road_sum(int x,int y){
	int ans=0;
	while(top_line[x]!=top_line[y]){
		if(dep[top_line[x]]<dep[top_line[y]]) swap(x,y);
		res=0;
		query(1,1,n,id[top_line[x]],id[x]);
		ans+=res;ans%=mod;
		x=father[top_line[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res=0;
	query(1,1,n,id[x],id[y]);
	ans+=res;
	return ans%mod;
}

//修改子树,编号是连续的
void update_tree(int x,int add){
	update(1,1,n,id[x],id[x]+child_tree[x]-1,add);
}

//子树求和,编号是连续的
int tree_sum(int x){
	res=0;
	query(1,1,n,id[x],id[x]+child_tree[x]-1);
	return res;
}
//路径求极值
int road_max(int x,int y){
	int ans=MIN;
	while(top_line[x]!=top_line[y]){
		if(dep[top_line[x]]<dep[top_line[y]]) swap(x,y);
		res2=MIN;
		query(1,1,n,id[top_line[x]],id[x]);
		ans=max(ans,res2);
		x=father[top_line[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res2=MIN;
	query(1,1,n,id[x],id[y]);
	ans=max(ans,res2);
	return ans;
}


int main(){
	mem(id,0);
	mem(dep,0);
	mem(head,-1);
	register int i;
	n=read();
	for(i=1;i<n;i++){
		int u,v;
		u=read();v=read();
		addedge(u,v);
		addedge(v,u);
	}
	for(i=1;i<=n;i++){
		a[i]=read();
	}
	dfs1(1,1);
	dfs2(1,1);
	mem(a,0);
	build(1,1,n);
	m=read();//m即q; 
	while(m--){
		char s[10];
		int u,t;
		scanf("%s",s);
		u=read();t=read();
		if(s[3]=='N'){
			update_road(u,u,t-count[id[u]]);
			count[id[u]]=t;
		}
		else if(s[3]=='X'){
			printf("%d\n",road_max(u,t));
		}
		else if(s[3]=='M'){
			printf("%d\n",road_sum(u,t));
		}
	}
	return 0;
}


« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。