P2590 [ZJOI2008]树的统计

WA20分...................

#include<bits/stdc++.h>
using namespace std;
struct node{int to,next;}bian[2000010];
int n,m,cnt,head[2000010],tree[2000010*4],maxn[2000010*4];
int fath[2000010],dep[2000010],son[2000010],size[2000010];
int top[2000010],seg[2000010],rev[2000010],w[2000010];
void add(int x,int y){
	cnt++;
	bian[cnt].to=y;
	bian[cnt].next=head[x];
	head[x]=cnt;
}
void build(int k,int l,int r){
	if(l==r){maxn[k]=tree[k]=w[rev[l]];return ;}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	tree[k]=tree[k*2]+tree[k*2+1];
	maxn[k]=max(maxn[k*2],maxn[k*2+1]);
}
void change(int k,int l,int r,int w,int v){//单点修改 把v处改成w 
	if(v>r||v<l)return ;
	if(l==r&&r==v){
		tree[k]=maxn[k]=w;
		return ;
	}
	int mid=(l+r)/2;
	change(k*2,l,mid,w,v);
	change(k*2+1,mid+1,r,w,v);
	tree[k]=tree[k*2]+tree[k*2+1];
	maxn[k]=max(maxn[k*2],maxn[k*2+1]);
}
int Summ,Maxn;//查询用 
void query(int k,int l,int r,int x,int y){
	if(l>y||r<x)return ;
	if(l>=x&&r<=y){
		Summ+=tree[k];
		Maxn=max(Maxn,maxn[k]);
		return ;
	} 
	int mid=(l+r)/2;
	query(k*2,l,mid,x,y);
	query(k*2+1,mid+1,r,x,y);
}
void dfs1(int u,int f){
	fath[u]=f;
	dep[u]=dep[f]+1;
	size[u]=1;
	for(int k=head[u];k;k=bian[k].next)
		if(bian[k].to!=f){
			dfs1(bian[k].to,u);
			size[u]+=size[bian[k].to];
			if(size[bian[k].to]>size[son[u]])son[u]=bian[k].to;
		}
}
void dfs2(int u){
	if(son[u]){
		top[son[u]]=top[u];
		seg[son[u]]=++seg[0];
		rev[seg[0]]=son[u];
		dfs2(son[u]); 
	}
	for(int k=head[u];k;k=bian[k].next){
		if(!top[bian[k].to]){
			top[bian[k].to]=bian[k].to;
			seg[bian[k].to]=++seg[0];
			rev[seg[0]]=bian[k].to;
			dfs2(bian[k].to);
		}
	}
}
int ask(int x,int y){//路径查询 
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
		query(1,1,seg[0],seg[fx],seg[x]);
		x=fath[fx];fx=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	query(1,1,seg[0],seg[x],seg[y]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;i++)cin>>w[i];
	dfs1(1,0);
	seg[0]=seg[1]=top[1]=rev[1]=1;//初始化
	dfs2(1);
	build(1,1,seg[0]);//建树 
	cin>>m;
	for(int i=1;i<=m;i++){
		string s;cin>>s;
		int u,v;cin>>u>>v;
		if(s=="CHANGE")// 把结点 u 的权值改为 v
			change(1,1,seg[0],v,u);
		else {
			Summ=0;Maxn=-0x3f3f3f3f;
			ask(u,v);
			if(s=="QMAX")cout<<Maxn<<endl;
			else if(s=="QSUM")cout<<Summ<<endl;
		}
	}
	return 0;
}