lp2590 ZJOI2008 树的统计

树剖套线段树裸题。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
using namespace std;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=30005;
const int INF=2147483647;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int dep[N],fa[N],sz[N],sn[N],tp[N],dfn[N];
int val[N],n;
inline void dfs0(int X,int FA){
	sz[X]=1,sn[X]=0;
	fa[X]=FA;dep[X]=dep[FA]+1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
	}
}
int cnt=0;
inline void dfs1(int X,int FA,int TP){
	tp[X]=TP;
	dfn[X]=++cnt;
	if(sn[X]){
		dfs1(sn[X],X,TP);
	}
	Fv(i,X){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,X,e[i].v);
	}
}

#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
int tr[240005],mx[240005];
inline void updt(int X){
	tr[X]=tr[LS]+tr[RS];
	mx[X]=Max(mx[LS],mx[RS]);
}
inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=mx[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	updt(X);
	return;
}
inline int qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X];
	}
	if(R<A||L>B){
		return 0;
	}
	return qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);
}
inline int qryMx(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return mx[X];
	}
	if(R<A||L>B){
		return -INF;
	}
	return Max(qryMx(LS,L,MID,A,B),qryMx(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	sz[0]=0;
	dfs0(1,0);
	dfs1(1,0,1);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		chg(1,1,n,dfn[i],val[i]);
	}
	char ch[6];
	int q,ans;
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		std::cin>>ch+1;
		scanf("%d%d",&u,&v);
		switch(ch[2]){
			case 'H':{
				val[u]=v;
				chg(1,1,n,dfn[u],v);
				break;
			}
			case 'S':{
				ans=0;
				while(tp[u]!=tp[v]){
					if(dep[tp[u]]<dep[tp[v]]){
						Swap(u,v);
					}
					ans+=qrySm(1,1,n,dfn[tp[u]],dfn[u]);
					u=fa[tp[u]];
				}
				if(dep[u]>dep[v]){
					Swap(u,v);
				}
				ans+=qrySm(1,1,n,dfn[u],dfn[v]);
				printf("%d\n",ans);
				break;
			}
			case 'M':{
				ans=-INF;
				while(tp[u]!=tp[v]){
					if(dep[tp[u]]<dep[tp[v]]){
						Swap(u,v);
					}
					ans=Max(ans,qryMx(1,1,n,dfn[tp[u]],dfn[u]));
					u=fa[tp[u]];
				}
				if(dep[u]>dep[v]){
					Swap(u,v);
				}
				ans=Max(ans,qryMx(1,1,n,dfn[u],dfn[v]));
				printf("%d\n",ans);
				break;
			}
		}
	}
} 

int main(){
	init();
	return 0;
}