C++14(g++5.4) 解法, 执行用时: 794ms, 内存消耗: 6296K, 提交时间: 2020-01-28 15:58:26

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e4+1;
const int MAXM = MAXN*4; 
int N;
vector<int> G[MAXN];
int fa[MAXN];
int dep[MAXN];
int siz[MAXN];
int son[MAXN];
int top[MAXN];
int dfn[MAXN];
int rnk[MAXN];
int clk;

int w[MAXN];
int _max[MAXM]; 
int _sum[MAXM];
int query_max(int o, int l, int r, int L, int R) {
  if (R < l || r < L) return -0x3f3f3f3f;
  // cout << "query_max" << " " << o << " " << l << " " << r << "|" << L << " " << R << " " << _max[o] << endl;
  if (L <= l && r <= R) return _max[o];
  int mid = (l+r)/2;
  return max(query_max(o*2, l, mid, L, R), 
             query_max(o*2+1, mid+1, r, L, R));
}
int query_sum(int o, int l, int r, int L, int R) {
  if (R < l || r < L) return 0;
  if (L <= l && r <= R) return _sum[o];
  int mid = (l+r)/2;
  return query_sum(o*2, l, mid, L, R) 
      + query_sum(o*2+1, mid+1, r, L, R);
}
void change(int o, int l, int r, int idx, int v) {
  if (idx < l || r < idx) return;
  if (idx <= l && r <= idx) _max[o] = v, _sum[o] = v;
  else {
    int mid = (l+r)/2;
    change(o*2, l, mid, idx, v);
    change(o*2+1, mid+1, r, idx, v);
    _max[o] = max(_max[o*2], _max[o*2+1]);
    _sum[o] = _sum[o*2] + _sum[o*2+1];
  }
}


void dfs1(int s, int f) {
  fa[s] = f;
  dep[s] = dep[f]+1;
  siz[s] = 1;
  for (auto t: G[s]) if (t != f) {
    dfs1(t, s);
    siz[s] += siz[t];
    if (siz[son[s]] < siz[t]) son[s] = t;
  }
}
void dfs2(int s, int f, int tp) {
  top[s] = tp;
  dfn[s] = ++clk;
  rnk[clk] = s;
  if (son[s]) dfs2(son[s], s, tp); 
  for (auto t: G[s]) if (t != f && son[s] != t) dfs2(t, s, t);
}

int main() {
  cin >> N;
  for (int i = 1; i < N; i++) {
    int u, v; cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs1(1, 0);
  dfs2(1, 0, 1);
  for (int i = 1; i <= N; i++) cin >> w[i];
  for (int i = 1; i <= N; i++) change(1, 1, N, dfn[i], w[i]);
  // for (int i = 1; i <= N; i++) cout << i << " " << dfn[i] << endl;
  // cout << "Init Done" << endl;
  int q; cin >> q;
  while (q--) {
    string op; int u, v; cin >> op >> u >> v;
    if (op == "QMAX") {
      int ans = -0x3f3f3f3f;
      while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) swap(u, v);
        ans = max(ans, query_max(1, 1, N, dfn[top[v]], dfn[v]));
        v = fa[top[v]];
      }
      if (dep[u] > dep[v]) swap(u, v);
      ans = max(ans, query_max(1, 1, N, dfn[u], dfn[v]));
      cout << ans << endl;
    } else if (op == "QSUM") {
      int ans = 0;
      while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) swap(u, v);
        ans += query_sum(1, 1, N, dfn[top[v]], dfn[v]);
        v = fa[top[v]];
      }
      if (dep[u] > dep[v]) swap(u, v);
      ans += query_sum(1, 1, N, dfn[u], dfn[v]);
      cout << ans << endl;
    } else if (op == "CHANGE") {
      w[u] = v;
      change(1, 1, N, dfn[u], v);
    }
  }
}

C++(clang++11) 解法, 执行用时: 629ms, 内存消耗: 9644K, 提交时间: 2020-11-05 16:39:25

#include<bits/stdc++.h>
#define ui unsigned int
#define mid ((l+r)>>1)
#define nxt (p<<1)
using namespace std;
const int nn=30001;
string opt;
int q,x,y,w[nn],maxi[nn<<2],ss[nn<<2];
void update(int p){
	maxi[p]=max(maxi[nxt],maxi[nxt|1]);
	ss[p]=ss[nxt]+ss[nxt|1];
}void plant(int p,int l,int r){
	if(l==r)ss[p]=maxi[p]=w[mid];
	else plant(nxt,l,mid),plant(nxt|1,mid+1,r),update(p);
}void change(int p,int l,int r){
	if(l==r)return ss[p]=maxi[p]=y,void();
	if(x<=mid)change(nxt,l,mid);
	else change(nxt|1,mid+1,r);
	update(p);
}int qmax(int p,int l,int r){
	if(x<=l&&r<=y)return maxi[p];
	int ans=-INT_MAX;
	if(x<=mid)ans=max(ans,qmax(nxt,l,mid));
	if(mid<y)ans=max(ans,qmax(nxt|1,mid+1,r));
	return ans;
}int qsum(int p,int l,int r){
	if(x<=l&&r<=y)return ss[p];
	int ans=0;
	if(x<=mid)ans+=qsum(nxt,l,mid);
	if(mid<y)ans+=qsum(nxt|1,mid+1,r);
	return ans;
}int n,tot,a,b,id[nn],top[nn],dep[nn],fa[nn];
vector<int>son[nn];
void dfs1(int u){
	int v,maxss=0;ss[u]=1;
	for(ui i=0;i<son[u].size();i++)
		if(!ss[v=son[u][i]]){
			fa[v]=u,dep[v]=dep[u]+1;
			dfs1(v),ss[u]+=ss[v];
			if(ss[v]>maxss)
				maxss=ss[v],w[u]=v;
		}
}void dfs2(int u){
	if(!u)return ;int v;
	id[u]=++tot;top[w[u]]=top[u];
	dfs2(w[u]);
	for(ui i=0;i<son[u].size();i++){
		v=son[u][i];
		if(!id[v]&&v!=w[u])dfs2(v);
	}
}int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		son[a].push_back(b);
		son[b].push_back(a);
	}dfs1(1);for(int i=1;i<=n;i++)
		top[i]=i;
	dfs2(1);for(int i=1;i<=n;i++)
		scanf("%d",w+id[i]);
	plant(1,1,n),scanf("%d",&q);
	for(int u,v,ans;q--;){
		cin>>opt;
		scanf("%d%d",&u,&v);
		if(opt=="CHANGE"){
			x=id[u],y=v;
			change(1,1,n);
		}else{
			if(opt=="QSUM")ans=0;
			else ans=-INT_MAX;
			while(top[u]!=top[v]){
				if(dep[top[u]]<dep[top[v]])
					swap(u,v);
				x=id[top[u]],y=id[u];
				if(opt=="QSUM")ans+=qsum(1,1,n);
				else ans=max(ans,qmax(1,1,n));
				u=fa[top[u]];
			}if((x=id[u])>(y=id[v]))swap(x,y);
			if(opt=="QSUM")ans+=qsum(1,1,n);
			else ans=max(ans,qmax(1,1,n));
			printf("%d\n",ans);
		}
	}return 0;
}