洛谷 P4426 - [HNOI/AHOI2018]毒瘤（虚树+dp）

神仙虚树题。

首先考虑最 trival 的情况：\(m=n-1\)，也就是一棵树的情况。这个我相信刚学树形 \(dp\) 的都能够秒掉罢（确信）。直接设 \(dp_{i,0/1}\) 在表示 \(i\) 的子树内选择，\(i\) 选/不选的方案数。转移就 \(dp_{u,0}=\prod\limits_{v\in son_u}(dp_{v,0}+dp_{v,1}),dp_{u,1}=\prod\limits_{v\in son_u}dp_{v,0}\) 即可。

接下来考虑有非树边的情况，首先我们一遍 DFS 找出所有非树边组成的集合 \(E_t\)（显然 \(|E_t|=m-n+1\)）注意到 \(m\le n+10\)，故 \(|E_t|\le 11\)，我们考虑暴力枚举每条非树边的选择情况——共有 \((0,0),(0,1),(1,0)\) 三种情况，但实际上我们发现如果左端点不选，那右端点就没有限制了，因此我们只需枚举左端点的情况，我们维护一个 \(ban_{u,x}\) 表示点 \(u\) 选/不选是否不可行，那么状态转移方程需改为 \(dp_{u,0}=\prod\limits_{v\in son_u}(dp_{v,0}+dp_{v,1})\times(1-ban_{u,0}),dp_{u,1}=\prod\limits_{v\in son_u}dp_{v,0}\times(1-ban_{u,1})\)。这样复杂度是 \(n2^{|E_t|}\) 的，大约可以拿到 \(75\) 分的好成绩。

考虑进一步优化，注意到虽然状态数很多，但满足 \(ban_{u,0}=1\lor ban_{u,1}=1\) 的点并不多，最多只有 \(22\) 个，因此我们考虑对这些关键点建立虚树，但是由于在建立虚树的过程中我们将有的链缩成了边，因此我们就不能再像之前那样转移了，我们考虑对每条虚树上的边 \(e=(u,v)\)（\(u\) 是 \(v\) 的父亲）预处理一个系数 \(k_{e,0/1,0/1}\)，表示 \(dp_{u,0}=\prod\limits_{e\in E_u}(dp_{v,0}\times k_{e,0,0}+dp_{v,1}\times k_{e,0,1}),dp_{u,1}=\prod\limits_{e\in E_u}(dp_{v,0}\times k_{e,1,0}+dp_{v,1}\times k_{e,1,1})\)（有点类似于矩阵乘法），其中 \(E_u\) 为以 \(u\) 为上端节点的虚链的集合，显然如果我们求出了 \(k_{e,0/1,0/1}\) 就可以直接在虚树上 \(dp\) 了，时间复杂度也就降到了 \(|E_t|\times 2^{|E_t|}\)。

于是现在我们的任务就是求出 \(k_{e,0/1,0/1}\)，首先对于每个虚树边 \((u,v)\) 的对应链上的点 \(w\)，\(w\) 子树内距离 \(w\) 最近的在虚树上的点是唯一的，这个点就是 \(v\)，因此我们再建一个数组 \(dk_{w,0/1,0/1}\) 表示 \(dp_{w,0}=dp_{v,0}\times dk_{w,0,0}+dp_{v,1}\times dk_{w,0,1},dp_{w,1}=dp_{v,0}\times dk_{w,1,0}+dp_{v,1}\times dk_{w,1,1}\)，显然对于关键点 \(u\)，\(dp_{u,0,0}=dp_{u,1,1}=1,dp_{u,1,0}=dp_{u,0,1}=0\)。考虑怎样通过 \(w\) 子树的 \(dk\) 求出 \(dk_w\)，显然对于 \(w\) 的所有儿子，有且只有一个在 \(u\to v\) 这条虚链上，我们假设这个点为 \(x\)，那么对于其他的 \(w\) 的儿子 \(y\ne x\)，\(dp_{y,0},dp_{y,1}\) 显然是定值，根据前面的状态转移方程是直接乘上即可，即 \(dk_{w,0,0/1}\) 乘上 \(dp_{y,0}+dp_{y,1}\)，\(dk_{w,1,0/1}\) 乘上 \(dp_{y,0}\)。而对于 \(w\) 在关键链上的儿子，根据 \(dp_{x,0}=dp_{v,0}\times dk_{x,0,0}+dp_{v,1}\times dk_{x,0,1},dp_{x,1}=dp_{v,0}\times dk_{x,1,0}+dp_{v,1}\times dk_{x,1,1}\)，可以得出 \(x\) 对 \(dp_{w,0}\) 的贡献是 \(dp_{x,0}+dp_{x,1}=dp_{v,0}\times(dk_{x,0,0}+dk_{x,1,0})+dp_{v,1}\times(dk_{x,0,1}+dk_{x,1,1})\)，对 \(dp_{w,1}\) 的贡献是 \(dp_{v,0}\times dk_{x,0,0}+dp_{v,1}\times dk_{x,0,1}\)，故我们需令 \(dk_{w,0,0}\leftarrow dk_{w,0,0}\times(dk_{x,0,0}+dk_{x,1,0}),dk_{w,1,0}\leftarrow dk_{w,1,0}\times dk_{x,0,0}\)，这样即可求出 \(k_{e,0/1,0/1}\)，具体见代码罢。

const int MAXN=1e5+10;

const int MAXK=11;

const int MOD=998244353;

int n,m,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=1,ans=0;

bool ist[MAXN+5],onv[MAXN+5];

void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}

int dfn[MAXN+5],tim=0;pii et[MAXK+5];int ecnt=0;

void dfs1(int x,int f){

	dfn[x]=++tim;

	for(int e=hd[x];e;e=nxt[e]){

		int y=to[e];if(y==f) continue;

		if(!dfn[y]) dfs1(y,x);

		else{

			onv[x]=onv[y]=1;ist[e>>1]=1;

			if(dfn[x]<dfn[y]) et[++ecnt]=mp(x,y);

		}

	}

}

int cnt[MAXN+5];

void dfs2(int x,int f){

	for(int e=hd[x];e;e=nxt[e]){

		int y=to[e];if(y==f||ist[e>>1]) continue;

		dfs2(y,x);cnt[x]+=cnt[y];

	} onv[x]|=(cnt[x]>=2);cnt[x]=!!(cnt[x]+onv[x]);

}

pii k[MAXN+5][2];int dp0[MAXN+5][2];

vector<pair<int,pair<pii,pii> > > g[MAXN+5];

pii operator +(pii lhs,pii rhs){return mp((lhs.fi+rhs.fi)%MOD,(lhs.se+rhs.se)%MOD);}

pii operator *(pii lhs,int rhs){return mp(1ll*lhs.fi*rhs%MOD,1ll*lhs.se*rhs%MOD);}

int dfs3(int x,int f){

	dp0[x][0]=dp0[x][1]=1;int z=0;

	for(int e=hd[x];e;e=nxt[e]){

		int y=to[e];if(y==f||ist[e>>1]) continue;

		int dw=dfs3(y,x);

		if(!dw){

			dp0[x][0]=1ll*dp0[x][0]*(dp0[y][0]+dp0[y][1])%MOD;

			dp0[x][1]=1ll*dp0[x][1]*dp0[y][0]%MOD;

		} else if(onv[x]) g[x].pb(mp(dw,mp(k[y][0]+k[y][1],k[y][0])));

		else k[x][0]=k[y][0]+k[y][1],k[x][1]=k[y][0],z=dw;

	} if(onv[x]) k[x][0]=mp(1,0),k[x][1]=mp(0,1),z=x;

	else k[x][0]=k[x][0]*dp0[x][0],k[x][1]=k[x][1]*dp0[x][1];

//	printf("%d %d %d %d %d\n",x,k[x][0].fi,k[x][0].se,k[x][1].fi,k[x][1].se);

//	printf("%d %d\n",dp0[x][0],dp0[x][1]);

	return z;

}

bool ban[MAXN+5][2];int dp[MAXN+5][2];

void dfs4(int x){

	dp[x][0]=(!ban[x][0])*dp0[x][0];

	dp[x][1]=(!ban[x][1])*dp0[x][1];

	for(int i=0;i<g[x].size();i++){

		int y=g[x][i].fi;dfs4(y);

		pii p0=g[x][i].se.fi,p1=g[x][i].se.se;

		dp[x][0]=1ll*dp[x][0]*((1ll*dp[y][0]*p0.fi+1ll*dp[y][1]*p0.se)%MOD)%MOD;

		dp[x][1]=1ll*dp[x][1]*((1ll*dp[y][0]*p1.fi+1ll*dp[y][1]*p1.se)%MOD)%MOD;

	} //printf("%d %d %d\n",x,dp[x][0],dp[x][1]);

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);

	dfs1(1,0);dfs2(1,0);onv[1]=1;dfs3(1,0);

//	for(int i=1;i<=n;i++) printf("%d%c",onv[i]," \n"[i==n]);

//	for(int i=1;i<=ecnt;i++) printf("%d %d\n",et[i].fi,et[i].se);

	for(int i=0;i<(1<<ecnt);i++){

		for(int j=1;j<=ecnt;j++){

			if(i>>(j-1)&1) ban[et[j].fi][0]=1,ban[et[j].se][1]=1;

			else ban[et[j].fi][1]=1;

		} dfs4(1);ans=(ans+dp[1][0])%MOD;ans=(ans+dp[1][1])%MOD;

		for(int j=1;j<=ecnt;j++){

			if(i>>(j-1)&1) ban[et[j].fi][0]=0,ban[et[j].se][1]=0;

			else ban[et[j].fi][1]=0;

		}

	} printf("%d\n",ans);

	return 0;

}

巴特西

洛谷 P4426 - [HNOI/AHOI2018]毒瘤（虚树+dp）

最新文章

热门文章