【ZJOI2008】【bzoj1036】【树链剖分】树的统计Count

3
24
2016

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 10204 Solved: 4143
[Submit][Status][Discuss]

Description

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. 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

12

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

1

2

2

10

6

5

6

5

16

HINT

Source

树的分治

树链剖分第一题。

模板题竟然写T了,亏我从月初开始写了两遍多..

先把80分的代码发上来：

MY CODE:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector> 
#define mec(a,x) memset(a,x,sizeof(a))
#define F(i,s,t) for(int i=(s);i<=(t);i++) 
using namespace std;
const int N=3e5;
const int inf=500000;
int n,q;
int val[N],w[N];
inline int getint()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
char s[10];
inline void getstring()
{
	int t=0;
	char ch=getchar();
	while(ch<'A'||ch>'Z'){ch=getchar();s[t++]=ch;}
	while(ch>='A'&&ch<='Z'){s[t++]=ch;ch=getchar();}
}
int head[N],tot=0;
struct edge{int fro,go,nxt;}e[N<<1];//树中双向边 
inline void addedge(int x,int y){
	e[++tot]=(edge){x,y,head[x]};head[x]=tot;
	e[++tot]=(edge){y,x,head[y]};head[y]=tot;
}
/*————segment tree 维护点值——————*/
struct seg{int l,r,max,sum;}t[N<<2];
inline void pushup(int k)
{
	t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
	t[k].max=max(t[k<<1].max,t[k<<1|1].max);
}
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
inline void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;
	if(l==r) {t[k].sum=t[k].max=w[l];return;}
	int mid=l+(r-l)/2;
	build(lson);
	build(rson);
	pushup(k);
}
inline void modify(int k,int pos,int data)
{
	if(t[k].l==t[k].r){t[k].sum=t[k].max=data;return;}
	int mid=(t[k].l+t[k].r)/2;
	if(pos<=mid) modify(k<<1,pos,data);
	else modify(k<<1|1,pos,data);
	pushup(k);
}
inline int query_sum(int k,int l,int r,int lx,int rx)
{
	if(l>=lx && rx>=r) return t[k].sum;
	int ans=0;int mid=l+(r-l)/2;
	if(lx<=mid) ans+=query_sum(lson,lx,rx);
	if(rx>mid) ans+=query_sum(rson,lx,rx);
 	return ans;
}
inline int query_max(int k,int l,int r,int lx,int rx)
{
	if(l>=lx && rx>=r) return t[k].max;
	int ans=-inf;int mid=l+(r-l)/2;
	if(lx<=mid) ans=max(ans,query_max(lson,lx,rx));
	if(rx>mid) ans=max(ans,query_max(rson,lx,rx));
	return ans;
}
/*—————operation in tree———————*/
int dep[N],son[N],fa[N],siz[N];
int top[N],id[N],num;
bool vis[N];
inline void clean()
{
	mec(head,0);tot=0;
	mec(dep,0);mec(fa,0);
	mec(siz,0);mec(son,0);
	mec(id,0);num=0;
	mec(val,0);mec(w,0);
	mec(vis,0);
}
inline void dfs(int x,int ff)
{
	vis[x]=1;
	fa[x]=ff;
	dep[x]=dep[ff]+1;
	siz[x]=1;
	son[x]=0;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].go;
		if(vis[y]) continue;
		dfs(y,x);
		siz[x]+=siz[y];
		if(siz[x]>siz[son[x]]) son[x]=y;
	}
}	
inline void dfs2(int x,int chain)
{
	id[x]=++num;//给结点重新编号 
	top[x]=chain;
	if(son[x]) dfs2(son[x],chain);
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].go;
		if(y!=fa[x] && y!=son[x]) dfs2(y,y);
	}
}
inline int getsum(int x,int y)
{
	int ans=0;
	//int f1=top[x],f2=top[y];
	//if(dep[f1]<dep[f2]) swap(x,y);这样无法修改f1与f2
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans+=query_sum(1,1,num,id[top[x]],id[x]);//线段树保存的是点! 
		x=fa[top[x]];
	}
	if(x==y) return ans+val[x];
	
	if(dep[x]>dep[y]) swap(x,y);
	ans+=query_sum(1,1,num,id[x],id[y]);
	return ans;
}		
inline int getmax(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,query_max(1,1,num,id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if(x==y) return max(ans,val[x]);
	
	if(dep[x]>dep[y]) swap(x,y);
	ans=max(ans,query_max(1,1,num,id[x],id[y]));
	return ans;
}
int main()
{
	n=getint();clean();
	F(i,1,n-1) addedge(getint(),getint());
	F(i,1,n) val[i]=getint();
	dfs(1,0);
	dfs2(1,1);//2!!dfs(1,0)不影响 
	F(i,1,n) w[id[i]]=val[i];
	build(1,1,num);
	int x,y;
	q=getint();
	while(q--){
		getstring();
		x=getint();y=getint();
		switch(s[1]){
			case 'H':
				modify(1,id[x],y);//值为x的点的编号(位置) 
				w[id[x]]=y,val[x]=y;
				break;
			case 'M':
				printf("%d\n",getmax(x,y));
				break;
			case 'S':
				printf("%d\n",getsum(x,y));
				break;
		}
	}
	return 0;
}

Category: 未分类 | Tags: 树链剖分 | Read Count: 381

Ryan_<

能追无尽景,始是不凡人_