P5024 保卫王国(动态dp/整体dp/倍增dp)

做法(倍增)

最好写的一种

以下0为不选，1为选

\(f_{i,0/1}\)为\(i\)子树的最小值，\(g_{i,0/1}\)为除i子树外的最小值

\(fh_{i,j,0/1,0/1}\)为确定\(i\)与\(i\)的\(2^j\)级祖先的状态，\(i\)的\(2^j\)祖先不包括i子树的最小值

这个转移挺好想的，故不赘述

查询

考虑边倍增爬上去，边处理即可

#include<bits/stdc++.h>

typedef long long LL;

const LL maxn=1e6+9,inf=0x3f3f3f3f3f3f3f3f;

inline LL Read(){

	LL x(0),f(1); char c=getchar();

	while(c<'0' || c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0' && c<='9'){

		x=(x<<3)+(x<<1)+c-'0'; c=getchar();

	}return x*f;

}

struct node{

	LL to,nxt;

}dis[maxn<<1];

LL n,q,num;

LL head[maxn],f[maxn][2],inc[maxn][21],g[maxn][2],fh[maxn][21][2][2],dep[maxn],p[maxn];

char s[3];

inline void Add(LL u,LL v){

	dis[++num]=(node){v,head[u]}; head[u]=num;

}

void Dfs1(LL u,LL fa){

	inc[u][0]=fa; dep[u]=dep[fa]+1; f[u][1]=p[u];

	for(LL i=1;i<=20;++i) inc[u][i]=inc[inc[u][i-1]][i-1];

	for(LL i=head[u];i;i=dis[i].nxt){

		LL v(dis[i].to); if(v==fa) continue;

		Dfs1(v,u);

		f[u][0]+=f[v][1]; f[u][1]+=std::min(f[v][0],f[v][1]);

	}

}

void Dfs2(LL u,LL fa){

	fh[u][0][0][1]=fh[u][0][1][1]=f[fa][1]-std::min(f[u][0],f[u][1]);

	fh[u][0][0][0]=inf; fh[u][0][1][0]=f[fa][0]-f[u][1];

	for(LL i=1;i<=20;++i)

		for(LL x=0;x<=1;++x)

			for(LL y=0;y<=1;++y){

				fh[u][i][x][y]=inf;

				for(LL xx=0;xx<=1;++xx)

				        fh[u][i][x][y]=std::min(fh[u][i][x][y],fh[inc[u][i-1]][i-1][xx][y]+fh[u][i-1][x][xx]);

			}

	for(LL i=head[u];i;i=dis[i].nxt){

		LL v(dis[i].to); if(v==fa) continue;

		g[v][0]=g[u][1]+f[u][1]-std::min(f[v][0],f[v][1]);

		g[v][1]=std::min(g[u][0]+f[u][0]-f[v][1],g[v][0]);

		Dfs2(v,u);

	}

}

inline LL Solve(LL a,LL x,LL b,LL y){

	if(dep[a]<dep[b]) std::swap(a,b),std::swap(x,y);

	LL aa[2]={inf,inf},ab[2]={inf,inf};

	LL ta[2]={inf,inf},tb[2]={inf,inf};

	aa[x]=f[a][x]; ab[y]=f[b][y];

	for(LL i=20;i>=0;--i){

		if(dep[inc[a][i]]>=dep[b]){

			for(LL ii=0;ii<=1;++ii){

				ta[ii]=inf;

				for(LL jj=0;jj<=1;++jj)

				    ta[ii]=std::min(ta[ii],aa[jj]+fh[a][i][jj][ii]);

			}

			a=inc[a][i]; aa[1]=ta[1],aa[0]=ta[0];

		}

	}

	if(a==b) return aa[y]+g[a][y];

	for(LL i=20;i>=0;--i){

		if(inc[a][i]!=inc[b][i]){

			for(LL ii=0;ii<=1;++ii){

				ta[ii]=tb[ii]=inf;

				for(LL jj=0;jj<=1;++jj){

					ta[ii]=std::min(ta[ii],aa[jj]+fh[a][i][jj][ii]);

					tb[ii]=std::min(tb[ii],ab[jj]+fh[b][i][jj][ii]);

				}

			}

			a=inc[a][i], b=inc[b][i]; aa[1]=ta[1],aa[0]=ta[0]; ab[1]=tb[1],ab[0]=tb[0];

		}

	}

	LL fa=inc[a][0];

	LL ans0(aa[1]+ab[1]+(g[fa][0]+f[fa][0]-f[a][1]-f[b][1]));

	LL ans1(g[fa][1]+f[fa][1]-std::min(f[a][1],f[a][0])-std::min(f[b][1],f[b][0])+std::min(aa[1],aa[0])+std::min(ab[1],ab[0]));

	return std::min(ans0,ans1);

}

int main(){

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

	n=Read(); q=Read(); scanf(" %s",s+1);

	for(LL i=1;i<=n;++i) p[i]=Read();

	for(LL i=1;i<n;++i){

		LL u(Read()),v(Read()); Add(u,v); Add(v,u);

	}

	Dfs1(1,0); Dfs2(1,0);

	while(q--){

		LL a(Read()),x(Read()),b(Read()),y(Read());

		LL ret(Solve(a,x,b,y));

		if(ret>=inf) puts("-1");

		else printf("%lld\n",ret);

	}

	return 0;

}

整体

思维较大，代码细节有点多

f与g与方法一同理得出

考虑类似tarjan离线的处理方式，用并查集，并查集按秩压缩

\(fa_x\)为x暂时在并查集里的父亲，\(h_{x,0/1,0/1}\)表示确定x父亲与x的状态，x父亲这棵子树的最小值，状态转移压缩时处理

当我们得出(x,y)的祖先时，把查询再丢到祖先u去

查询

对于u存在于(x,y)的情况单独讨论，因为这样u的状态唯一

否则枚举u状态，\(min(g[u][0]+h[a][0][x]+h[b][0][y]-f[u][0],g[u][1]+h[a][1][x]+h[b][1][y]-f[u][1])\)

#include<bits/stdc++.h>

typedef long long LL;

const LL maxn=1e6+9,inf=0x3f3f3f3f3f3f3f3f;

inline LL Read(){

	LL x(0),f(1); char c=getchar();

	while(c<'0' || c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0' && c<='9'){

		x=(x<<3)+(x<<1)+c-'0'; c=getchar();

	}return x*f;

}

struct node{

	LL to,nxt;

}dis[maxn<<1];

struct qy{

	LL a,x,b,y,id;

};

LL n,q,num;

LL head[maxn],f[maxn][2],g[maxn][2],h[maxn][2][2],dep[maxn],p[maxn],fa[maxn],nx[2][2],ans[maxn];

std::vector<qy> Qy[maxn],Ans[maxn];

char s[3];

inline void Add(LL u,LL v){

	dis[++num]=(node){v,head[u]}; head[u]=num;

}

void Dfs1(LL u,LL ff){

	f[u][1]=p[u];

	for(LL i=head[u];i;i=dis[i].nxt){

		LL v(dis[i].to); if(v==ff) continue;

		Dfs1(v,u);

		f[u][0]+=f[v][1]; f[u][1]+=std::min(f[v][0],f[v][1]);

	}

}

void Dfs2(LL u,LL ff){

	for(LL i=head[u];i;i=dis[i].nxt){

		LL v(dis[i].to); if(v==ff) continue;

		g[v][0]=g[u][1]+f[u][1]-std::min(f[v][0],f[v][1]);

		g[v][1]=std::min(g[u][0]+f[u][0]-f[v][1],g[v][0]);

		Dfs2(v,u);

	}

}

inline void Union(LL x,LL y){

	fa[x]=y; LL tmp(f[y][1]-std::min(f[x][0],f[x][1]));

	h[x][0][0]=inf; h[x][0][1]=f[y][0]; h[x][1][1]=tmp+f[x][1]; h[x][1][0]=tmp+f[x][0];

}

void Find(LL x){

	if(fa[x]==fa[fa[x]]) return;

	Find(fa[x]);

	LL up(fa[x]);

	for(LL i=0;i<=1;++i)

	    for(LL j=0;j<=1;++j){

	    	nx[i][j]=h[x][i][j]; h[x][i][j]=inf;

		}

	for(LL i=0;i<=1;++i)

	    for(LL j=0;j<=1;++j)

	        for(LL k=0;k<=1;++k)

	            h[x][i][j]=std::min(h[x][i][j],nx[k][j]+h[up][i][k]-f[up][k]);

	fa[x]=fa[fa[x]];

}

void Dfs3(LL u,LL ff){

	for(LL i=head[u];i;i=dis[i].nxt){

		LL v(dis[i].to); if(v==ff) continue;

		Dfs3(v,u);

		Union(v,u);

	}

	for(LL i=0;i<Qy[u].size();++i){

		LL a(Qy[u][i].a),b(Qy[u][i].b);

		if(a==u) a=b;

		Find(a);

		if(a!=fa[a]){

		    Ans[fa[a]].push_back(Qy[u][i]);

		}

	}

	for(LL i=0;i<Ans[u].size();++i){

		LL a(Ans[u][i].a),b(Ans[u][i].b),x(Ans[u][i].x),y(Ans[u][i].y),id(Ans[u][i].id);

		Find(a); Find(b);

		if(u!=a && u!=b) ans[id]=std::min(g[u][0]+h[a][0][x]+h[b][0][y]-f[u][0],g[u][1]+h[a][1][x]+h[b][1][y]-f[u][1]);

		else{

			if(u!=a) std::swap(a,b),std::swap(x,y);

			ans[id]=g[a][x]+h[b][x][y];

		}

	}

}

int main(){

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

	n=Read(); q=Read(); scanf(" %s",s+1);

	for(LL i=1;i<=n;++i) p[i]=Read();

	for(LL i=1;i<n;++i){

		LL u(Read()),v(Read()); Add(u,v); Add(v,u);

	}

	Dfs1(1,0); Dfs2(1,0);

	for(LL i=1;i<=q;++i){

		LL a(Read()),x(Read()),b(Read()),y(Read());

		Qy[a].push_back((qy){a,x,b,y,i}); Qy[b].push_back((qy){a,x,b,y,i});

	}

	for(LL i=1;i<=n;++i) fa[i]=i;

	Dfs3(1,0);

	for(LL i=1;i<=q;++i){

		if(ans[i]>=inf) puts("-1");

		else printf("%lld\n",ans[i]);

	}

	return 0;

}

巴特西

P5024 保卫王国(动态dp/整体dp/倍增dp)

做法(倍增)

整体

最新文章

热门文章