题解 P4074 【[WC2013]糖果公园】
Great_Influence
2018-05-05 19:00:55
## [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$区分一下(偷懒没写结果调试半天)。