完全理解树剖了。。不怪别人评价这个算法无脑
核心思想就是跳，这么暴力复杂度居然可以低到nlogn+Qlog^2
#include<bits/stdc++.h>//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<iostream>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
using namespace std;
#define ll long long
#define pb push_back
#define FOR(a) for(int i=1;i<=a;i++)
const int inf=0x3f3f3f3f;
const int maxn=3e4+9;
int arr[maxn];
struct EDGE{
int v;int next;
}G[maxn<<2];
int head[maxn],tot;
void init(){
memset(head,-1,sizeof head);tot=0;
}
void addedge(int u,int v){
++tot;G[tot].v=v;G[tot].next=head[u];head[u]=tot;
}
int n;
int top[maxn];
int pre[maxn];
int dep[maxn];
int num[maxn];
int p[maxn]; //v的对应位置
int fp[maxn]; //访问序列
int son[maxn]; //重儿子
int pos;
void dfs1(int u,int fa,int d){
dep[u]=d;
pre[u]=fa;
num[u]=1;
for(int i=head[u];~i;i=G[i].next){
int v=G[i].v;
if(v==fa)continue;
dfs1(v,u,d+1);
num[u]+=num[v];
if(son[u]==-1||num[v]>num[son[u]])son[u]=v;
}
}
void getpos(int u,int sp){
top[u]=sp;
p[u]=++pos;
fp[p[u]]=u;
if(!son[u])return;
getpos(son[u],sp);
for(int i=head[u];~i;i=G[i].next){
int v=G[i].v;
if(v!=son[u]&&v!=pre[u])getpos(v,v);
}
}
struct NODE{
int maxx;
int sum;
}ST[maxn<<2];
void pushup(int rt){
ST[rt].maxx=max(ST[rt<<1].maxx,ST[rt<<1|1].maxx);
ST[rt].sum=ST[rt<<1].sum+ST[rt<<1|1].sum;
}
void build(int l,int r,int rt){
if(l==r){ST[rt].maxx=ST[rt].sum=arr[fp[l]];return;}
int m=l+r>>1;
build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushup(rt);
}
void update(int a,int b,int l,int r,int rt){
if(l==r){ST[rt].maxx=ST[rt].sum=b;return;}
int m=l+r>>1;
if(a<=m)update(a,b,l,m,rt<<1);else update(a,b,m+1,r,rt<<1|1);
pushup(rt);
}
int Squery(int a,int b,int l,int r,int rt){
int ans=0;
if(a<=l && b>=r)return ST[rt].sum;
int m=l+r>>1;
if(a<=m)ans+=Squery(a,b,l,m,rt<<1);
if(b>m)ans+=Squery(a,b,m+1,r,rt<<1|1);
return ans;
}
int Mquery(int a,int b,int l,int r,int rt){
//cout<<l<<" "<<r<<endl;
int ans=-inf;
if(a<=l&&b>=r)return ST[rt].maxx;
int m=l+r>>1;
if(a<=m)ans=Mquery(a,b,l,m,rt<<1);
if(b>m)ans=max(ans,Mquery(a,b,m+1,r,rt<<1|1));
return ans;
}
int solve(int kind,int u,int v){
if(kind){ //maxx
int ans=-inf;
while(top[u]!=top[v]){
//cout<<u<<" "<<v<<endl;
if(dep[top[u]]<dep[top[v]])swap(u,v);//u出发
ans=max(ans,Mquery(p[top[u]],p[u],1,n,1));
u=pre[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
ans=max(ans,Mquery(p[v],p[u],1,n,1));
return ans;
}else{
int ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
ans+=Squery(p[top[u]],p[u],1,n,1);
u=pre[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
ans+=Squery(p[v],p[u],1,n,1);
return ans;
}
}
char op[10];
int o1,o2;
int main(){
scanf("%d",&n);
init();
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
addedge(x,y);addedge(y,x);
}
dfs1(1,0,0);
getpos(1,1);
for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
build(1,pos,1);
int t;scanf("%d",&t);
while(t--){
scanf("%s%d%d",op,&o1,&o2);
if(op[1]=='H')update(p[o1],o2,1,n,1);
else if(op[1]=='M')printf("%d ",solve(1,o1,o2));
else if(op[1]=='S')printf("%d ",solve(0,o1,o2));
}
}