[ZJOI2008]树的统计Count - 树链剖分

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 25368 Solved: 10236
[Submit][Status][Discuss]

Description
　　一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成
一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. QSUM u v: 询问从点u到点v的路径上的节点的权值和注意：从点u到点v的路径上的节点包括u和v本身

Input
　　输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有
一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作
的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

Output
　　对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

Sample Input
4

1 2

2 3

4 1

4 2 1 3

QMAX 3 4

QMAX 3 3

QMAX 3 2

QMAX 2 3

QSUM 3 4

QSUM 2 1

CHANGE 1 5

QMAX 3 4

CHANGE 3 6

QMAX 3 4

QMAX 2 4

QSUM 3 4
Sample Output
4

一道挺简单的树链剖分，刚开始cin，TLE了一发。。。。。。

题意很简单，我们每次操作树上的一个点，或者询问一个区间的最大值或者和。

因为不涉及到子树的操作，所以我们不能dfs序展开，所以迫不得已使出了树上万能操作树链剖分。利用树链剖分把树变成许多个子区间，其实dfs序和树链剖分也就是一种树到区间的hash。

利用树剖hash之后，我们就可以用线段树或者树状数组来维护了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3e4+10;
int n,q,h[N],pos[N],bl[N],sz[N],f[N],cnt;
int head[N],nex[N<<1],to[N<<1],tot;
struct node{
	int l,r,max,sum;
}t[N<<2];
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
inline void push_up(int p){
	t[p].max=max(t[p<<1].max,t[p<<1|1].max);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void dfs1(int x){
	sz[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==f[x])	continue;
		h[to[i]]=h[x]+1;	f[to[i]]=x;
		dfs1(to[i]);	sz[x]+=sz[to[i]];
	}
}
void dfs2(int x,int belong){
	int k=0;	pos[x]=++cnt;	bl[x]=belong;
	for(int i=head[x];i;i=nex[i])
		if(h[to[i]]>h[x]&&sz[to[i]]>sz[k])	k=to[i];
	if(!k)	return ;	dfs2(k,belong);
	for(int i=head[x];i;i=nex[i])
		if(h[to[i]]>h[x]&&to[i]!=k)	dfs2(to[i],to[i]);
}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r;	if(l==r)	return ;
	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
}
void change(int p,int x,int v){
	if(t[p].l==t[p].r){
		t[p].max=t[p].sum=v;	return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	change(p<<1,x,v);
	else	change(p<<1|1,x,v);
	push_up(p);
}
int asksum(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].sum;
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return asksum(p<<1,l,r);
	else if(l>mid)	return asksum(p<<1|1,l,r);
	else	return asksum(p<<1,l,mid)+asksum(p<<1|1,mid+1,r);
}
int askmax(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].max;
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return askmax(p<<1,l,r);
	else if(l>mid)	return askmax(p<<1|1,l,r);
	else	return max(askmax(p<<1,l,mid),askmax(p<<1|1,mid+1,r));
}
int querymax(int x,int y){
	int res=-0x3f3f3f3f;
	while(bl[x]!=bl[y]){
		if(h[bl[x]]<h[bl[y]])	swap(x,y);
		res=max(res,askmax(1,pos[bl[x]],pos[x]));
		x=f[bl[x]];
	}
	if(pos[x]>pos[y])	swap(x,y);
	res=max(res,askmax(1,pos[x],pos[y]));
	return res;
}
int querysum(int x,int y){
	int res=0;
	while(bl[x]!=bl[y]){
		if(h[bl[x]]<h[bl[y]])	swap(x,y);
		res+=asksum(1,pos[bl[x]],pos[x]);
		x=f[bl[x]];
	}
	if(pos[x]>pos[y])	swap(x,y);
	res+=asksum(1,pos[x],pos[y]);
	return res; 
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int a,b;	scanf("%d %d",&a,&b);	add(a,b);	add(b,a);
	}
	dfs1(1);	dfs2(1,1);	build(1,1,n);
	for(int i=1;i<=n;i++){
		int x;	scanf("%d",&x);	change(1,pos[i],x);
	}
	char op[10];	scanf("%d",&q);
	while(q--){
		int x,y;	scanf("%s %d %d",op,&x,&y);
		if(op[0]=='C')	change(1,pos[x],y);
		else if(op[1]=='M')	printf("%d\n",querymax(x,y));
		else	printf("%d\n",querysum(x,y));
	}
	return 0;
}