完全理解树剖了。。不怪别人评价这个算法无脑
核心思想就是跳，这么暴力复杂度居然可以低到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\n",solve(1,o1,o2)); else if(op[1]=='S')printf("%d\n",solve(0,o1,o2)); } }