P2590 [ZJOI2008] 树的统计
Orz

#include <bits/stdc++.h>
using namespace std;
int n, q;
const int maxn = 3e4 + 1;
const int inf = 3e4; 
struct edge{
	int fr,to,nxt;
}e[maxn*2] = {};
int head[maxn] = {}, cnt_edge = 0;
int w[maxn] = {};
int dfn[maxn] = {}, rnk[maxn] = {}, son[maxn] = {}, siz[maxn] = {}, dep[maxn] = {}, fa[maxn] = {}, top[maxn] = {};

struct segTree{
	int sum[maxn*4]	, maxx[maxn*4];
	segTree(){
		memset(sum,0,sizeof(sum));
		memset(maxx,0,sizeof(maxx));
	}
	
	void buildTree(int s, int t, int node){
		int left = 2*node, right = 2*node + 1, mid = (s+t)/2;
		if(s == t){
			sum[node] = maxx[node] = w[rnk[t]];
		}
		buildTree(s,mid,left);
		buildTree(mid+1,t,right);
		sum[node] = sum[left] + sum[right];
		maxx[node] = max(maxx[left],maxx[right]);
	}
	
	int getsum(int l, int r, int s, int t, int node){
		int left = 2*node, right = 2*node + 1, mid = (s+t)/2;
		if(s > r || t < l) return 0;
		if(l <= s && t <= r) return sum[node];
		return (getsum(l,r,s,mid,left) + getsum(l,r,mid+1,t,right));
	}
	
	int getmax(int l, int r, int s, int t, int node){
		int left = 2*node, right = 2*node + 1, mid = (s+t)/2;
		if(s > r || t < l) return -inf;
		if(l <= s && t <= r) return maxx[node];
		return (getsum(l,r,s,mid,left) + getsum(l,r,mid+1,t,right));
	}
	
	void update(int x, int k, int s, int t, int node){
		int left = 2*node, right = 2*node + 1, mid = (s+t)/2;
		if(s == t){
			sum[t] = maxx[t] = k;
			return ;
		}
		if(x <= mid) update(x,k,s,mid,left);
		if(x > mid) update(x,k,mid+1,t,right);
		sum[node] = sum[left] + sum[right];
		maxx[node] = max(maxx[left],maxx[right]);
	}
	
}st;
void add_edge(int u, int v){
	e[++cnt_edge] = (edge){u,v,head[u]};
	head[u] = cnt_edge;
}
void dfs1(int u){
	son[u] = -1;
	siz[u] = 1;
	for(int i = head[u]; i != -1; i = e[i].nxt){
		int v = e[i].to;
		if(!dep[v]){
			dep[v] = dep[u] + 1;
			fa[v] = u;
			dfs1(v);
			siz[u] += v;
			if(son[u] == -1 || siz[son[u]] < siz[v] ) son[u] = v;
		}
	}
}
int cnt_dfn = 0;
void dfs2(int u, int t){
	dfn[u] = ++cnt_dfn;
	rnk[cnt_dfn] = u;
	top[u] = u;
	dfs2(son[u], t);	if(son[u] == -1) return;

	for(int i = head[u]; i != -1; i = e[i].nxt){
		int v = e[i].to;
		if(v != fa[u] && v != son[u]) dfs2(v,v);
	}
}
int queryMax(int u, int v){
	int ans = -inf;
	while(top[u] != top[v]){
		if(dep[top[v]] > dep[top[u]]) swap(u,v);
		ans = max(ans, st.getmax(dfn[u],dfn[top[u]],1,n,1));
		u = fa[top[u]];
	}
	if(dfn[u] > dfn[v]) swap(u,v);
	ans = max(ans, st.getmax(dfn[u],dfn[v],1,n,1));
	return ans;
}
int querySum(int u, int v){
	int ans = 0;
	while(top[u] != top[v]){
		if(dep[top[v]] > dep[top[u]]) swap(u,v);
		ans += st.getsum(dfn[u],dfn[top[u]],1,n,1);
		u = fa[top[u]];
	}
	if(dfn[u] > dfn[v]) swap(u,v);
	ans += st.getsum(dfn[u],dfn[v],1,n,1);
	return ans;
}
int main(){
	cin>>n;
	memset(head, -1, sizeof(head));
	for(int i = 1; i <= n-1; ++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u , v); add_edge(v, u);
	}
	for(int i = 1; i <= n; ++i) cin>>w[i];
	
	dep[1] = 1;
	dfs1(1);
	dfs2(1,1);
	st.buildTree(1,n,1);
	do{
		string s; 
		int u, v;
		cin>>s>>u>>v;
		if(s == "CHANGE"){
			st.update(dfn[u],v,1,n,1);
		}
		if(s == "QMAX"){
			printf("%d\n",queryMax(u,v));
		}
		if(s == "QSUM"){
			printf("%d\n",querySum(u,v));
		}
	}while(--q);
	return 0;
}