传送门
Solution:
就是树链剖分入门题啦~
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define N 30005 #define M 200005 #define lson now<<1 #define rson now<<1|1 #define INF 0x7fffffff using namespace std; int n,tot,first[N],val[N]; int father[N],size[N],maxson[N],depth[N],top[N],id[N],sign,wnew[N]; int ans=0; struct Edge { int to,next; }edge[2*N]; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } struct node { int l,r,sum,maxv; }tree[4*N]; inline void build(int l,int r,int now) { tree[now].l=l,tree[now].r=r,tree[now].sum=0,tree[now].maxv=0; if(l==r) { tree[now].sum=wnew[l]; tree[now].maxv=wnew[l]; return; } int m=(l+r)>>1; build(l,m,lson); build(m+1,r,rson); tree[now].sum=tree[lson].sum+tree[rson].sum; tree[now].maxv=max(tree[lson].maxv,tree[rson].maxv); } inline void update(int now,int x,int k) { if(tree[now].l==x&&tree[now].r==x) { tree[now].sum=k; tree[now].maxv=k; return; } int m=(tree[now].l+tree[now].r)>>1; if(x<=m) update(lson,x,k); else update(rson,x,k); tree[now].sum=tree[lson].sum+tree[rson].sum; tree[now].maxv=max(tree[lson].maxv,tree[rson].maxv); } inline void query_sum(int l,int r,int now) { if(l<=tree[now].l&&tree[now].r<=r) { ans+=tree[now].sum; return; } int m=(tree[now].l+tree[now].r)>>1; if(l<=m) query_sum(l,r,lson); if(r>m) query_sum(l,r,rson); } inline void query_max(int l,int r,int now) { if(l<=tree[now].l&&tree[now].r<=r) { ans=max(ans,tree[now].maxv); return; } int m=(tree[now].l+tree[now].r)>>1; if(l<=m) query_max(l,r,lson); if(r>m) query_max(l,r,rson); } inline void dfs1(int now,int fa) { father[now]=fa; size[now]=1; depth[now]=depth[fa]+1; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs1(vis,now); size[now]+=size[vis]; if(size[vis]>size[maxson[now]]) maxson[now]=vis; } } inline void dfs2(int now,int topf) { id[now]=++sign; top[now]=topf; wnew[sign]=val[now]; if(maxson[now]) dfs2(maxson[now],topf); for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==father[now]||vis==maxson[now]) continue; dfs2(vis,vis); } } inline int qmax(int x,int y) { int ret=-INF; while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y);//默认x比y深 ans=-INF; query_max(id[top[x]],id[x],1); ret=max(ret,ans); x=father[top[x]]; } if(depth[x]<depth[y]) swap(x,y); ans=-INF; query_max(id[y],id[x],1); return max(ret,ans); } inline int qsum(int x,int y) { int ret=0; while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y);//默认x比y浅 ans=0; query_sum(id[top[x]],id[x],1); ret+=ans; x=father[top[x]]; } if(depth[x]<depth[y]) swap(x,y); ans=0; query_sum(id[y],id[x],1); ret+=ans; return ret; } int main() { cin>>n; for(int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; addedge(x,y); addedge(y,x); } for(int i=1;i<=n;i++) cin>>val[i]; dfs1(1,0); dfs2(1,1); build(1,n,1); int Q; cin>>Q; while(Q--) { string s; int x,y; cin>>s>>x>>y; if(s=="CHANGE") update(1,id[x],y); if(s=="QMAX") cout<<qmax(x,y)<<'\n'; if(s=="QSUM") cout<<qsum(x,y)<<'\n'; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9467483.html
