^{<style id="uxfti"></style>}

[BZOJ3052][wc2013]糖果公園（樹上帶修改莫隊）

2019-11-06 06:13:43

字體：大中小

來源：轉載

供稿：網友

題目描述

傳送門

題解

樹上帶修改莫隊： 1、將樹分塊，然后離線并將修改和詢問分開，對于詢問的兩個點，將dfs序較小的點作為左端點。 2、將詢問排序，關鍵字為：左端點塊的編號、右端點塊的編號、最近的修改的時間 3、對于兩個詢問，轉移方式是：將兩個左端點的樹鏈狀態取反，將兩個右端點的樹鏈狀態取反。注意取反操作都要刨除樹鏈的lca，在查詢的時候要先加上lca、然后查詢、然后再減去。然后這題就是道裸題了。。注意分塊n232 $n^{2/over 3}/over 2$ 跑的最快

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long long#define N 100005#define sz 17int n,m,k,x,y,opt,cc,cq,val[N],w[N],c[N];int tot,point[N],nxt[N*2],v[N*2];int b,tr,dfs_clock,h[N],in[N],f[N][sz+3],belong[N],stack[N],top;struct data{int x,y,r,id,t;LL ans;}ch[N],q[N];int now,last[N],cnt[N];bool ext[N];LL ans;int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x;}void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}void dfs(int x,int fa){ h[x]=h[fa]+1;in[x]=++dfs_clock; for (int i=1;i<sz;++i) f[x][i]=f[f[x][i-1]][i-1]; int bottom=top; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) { f[v[i]][0]=x; dfs(v[i],x); if (top-bottom>=b) { ++tr; while (top!=bottom) belong[stack[top--]]=tr; } } stack[++top]=x;}int lca(int x,int y){ if (h[x]<h[y]) swap(x,y); int k=h[x]-h[y]; for (int i=0;i<sz;++i) if ((k>>i)&1) x=f[x][i]; if (x==y) return x; for (int i=sz-1;i>=0;--i) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0];}int cmp(data a,data b){ return belong[a.x]<belong[b.x]|| (belong[a.x]==belong[b.x]&&belong[a.y]<belong[b.y])|| (belong[a.x]==belong[b.x]&&belong[a.y]<belong[b.y]&&a.t<b.t);}void change(int x,int opt){ int y=cnt[x]; if (opt==1) ans+=(LL)val[x]*w[y+1]; else ans-=(LL)val[x]*w[y]; cnt[x]+=opt;}void rev(int x){ if (ext[x]) change(c[x],-1); else change(c[x],1); ext[x]^=1;}void modui(int x,int y){ while (x!=y) { if (h[x]<h[y]) swap(x,y); rev(x);x=f[x][0]; }}int main(){ n=read();m=read();k=read(); for (int i=1;i<=m;++i) val[i]=read(); for (int i=1;i<=n;++i) w[i]=read(); for (int i=1;i<n;++i) { x=read();y=read(); add(x,y),add(y,x); } for (int i=1;i<=n;++i) c[i]=read(); b=pow(n,2.0/3.0)*0.5;dfs(1,0); while (top) belong[stack[top--]]=tr; for (int i=1;i<=k;++i) { opt=read(); if (!opt) ch[++cc].x=read(),ch[cc].y=read(); else { q[++cq].x=read(),q[cq].y=read(); q[cq].t=cc;q[cq].id=cq;q[cq].r=lca(q[cq].x,q[cq].y); if (in[q[cq].x]>in[q[cq].y]) swap(q[cq].x,q[cq].y); } } sort(q+1,q+cq+1,cmp); for (int i=1;i<=q[1].t;++i) { last[i]=c[ch[i].x]; c[ch[i].x]=ch[i].y; }now=q[1].t; modui(q[1].x,q[1].y); change(c[q[1].r],1); q[q[1].id].ans=ans; change(c[q[1].r],-1); for (int i=2;i<=cq;++i) { if (now<q[i].t) for (int j=now+1;j<=q[i].t;++j) { if (ext[ch[j].x]) change(c[ch[j].x],-1),change(ch[j].y,1); last[j]=c[ch[j].x]; c[ch[j].x]=ch[j].y; } else for (int j=now;j>q[i].t;--j) { if (ext[ch[j].x]) change(c[ch[j].x],-1),change(last[j],1); c[ch[j].x]=last[j]; } now=q[i].t; modui(q[i-1].x,q[i].x); modui(q[i-1].y,q[i].y); change(c[q[i].r],1); q[q[i].id].ans=ans; change(c[q[i].r],-1); } for (int i=1;i<=cq;++i)