记录编号	157035	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	2.347 s
提交时间	2015-04-07 10:06:51	内存使用	12.52 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

#define Maxn 200010
#define INF 0x3f3f3f3f

using namespace std;

struct node{
	node *ch[2];
	int v,sum,maxv,sumv;
	int cmp(int x){
		if(ch[0]->sum+1==x) return -1;
		return x>ch[0]->sum;
	}
	node* init(int x);
	void update(){
		sum=ch[0]->sum+ch[1]->sum+1;
		maxv=max(v,max(ch[0]->maxv,ch[1]->maxv));
		sumv=ch[0]->sumv+ch[1]->sumv+v;
	}
}spT[Maxn],Null,*root;

int tot=0;

node* node::init(int x){
	v=x; maxv=sumv=x;
	ch[0]=ch[1]=&Null; sum=1;
	return this;
}

node* build(int src[],int l,int r){
	if(l==r) return spT[++tot].init(src[l]);
	int mid=(l+r)>>1;
	node* tmp=spT[++tot].init(src[mid]);
	if(l<mid) tmp->ch[0]=build(src,l,mid-1);
	if(mid<r) tmp->ch[1]=build(src,mid+1,r);
	tmp->update();
	return tmp;
}

void rot(node* &o,int x){
	node* tmp=o->ch[x];
	o->ch[x]=tmp->ch[x^1];
	tmp->ch[x^1]=o;
	o->update(); o=tmp;
	o->update();
}

void splay(node* &o,int k){
	int t=o->cmp(k);
	if(t==-1) return;
	if(t) k-=o->ch[0]->sum+1;
	int t1=o->ch[t]->cmp(k);
	if(~t1){
		if(t1) k-=o->ch[t]->ch[0]->sum+1;
		splay(o->ch[t]->ch[t1],k);
		if(t1==t) rot(o,t);
		else rot(o->ch[t],t1);
	}
	rot(o,t);
}

void change(int x,int v){
	splay(root,x+1);
	root->v=v;
	root->update();
}

int qsum(int l,int r){
	int len=r-l+1;
	splay(root,l);
	splay(root->ch[1],len+1);
	node* tmp=root->ch[1]->ch[0];
	return tmp->sumv;
}

int qmax(int l,int r){
	int len=r-l+1;
	splay(root,l);
	splay(root->ch[1],len+1);
	node* tmp=root->ch[1]->ch[0];
	return tmp->maxv;
}

vector<int> G[Maxn];
int n,m,fa[Maxn],hea[Maxn],siz[Maxn],d[Maxn],rank[Maxn];
int tott=0,top[Maxn],a[Maxn];

void dfs(int x){
	siz[x]=1; hea[x]=0;
	for(int i=G[x].size()-1;~i;i--)
		if(G[x][i]!=fa[x]){
			fa[G[x][i]]=x;
			d[G[x][i]]=d[x]+1;
			dfs(G[x][i]);
			siz[x]+=siz[G[x][i]];
			if(!hea[x]||siz[hea[x]]<siz[G[x][i]])
				hea[x]=G[x][i];
		}
}

void cut(int x,int tp){
	top[x]=tp; rank[x]=++tott;
	if(hea[x]) cut(hea[x],tp);
	for(int i=G[x].size()-1;~i;i--)
		if(G[x][i]!=hea[x]&&G[x][i]!=fa[x])
			cut(G[x][i],G[x][i]);
}

int querys(int u,int v){
	int f1=top[u],f2=top[v],ans=0;
	while(f1!=f2){
		if(d[f1]<d[f2]) swap(f1,f2),swap(u,v);
		ans+=qsum(rank[f1],rank[u]);
		u=fa[f1]; f1=top[u];
	}
	if(rank[u]>rank[v]) swap(u,v);
	ans+=qsum(rank[u],rank[v]);
	return ans;
}

int querym(int u,int v){
	int f1=top[u],f2=top[v],ans=-INF;
	while(f1!=f2){
		if(d[f1]<d[f2]) swap(f1,f2),swap(u,v);
		ans=max(ans,qmax(rank[f1],rank[u]));
		u=fa[f1]; f1=top[u];
	}
	if(rank[u]>rank[v]) swap(u,v);
	ans=max(ans,qmax(rank[u],rank[v]));
	return ans;
}

int main(){
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	Null.maxv=-INF;
	Null.sumv=Null.v=0;
	d[1]=1; fa[1]=0;
	dfs(1);
	cut(1,1);
	for(int i=1;i<=n;i++) scanf("%d",&a[rank[i]]);
	root=build(a,0,n+1);
	char cmd[11];
	scanf("%d",&m);
	for(int i=1,x,y;i<=m;i++){
		scanf("%s%d%d",cmd,&x,&y);
		if(cmd[0]=='Q'){
			if(cmd[1]=='S') printf("%d\n",querys(x,y));
			else printf("%d\n",querym(x,y));
		}
		else change(rank[x],y);
	}
	return 0;
}
/*
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
*/