【BZOJ】3052: [wc2013]糖果公园 树分块+带修改莫队算法

#include<cmath> #include<cstdio> #include<cctype> #include<cstring> #include<algorithm> using namespace std; int read(){ int s=0,t=1;char c; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } const int maxn=100010; int tot,n,m,q,B,top,cnt,c0,c1; int first[maxn],deep[maxn],f[maxn][20],belong[maxn],st[maxn],num[maxn],c[maxn],w[maxn],v[maxn],pre[maxn]; long long ans,ANS[maxn]; bool vis[maxn]; struct edge{ int v,from;}e[maxn*2]; struct C0{ int x,y,pre;}a[maxn]; struct C1{ int x,y,t,id;}b[maxn]; void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;} void dfs(int x,int fa){ int lim=top; for(int j=1;(1<<j)<=deep[x];j++)f[x][j]=f[f[x][j-1]][j-1]; for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){ deep[e[i].v]=deep[x]+1; f[e[i].v][0]=x; dfs(e[i].v,x); if(top-lim>=B){ cnt++; while(top>lim)belong[st[top--]]=cnt; } } st[++top]=x; } int lca(int x,int y){ if(deep[x]<deep[y])swap(x,y); int d=deep[x]-deep[y]; for(int j=0;(1<<j)<=d;j++)if((1<<j)&d)x=f[x][j]; if(x==y)return x; for(int j=17;j>=0;j--)if((1<<j)<=deep[x]&&f[x][j]!=f[y][j])x=f[x][j],y=f[y][j]; return f[x][0]; } void reverse(int x){ if(vis[x])ans-=1ll*w[num[c[x]]--]*v[c[x]]; else ans+=1ll*w[++num[c[x]]]*v[c[x]]; vis[x]^=1; } void modify(int x,int y){ if(!vis[x])c[x]=y; else reverse(x),c[x]=y,reverse(x); } void solve(int x,int y){ while(x!=y){ if(deep[x]>deep[y])reverse(x),x=f[x][0]; else reverse(y),y=f[y][0]; } } bool cmp(C1 a,C1 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);} int main(){ n=read();m=read();q=read(); for(int i=1;i<=m;i++)v[i]=read(); for(int i=1;i<=n;i++)w[i]=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); insert(u,v);insert(v,u); } B=pow(n,2.0/3)*0.5; dfs(1,0); while(top)belong[st[top--]]=cnt; for(int i=1;i<=n;i++)c[i]=pre[i]=read(); for(int i=1;i<=q;i++){ int kind=read(),x=read(),y=read(); if(!kind){ a[++c0]=(C0){x,y,pre[x]},pre[x]=y; } else{ b[++c1]=(C1){x,y,c0,c1}; if(belong[b[c1].x]>belong[b[c1].y])swap(b[c1].x,b[c1].y); } } sort(b+1,b+c1+1,cmp); for(int i=1;i<=b[1].t;i++)modify(a[i].x,a[i].y); solve(b[1].x,b[1].y); int c=lca(b[1].x,b[1].y); reverse(c);ANS[b[1].id]=ans;reverse(c); for(int i=2;i<=c1;i++){ for(int j=b[i-1].t+1;j<=b[i].t;j++)modify(a[j].x,a[j].y); for(int j=b[i-1].t;j>b[i].t;j--)modify(a[j].x,a[j].pre); solve(b[i-1].x,b[i].x);solve(b[i-1].y,b[i].y); int c=lca(b[i].x,b[i].y); reverse(c);ANS[b[i].id]=ans;reverse(c); } for(int i=1;i<=c1;i++)printf("%lld\n",ANS[i]); return 0; }