题解 P4074 【[WC2013]糖果公园】

## [WC2013]糖果公园(树上待修莫队) 可谓莫队题之集大成者。基本上所有的难点都囊括了。 莫队和带修莫队都没什么意思，重点讲一下树上莫队。 ### 引入:[SCOI2005]王室联邦 这道题目没什么意思，一顿乱搜都可以过去。重点是按这道题目的方法，可以将树分得十分均匀。这样就可以引入分块了。如果$B=\sqrt n$，那么块的分布将会十分均匀。下面给出一种分块方法。 ```cpp static int sta[MAXN],tp,blk_cnt,bel[MAXN],pr[MAXN]; //辅助用的栈,栈元素个数，分块数，每个点所属块编号，每个块的省会(仅本题有用) void dfs(int u,int fa=0) { int sz=tp; for(auto v:p[u])if(v^fa) { dfs(v,u); if(tp-sz>=B)//一般=sqrt(n) { pr[++blk_cnt]=u; while(tp>sz)bel[sta[tp--]]=blk_cnt; } } sta[++tp]=u; } ``` ### 正文 利用引入中的分块方法，可以将点均匀分成$\sqrt n$块。之后就和正常莫队区别不大了。第一维按照所属块排序，第二维按照dfn排序。然后就暴力修改即可。 记得带修莫队为了将时间复杂度摊匀分的块大小变为$n^\frac{2}{3}$，这样才能保证复杂度正确。总时间复杂度$O(n^\frac{5}{3})$。 代码: ```cpp #include<bits/stdc++.h> #define For(i,a,b) for(i=(a);i<=(b);++i) #define Forward(i,a,b) for(i=(a);i>=(b);--i) #define Rep(i,a,b) for(register int i=(a);i<=(b);++i) #define Repe(i,a,b) for(register int i=(a);i>=(b);--i) using namespace std; template<typename T>inline void read(T &x) { T s=0,f=1;char k=getchar(); while(!isdigit(k)&&(k^'-'))k=getchar(); if(!isdigit(k)){f=-1;k=getchar();} while(isdigit(k)){s=s*10+(k^48);k=getchar();} x=s*f; } const int MAXN=1e5+7; static int n,m,Q,B,V[MAXN],W[MAXN],C[MAXN],fa[MAXN],dep[MAXN]; static vector<int>p[MAXN]; static int sta[MAXN],tp,blk_cnt,bel[MAXN],dfn[MAXN],e; void dfs(int u) { int sz=tp; dep[u]=dep[fa[u]]+1;dfn[u]=++e; for(auto v:p[u])if(v^fa[u]) { fa[v]=u;dfs(v); if(tp-sz>=B) { ++blk_cnt; while(tp>sz)bel[sta[tp--]]=blk_cnt; } } sta[++tp]=u; } static struct quer { int u,v,tm,id; friend bool operator<(quer a,quer b) {return bel[a.u]^bel[b.u]?bel[a.u]<bel[b.u]:dfn[a.v]<dfn[b.v];} }q[MAXN]; static int t; static int modi[MAXN][3]; inline void init() { read(n);read(m);read(Q);B=pow(n,0.666666); Rep(i,1,m)read(V[i]); Rep(i,1,n)read(W[i]); static int u,v; Rep(i,1,n-1)read(u),read(v),p[u].push_back(v),p[v].push_back(u); dfs(1);e=0; while(tp)bel[sta[tp--]]=blk_cnt; Rep(i,1,n)read(C[i]); static int opt; Rep(i,1,Q) { read(opt);read(u);read(v); if(!opt)modi[++e][0]=u,modi[e][1]=v,modi[e][2]=C[u],C[u]=v; else { if(dfn[u]<dfn[v])swap(u,v); q[++t].u=u;q[t].v=v;q[t].tm=e,q[t].id=t; } } sort(q+1,q+t+1); } static int cnt; static int bar[MAXN],st[MAXN]; static long long ans[MAXN],as; inline void insert(int pos) { st[pos]^=1; if(st[pos])as+=(long long)W[++bar[C[pos]]]*V[C[pos]]; else as-=(long long)W[bar[C[pos]]--]*V[C[pos]]; } static int cross; inline void goup(int&u) { if(!cross) { if(st[u]&&!st[fa[u]])cross=u; else if(!st[u]&&st[fa[u]])cross=fa[u]; } insert(u);u=fa[u]; } inline void modiroad(int u,int v) { if(u==v)return; cross=0; if(st[v])cross=v; if(dep[u]<dep[v])swap(u,v); while(dep[u]>dep[v])goup(u); while(u^v)goup(u),goup(v); insert(u);if(cross)insert(cross); } inline void solve() { static int u,v; u=q[1].u;v=q[1].v;cnt=e; while(cnt>q[1].tm)C[modi[cnt][0]]=modi[cnt][2],--cnt; modiroad(u,v);ans[q[1].id]=as; Rep(i,2,t) { bool flag; while(cnt>q[i].tm) { flag=false; if(st[modi[cnt][0]])insert(modi[cnt][0]),flag=true; C[modi[cnt][0]]=modi[cnt][2]; if(flag)insert(modi[cnt][0]); --cnt; } while(cnt<q[i].tm) { ++cnt; flag=false; if(st[modi[cnt][0]])insert(modi[cnt][0]),flag=true; C[modi[cnt][0]]=modi[cnt][1]; if(flag)insert(modi[cnt][0]); } modiroad(u,q[i].u);modiroad(v,q[i].v);u=q[i].u,v=q[i].v; ans[q[i].id]=as; } Rep(i,1,t)printf("%lld\n",ans[i]); } int main() { init(); solve(); return 0; } ``` 代码量相对较大，推荐个个部分写成函数型，方便调用和$debug$。最好写几个$namespace$区分一下(偷懒没写结果调试半天)。