[BZOJ 1036]树的统计

danihao123 posted @ 2015年12月19日 19:29 in 题解 with tags ZJOI bzoj 省选 树链剖分 , 412 阅读
转载请注明出处:http://danihao123.is-programmer.com/

终于A了这题了!

树剖大水题~

然而zzs这种蒟蒻还是要交很多次才过:

zzs大蒟蒻1036交了11次才过

放代码辣:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
const int maxn=30001;
// 邻接表
vector<int> G[maxn];
inline void Add_Edge(int x,int y){
	G[x].push_back(y);
	G[y].push_back(x);
	return;
}
// 线段树
int A[maxn];
int maxv[maxn*4],sumv[maxn*4];
void build_tree(int o,int L,int R){
	if(L==R){
		maxv[o]=sumv[o]=A[L];
		return;
	}
	int M=L+(R-L)/2;
	build_tree(o*2,L,M);
	build_tree(o*2+1,M+1,R);
	maxv[o]=max(maxv[o*2],maxv[o*2+1]);
	sumv[o]=sumv[o*2]+sumv[o*2+1];
	return;
}
int ql,qr;
int _get_max(int o,int L,int R){
	if(ql<=L && R<=qr){
		return maxv[o];
	}else{
		int M=L+(R-L)/2,ans=-0xfffffff;
		if(ql<=M)
			ans=max(ans,_get_max(o*2,L,M));
		if(qr>M)
			ans=max(ans,_get_max(o*2+1,M+1,R));
		return ans;
	}
}
int _get_sum(int o,int L,int R){
	if(ql<=L && R<=qr){
		return sumv[o];
	}else{
		int M=L+(R-L)/2,ans=0;
		if(ql<=M)
			ans+=_get_sum(o*2,L,M);
		if(qr>M)
			ans+=_get_sum(o*2+1,M+1,R);
		return ans;
	}
}
int p,v;
void _change(int o,int L,int R){
	if(L==R){
		sumv[o]=maxv[o]=v;
		return;
	}else{
		int M=L+(R-L)/2;
		if(p<=M)
			_change(o*2,L,M);
		else
			_change(o*2+1,M+1,R);
		maxv[o]=max(maxv[o*2],maxv[o*2+1]);
		sumv[o]=sumv[o*2]+sumv[o*2+1];
		return;
	}
}
inline int get_max(int l,int r){
	ql=l;
	qr=r;
	return _get_max(1,1,n);
}
inline int get_sum(int l,int r){
	ql=l;
	qr=r;
	return _get_sum(1,1,n);
}
inline void change(int pos,int value){
	p=pos;
	v=value;
	_change(1,1,n);
	return;
}
bool vis[maxn];
int dep[maxn],son[maxn],siz[maxn],fa[maxn];
void dfs_1(int x,int father,int depth){
	vis[x]=true;
	dep[x]=depth;
	siz[x]=1;
	fa[x]=father;
	int i,max_siz=0,temp;
	for(i=0;i<G[x].size();i++){
		temp=G[x][i];
		if(!vis[temp]){
			dfs_1(temp,x,depth+1);
			siz[x]+=siz[temp];
			if(siz[temp]>max_siz){
				max_siz=siz[temp];
				son[x]=temp;
			}
		}
	}
	return;
}
int cnt=0;
int top[maxn],tid[maxn],d[maxn];
void dfs_2(int x,int a){
	vis[x]=true;
	A[++cnt]=d[x];
	tid[x]=cnt;
	top[x]=a;
	if(son[x])
		dfs_2(son[x],a);
	else
		return;
	int temp;
	for(int i=0;i<G[x].size();i++){
		temp=G[x][i];
		if(!vis[temp])
			dfs_2(temp,temp);
	}
}
int query_max(int x,int y){
	if(top[x]==top[y]){
		if(tid[x]>tid[y])
			swap(x,y);
		return get_max(tid[x],tid[y]);
	}
	if(dep[top[x]]<dep[top[y]])
		swap(x,y);
	return max(get_max(tid[top[x]],tid[x]),query_max(fa[top[x]],y));
}
int query_sum(int x,int y){
	if(top[x]==top[y]){
		if(tid[x]>tid[y])
			swap(x,y);
		return get_sum(tid[x],tid[y]);
	}
	if(dep[top[x]]<dep[top[y]])
		swap(x,y);
	return get_sum(tid[top[x]],tid[x])+query_sum(fa[top[x]],y);
}
int main(){
	register int i;
	int x,y,t,m;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		Add_Edge(x,y);
	}
	for(i=1;i<=n;i++){
		scanf("%d",&t);
		d[i]=t;
	}
	memset(vis,0,sizeof(vis));
	memset(son,0,sizeof(son));
	dfs_1(1,0,1);
	memset(vis,0,sizeof(vis));
	dfs_2(1,1);
	build_tree(1,1,n);
	scanf("%d",&m);
	char buf[10];
	for(i=0;i<m;i++){
		scanf("\n%s%d%d",buf,&x,&y);
		switch(buf[1]){
			case 'H':
				change(tid[x],y);
				break;
			case 'M':
				printf("%d\n",query_max(x,y));
				break;
			case 'S':
				printf("%d\n",query_sum(x,y));
				break;
		}
	}
	return 0;
}

群众:不解释一下?

zzs:等回来写篇文章具体讲一下树剖~


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter