【BZOJ3052】[wc2013]糖果公园带修改的树上莫队

【BZOJ3052】[wc2013]糖果公园

Description

Input

Output

Sample Input

Sample Output

84
131
27
84

HINT

题解：区间中的带修改的莫队做法：将块的大小设为n^2/3，将所有询问按照(l所在块，r所在块，time)排序，每次暴力移动三个指针即可。

树上莫队做法：将树按siz分块(如果fa的siz<B则加入到fa的块中，否则新建一块)，将询问按(l所在块，r的DFS序)排序，每次暴力移动两个指针即可。

但是当我们扫过移动指针时，需要将经过的所有点的状态取反。但是这能处理边权。所以我们要将LCA单独拿出来特判。

所以带修改的树上莫队呢~将两者合起来就行了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=100010;
typedef long long ll;
int n,m,q,now,tot,B,sum,cnt,flag;
ll ans,f[maxn],v[maxn],w[maxn];
int fa[18][maxn],next[maxn<<1],to[maxn<<1],head[maxn],dep[maxn],siz[maxn],bel[maxn];
int pa[maxn],pb[maxn],pc[maxn],last[maxn],s[maxn],vis[maxn],c[maxn];
struct node
{
	int a,b,tim,org;
}p[maxn];
int rd()
{
	int ret=0,f=1;	char gc=getchar();
	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}
	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();
	return ret*f;
}
void add(int a,int b)
{
	to[++cnt]=b,next[cnt]=head[a],head[a]=cnt;
}
void dfs(int x)
{
	if(x==1||siz[bel[fa[0][x]]]==B)	bel[x]=++sum;
	else	bel[x]=bel[fa[0][x]];
	siz[bel[x]]++;
	for(int i=head[x];i;i=next[i])	if(!dep[to[i]])	fa[0][to[i]]=x,dep[to[i]]=dep[x]+1,dfs(to[i]);
}
bool cmp(node a,node b)
{
	return (bel[a.a]==bel[b.a])?((bel[a.b]==bel[b.b])?(a.tim<b.tim):(bel[a.b]<bel[b.b])):(bel[a.a]<bel[b.a]);
}
inline void rev(int x)
{
	if(!vis[x])	vis[x]=1,s[c[x]]++,ans+=v[c[x]]*w[s[c[x]]];
	else	vis[x]=0,ans-=v[c[x]]*w[s[c[x]]],s[c[x]]--;
}
void work(int a,int b)
{
	if(dep[a]<dep[b])	swap(a,b);
	while(dep[a]>dep[b])	rev(a),a=fa[0][a];
	while(a!=b)	rev(a),rev(b),a=fa[0][a],b=fa[0][b];
}
int lca(int a,int b)
{
	if(dep[a]<dep[b])	swap(a,b);
	for(int i=17;i>=0;i--)	if(dep[fa[i][a]]>=dep[b])	a=fa[i][a];
	if(a==b)	return a;
	for(int i=17;i>=0;i--)	if(fa[i][a]!=fa[i][b])	a=fa[i][a],b=fa[i][b];
	return fa[0][a];
}
int main()
{
	n=rd(),m=rd(),q=rd();
	int i,j,a,b,lc;
	for(i=1;i<=m;i++)	v[i]=rd();
	for(i=1;i<=n;i++)	w[i]=rd();
	for(i=1;i<n;i++)	a=rd(),b=rd(),add(a,b),add(b,a);
	for(i=1;i<=n;i++)	c[i]=rd();
	for(i=1;i<=q;i++)
	{
		if(!rd())	flag=1,j=++tot,pa[j]=rd(),pb[j]=rd(),pc[j]=(!last[pa[j]])?c[pa[j]]:pb[last[pa[j]]],last[pa[j]]=j;
		else	j=i-tot,p[j].a=rd(),p[j].b=rd(),p[j].tim=tot,p[j].org=j;
	}
	if(flag)	B=int(ceil(exp(log(1.0*n)*2.0/3.0)));
	else	B=int(sqrt(double(n)));
	dep[1]=1,dfs(1);
	for(j=1;(1<<j)<=n;j++)	for(i=1;i<=n;i++)	fa[j][i]=fa[j-1][fa[j-1][i]];
	sort(p+1,p+q-tot+1,cmp);
	a=b=1;
	for(i=1;i<=q-tot;i++)
	{
		work(a,p[i].a),work(b,p[i].b),a=p[i].a,b=p[i].b;
		lc=lca(a,b),rev(lc);
		while(now<p[i].tim)
		{
			now++;
			if(vis[pa[now]])	rev(pa[now]),c[pa[now]]=pb[now],rev(pa[now]);
			c[pa[now]]=pb[now];
		}
		while(now>p[i].tim)
		{
			if(vis[pa[now]])	rev(pa[now]),c[pa[now]]=pc[now],rev(pa[now]);
			c[pa[now]]=pc[now],now--;
		}
		f[p[i].org]=ans,rev(lc);
	}
	for(i=1;i<=q-tot;i++)	printf("%lld
",f[i]);
	return 0;
}//4 3 5 1 9 2 7 6 5 1 2 3 3 1 3 4 1 2 3 2 1 1 2 1 4 2 0 2 1 1 1 2 1 4 2

【BZOJ3052】[wc2013]糖果公园 带修改的树上莫队