很裸的一道树刨题，老规矩做一下dfs序然后线段树维护一下
略有不同的是应该维护一下最大最小值
这道题我没怎么刻意去卡常数，最慢的一个998ms很神奇吧
#include<bits/stdc++.h> #define ls(x) x<<1 #define rs(x) x<<1|1 const int INF=-2146183647; using namespace std; const int N=1e6+6; int m,n,k,p,tot,cnt,res,root,inc; int son[N],size[N],id[N],sum[N<<2],maxx[N<<2],fa[N],head[N],dep[N],top[N],vt[N],v[N]; struct egde { int nx,to; } e[N]; void add_edge(int a,int b) { cnt++;e[cnt].to=b;e[cnt].nx=head[a];head[a]=cnt; cnt++;e[cnt].to=a;e[cnt].nx=head[b];head[b]=cnt; } void push_up(int p) { sum[p]=sum[ls(p)]+sum[rs(p)]; maxx[p]=max(maxx[ls(p)],maxx[rs(p)]); } void build(int p,int l,int r) { if (l==r) { sum[p]=vt[l]; maxx[p]=vt[l]; return; } int mid=(l+r)>>1; build(ls(p),l,mid); build(rs(p),mid+1,r); push_up(p); } void update(int p,int l,int r,int pos,int val) { if (l==r&&l==pos) { sum[p]=val; maxx[p]=val; return; } int mid=(l+r)>>1; if (pos<=mid) update(ls(p),l,mid,pos,val); if (pos>mid) update(rs(p),mid+1,r,pos,val); push_up(p); } void qx(int p,int l,int r,int nl,int nr) { if (nl<=l&&r<=nr) { res=max(res,maxx[p]); return; } int mid=(l+r)>>1; if (nl<=mid) qx(ls(p),l,mid,nl,nr); if (nr>mid) qx(rs(p),mid+1,r,nl,nr); } void query(int p,int l,int r,int xl,int xr) { if (xl<=l&&r<=xr) { res+=sum[p]; return; } int mid=(l+r)>>1; if (xl<=mid) query(ls(p),l,mid,xl,xr); if (xr>mid) query(rs(p),mid+1,r,xl,xr); } void dfs1(int x,int f,int deep) { fa[x]=f; dep[x]=deep; size[x]=1; int maxson=-1; for (int i=head[x];i;i=e[i].nx) { int y=e[i].to; if (y==fa[x]) continue; dfs1(y,x,deep+1); size[x]+=size[y]; if (size[y]>maxson) {maxson=size[y];son[x]=y;} } } void dfs2(int x,int topf) { id[x]=++tot; vt[tot]=v[x]; top[x]=topf; if (!son[x]) return; dfs2(son[x],topf); for (int i=head[x];i;i=e[i].nx) { int y=e[i].to; if (y==fa[x]||y==son[x]) continue; dfs2(y,y); } } int qrange(int x,int y) { int ans=0; while (top[x]!=top[y]) { res=0; if (dep[top[x]]<dep[top[y]]) swap(x,y); query(1,1,n,id[top[x]],id[x]); ans+=res; x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); res=0; query(1,1,n,id[x],id[y]); ans+=res; return ans; } int qmax(int x,int y) { int ans=INF; while (top[x]!=top[y]) { res=INF; if (dep[top[x]]<dep[top[y]]) swap(x,y); qx(1,1,n,id[top[x]],id[x]); ans=max(ans,res); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); res=INF; qx(1,1,n,id[x],id[y]); ans=max(ans,res); return ans; } int main() { scanf("%d",&n); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x,y); } for (int i=1;i<=n;i++) scanf("%d",&v[i]); root=1; dfs1(root,0,1); dfs2(root,root); build(1,1,n); scanf("%d",&m); string c; for (int i=1;i<=m;i++) { cin>>c;int x,y; scanf("%d%d",&x,&y); if (c=="QMAX") {printf("%d ",qmax(x,y));} if (c=="QSUM") {printf("%d ",qrange(x,y));} if (c=="CHANGE") {update(1,1,n,id[x],y);} } return 0; }