【BZOJ3052】【WC2013】糖果公园

  带修改树上莫队。取每块大小为\({n^{\frac{2}{3}}}\)，依然对询问排序，第一关键字为左端点所在块编号，第二关键字为右端点所在块编号，第三关键字为该操作的编号。

  暴力查询+修改，时间复杂度\(O({n^{\frac{5}{3}}})\)，由于我的代码自带大常数特效，所以跑了114s。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010;

template <class T>
void read(T &x) {char ch;while ((ch=getchar())<'0' && ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

struct Query
{
	int x,y,ct,xblock,yblock,id;
}Q[maxn];

struct Modification
{
	int x,y,lasty;
}M[maxn];

int temp[maxn];
int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt;
LL V[maxn],W[maxn],C[maxn];
int belong[maxn],Bcnt;
int dep[maxn],fa[maxn][20];
int n,m,q,Qs,Ms,B;
LL ans[maxn];

void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}

int stack[maxn],top;
void DFS(int x,int father,int depth)
{
	dep[x]=depth;
	fa[x][0]=father;
	for (int l=0;fa[fa[x][l]][l];l++) fa[x][l+1]=fa[fa[x][l]][l];
	int bottom=top;
	for (int i=head[x];i;i=next[i]) if (E[i]!=father)
	{
		DFS(E[i],x,depth+1);
		if (top-bottom>=B)
		{
			Bcnt++;
			while (top>bottom) belong[stack[top--]]=Bcnt;
		}
	}
	stack[++top]=x;
}

void Init()
{
	read(n),read(m),read(q);
	B=pow(n,2.0/3.0);
	for (int i=1;i<=m;i++) read(V[i]);
	for (int i=1;i<=n;i++) read(W[i]);
	for (int i=1,x,y;i<n;i++) read(x),read(y),Add_Edge(x,y);
	for (int i=1;i<=n;i++) read(C[i]);
	for (int i=1;i<=q;i++)
	{
		int type;
		read(type);
		if (type==0) ++Ms,read(M[Ms].x),read(M[Ms].y);
		else ++Qs,read(Q[Qs].x),read(Q[Qs].y),Q[Qs].ct=Ms,Q[Qs].id=Qs;
	}
	DFS(1,0,1);
	while (top) belong[stack[top--]]=Bcnt;
	for (int i=1;i<=Qs;i++)
	{
		if (belong[Q[i].x]>belong[Q[i].y]) swap(Q[i].x,Q[i].y);
		Q[i].xblock=belong[Q[i].x],Q[i].yblock=belong[Q[i].y];
	}
	for (int i=1;i<=n;i++) temp[i]=C[i];
	for (int i=1;i<=Ms;i++) M[i].lasty=temp[M[i].x],temp[M[i].x]=M[i].y;
}

bool cmp(const Query &a,const Query &b) {return a.xblock<b.xblock || (a.xblock==b.xblock && (a.yblock<b.yblock || (a.yblock==b.yblock && a.ct<b.ct)));}

int vis[maxn],c[maxn];
LL res;

int LCA(int u,int v)
{
	if (dep[u]<dep[v]) swap(u,v);
	int dis=dep[u]-dep[v],l=0;
	while (dis)
	{
		if (dis&1) u=fa[u][l];
		dis>>=1;l++;
	}
	l=0;
	while (fa[u][l]!=fa[v][l]) l++;
	while (l>=0)
	{
		if (fa[u][l]!=fa[v][l]) u=fa[u][l],v=fa[v][l];
		l--;
	}
	return (u!=v)?fa[u][0]:u;
}

void Update(int u,int v)
{
	v=fa[v][0];
	while (u!=v)
	{
		if (!vis[u])
		{
			res+=V[C[u]]*W[++c[C[u]]];
			vis[u]=1;
		}
		else
		{
			res-=V[C[u]]*W[c[C[u]]--];
			vis[u]=0;
		}
		u=fa[u][0];
	}
}

void Solve()
{
	sort(Q+1,Q+1+Qs,cmp);
	int u=1,v=1,ctr=0;
	for (int i=1;i<=Qs;i++)
	{
		int nu=Q[i].x,nv=Q[i].y,nctr=Q[i].ct;
		int lca=LCA(u,nu);
		Update(u,lca);Update(nu,lca);
		lca=LCA(v,nv);
		Update(v,lca);Update(nv,lca);
		u=nu;v=nv;
		lca=LCA(u,v);
		Update(lca,lca);
		while (ctr>nctr)
		{
			C[M[ctr].x]=M[ctr].lasty;
			if (vis[M[ctr].x]) res+=W[++c[M[ctr].lasty]]*V[M[ctr].lasty]-W[c[M[ctr].y]--]*V[M[ctr].y]; 
			ctr--;
		}
		while (ctr<nctr)
		{
			++ctr;
			C[M[ctr].x]=M[ctr].y;
			if (vis[M[ctr].x]) res+=W[++c[M[ctr].y]]*V[M[ctr].y]-W[c[M[ctr].lasty]--]*V[M[ctr].lasty];
		}
		ans[Q[i].id]=res;
		Update(lca,lca);
	}
	for (int i=1;i<=Qs;i++) printf("%lld\n",ans[i]);
}

int main()
{
	Init();
	Solve();
	return 0;
}