树链剖分裸题，可以当作熟悉模板写一下把
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; #define ll long long #define re register #define pb push_back #define fi first #define se second const int N=1e6+10; const int mod=998244353; void read(int &a) { a=0;int d=1;char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } struct note{int l,r;ll lazy,sum,ma;}tree[N<<1]; int top[N],id[N],rk[N],son[N],siz[N],f[N],cnt,dep[N],val[N],rt=1; vector <int> v[N]; void dfs1(int x) { siz[x]=1,dep[x]=dep[f[x]]+1; for(auto i:v[x]) { if(i!=f[x]) { f[i]=x,dfs1(i); siz[x]+=siz[i]; if(siz[son[x]]<siz[i]) son[x]=i; } } } void dfs2(int x,int tp) { top[x]=tp;id[x]=++cnt;rk[cnt]=x; if(son[x]) dfs2(son[x],tp); for(auto i:v[x]) if(i!=son[x]&&i!=f[x]) dfs2(i,i); } void build(int l,int r,int now) { tree[now].l=l,tree[now].r=r; if(l==r) {tree[now].sum=val[rk[l]],tree[now].lazy=0,tree[now].ma=val[rk[l]];return;} int m=l+r>>1; build(l,m,now<<1),build(m+1,r,now<<1|1); tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; tree[now].ma=max(tree[now<<1].ma,tree[now<<1|1].ma); } void work(int now,int k) { tree[now].sum=1ll*(tree[now].r-tree[now].l+1)*k; tree[now].ma=k; tree[now].lazy=k; } void pushdown(int now) { work(now<<1,tree[now].lazy); work(now<<1|1,tree[now].lazy); tree[now].lazy=0; } void modify(int l,int r,int now,int k) { if(tree[now].l>=l&&tree[now].r<=r) {work(now,k);return;} if(tree[now].lazy) pushdown(now); int m=tree[now].l+tree[now].r>>1; if(m>=l) modify(l,r,now<<1,k); if(m<r) modify(l,r,now<<1|1,k); tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; tree[now].ma=max(tree[now<<1].ma,tree[now<<1|1].ma); } ll query(int l,int r,int now) { ll ans=0; if(tree[now].l>=l&&tree[now].r<=r) {return tree[now].sum;} if(tree[now].lazy) pushdown(now); int m=tree[now].l+tree[now].r>>1; if(m>=l) ans+=query(l,r,now<<1); if(m<r) ans+=query(l,r,now<<1|1); return ans; } ll queryy(int l,int r,int now) { ll ans=-1e18; if(tree[now].l>=l&&tree[now].r<=r) {return tree[now].ma;} if(tree[now].lazy) pushdown(now); int m=tree[now].l+tree[now].r>>1; if(m>=l) ans=max(ans,queryy(l,r,now<<1)); if(m<r) ans=max(ans,queryy(l,r,now<<1|1)); return ans; } ll query1(int x,int y) { ll ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(id[top[x]],id[x],1); x=f[top[x]]; } if(dep[x]>dep[y]) swap(x,y); return ans+query(id[x],id[y],1); } ll query2(int x,int y) { ll ans=-1e18; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans=max(ans,queryy(id[top[x]],id[x],1)); x=f[top[x]]; } if(dep[x]>dep[y]) swap(x,y); return ans=max(ans,queryy(id[x],id[y],1)); } int main() { int n,m; read(n); for(re int i=1,x,y;i<n;i++) read(x),read(y),v[x].pb(y),v[y].pb(x); for(re int i=1;i<=n;i++) read(val[i]); dfs1(rt),dfs2(rt,rt),build(1,n,1); read(m); char op[10]; for(re int i=1,l,r;i<=m;i++) { scanf("%s %d %d",&op,&l,&r); if(op[1]=='M') printf("%lld ",query2(l,r)); else if(op[1]=='S') printf("%lld ",query1(l,r)); else modify(id[l],id[l],1,r); } return 0; }