bzoj3052: [wc2013]糖果公园

时间：2022-05-22 20:09:32

又是一代神题。

uoj测速rank10，bzoj测速rank26（截止当前2016.5.30 12:58）

带修改的树上莫队。

修改很少，块的大小随便定都能A

然而我一开始把开3次根写成了pow(blabla,1/3)

我一副见了鬼的样子.jpg

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

#define ll long long

#define N 200005

#define M 200005

using namespace std;

inline int read(){

	int ret=0;char ch=getchar();

	while (ch<'0'||ch>'9') ch=getchar();

	while ('0'<=ch&&ch<='9'){

		ret=ret*10-48+ch;

		ch=getchar();

	}

	return ret;

}

struct edge{

	int adj,next;

	edge(){}

	edge(int _adj,int _next):adj(_adj),next(_next){}

} e[M];

int n,g[N],m;

void AddEdge(int u,int v){

	e[++m]=edge(v,g[u]);g[u]=m;

	e[++m]=edge(u,g[v]);g[v]=m;

}

int fa[N],deep[N],dfn[N],stamp;

void dfs(int u){

	dfn[u]=++stamp;

	deep[u]=deep[fa[u]]+1;

	for (int i=g[u];i;i=e[i].next){

		int v=e[i].adj;

		if (v==fa[u]) continue;

		fa[v]=u;

		dfs(v);

	}

	++stamp;

}

int anc[N][19];

void precompute(){

	fa[1]=fa[0]=deep[0]=0;stamp=0;

	dfs(1);

	memset(anc[0],0,sizeof(anc[0]));

	for (int i=1;i<=n;++i) anc[i][0]=fa[i];

	for (int k=1;k<17;++k)

		for (int i=1;i<=n;++i)

			anc[i][k]=anc[anc[i][k-1]][k-1];

}

int qlca(int u,int v){

	if (deep[u]<deep[v]) swap(u,v);

	for (int k=16;k>=0;--k) if (deep[anc[u][k]]>=deep[v]) u=anc[u][k];

	for (int k=16;k>=0;--k) if (anc[u][k]!=anc[v][k]) u=anc[u][k],v=anc[v][k];

	return u==v?u:fa[u];

}

struct Query{

	int u,v,tm,id;

} q[N];

int bl[N];

inline bool operator <(const Query &x,const Query &y){

	if (bl[dfn[x.u]]!=bl[dfn[y.u]]) return bl[dfn[x.u]]<bl[dfn[y.u]];

	else if (bl[dfn[x.v]]!=bl[dfn[y.v]]) return bl[dfn[x.v]]<bl[dfn[y.v]];

	else return ((x.tm<y.tm)^(bl[dfn[x.v]]&1));

}

int Q;

int cdy,c[N],val[N],kk[N];

int cnt[N];

bool exist[N];

ll nowans;

void change(int u){

	if (exist[u]) nowans-=(ll)val[c[u]]*kk[cnt[c[u]]--];

	else nowans+=(ll)val[c[u]]*kk[++cnt[c[u]]];

	exist[u]^=1;

}

void moveTo(int u,int v){

	int w=qlca(u,v);

	for (;u!=w;u=fa[u]) change(u);

	for (;v!=w;v=fa[v]) change(v);

}

void modify(int u,int to){

	if (exist[u]) nowans-=(ll)val[c[u]]*kk[cnt[c[u]]--];

	c[u]=to;

	if (exist[u]) nowans+=(ll)val[c[u]]*kk[++cnt[c[u]]];

}

int mdf,pt[N],fr[N],to[N];

int tmpc[N];

ll ans[N];

int main(){

//	freopen("candyland.in","r",stdin);

//	freopen("candyland.out","w",stdout);

	n=read();cdy=read();Q=read();

	for (int i=1;i<=cdy;++i) val[i]=read();

	for (int i=1;i<=n;++i) kk[i]=read();

	memset(g,0,sizeof(g));m=1;

	for (int i=1;i<n;++i) AddEdge(read(),read());

	for (int i=1;i<=n;++i) tmpc[i]=c[i]=read();

	precompute();

	mdf=0;

	for (int i=1;i<=Q;++i)if (read()){

		q[i].u=read();q[i].v=read();

		if (dfn[q[i].u]>dfn[q[i].v]) swap(q[i].u,q[i].v);

		q[i].tm=mdf;

		q[i].id=i;

	}

	else{

		--Q;--i;++mdf;

		pt[mdf]=read();

		fr[mdf]=c[pt[mdf]];

		to[mdf]=c[pt[mdf]]=read();

	}

	int K=max(sqrt(n),pow((double)4*n*n*mdf/Q,1.0/3));

	for (int i=1;i<=2*n;++i) bl[i]=i/K;

	sort(q+1,q+Q+1);

	for (int i=1;i<=n;++i) c[i]=tmpc[i];

	memset(cnt,0,sizeof(cnt));

	memset(exist,0,sizeof(exist));

	q[0].u=q[0].v=1;q[0].tm=0;

	nowans=0;

	int nowtm=0,w;

	for (int i=1;i<=Q;++i){

		moveTo(q[i-1].u,q[i].u);

		moveTo(q[i-1].v,q[i].v);

		change(w=qlca(q[i].u,q[i].v));

		for (;nowtm<q[i].tm;++nowtm) modify(pt[nowtm+1],to[nowtm+1]);

		for (;nowtm>q[i].tm;--nowtm) modify(pt[nowtm],fr[nowtm]);

		ans[q[i].id]=nowans;

		change(w);

	}

	for (int i=1;i<=Q;++i) printf("%lld\n",ans[i]);

	return 0;

}

　　

相关文章