题解：AT_abc207_f [ABC207F] Tree Patrolling

显然树上背包，但是每个点的贡献至多为

1

，若该点被控制则相邻点染色时该点无贡献，故而仅使用

dp_{i,j}

表示

i

子树中有

j

个被控制是不够的，需要多添加一些信息。

定义

dp_{i,j,0/1/2}

表示

i

子树中有

j

个被控制，

0

代表

i

未染色也未被控制，

1

代表

i

被控制但没被染色，

2

表示

i

染色，不可能出现染色但没被控制的情况，因为染色即控制了本身。

设

u

为当前节点，

v

为其中一个儿子，枚举

u

已遍历子树被控制的个数

i

和

v

为根的子树被控制点个数

j

，转移方程如下：

若 $u$ 未被染色且未被控制，则 $v$ 不能染色：

dp_{u,i+j,0} = dp_{u,i,0} \times (dp_{v,j,0} + dp_{v,j,1})

若 $u$ 被控制但不染色，要么 $u$ 原来没被控制，被 $v$ 染色后控制，要么 $u$ 原来就被控制， $v$ 任意。

dp_{u,i+j,1} = dp_{u,i-1,0} \times dp_{v,j,2} + dp_{u,i,1} \times (dp_{v,j,0} + dp_{v,j,1} + dp_{v,j,2})

若 $u$ 染色， $v$ 要么已被控制，要么没被控制，此时被 $u$ 控制。

dp_{u,i+j,2} = dp_{u,i,2} \times (dp_{v,j-1,0} + dp_{v,j,1} + dp_{v,j,2})

初始化：

显然对于每个点

i

，若不染本身，

dp_{i,0,0} = 1

。

若染本身，

dp_{i,1,2} = 1

。

注意一些细节：

枚举 $i,j$ 时要倒序枚举，否则会重算。
计算前要将 $dp_u$ 复制到 $t$ 中，然后 $dp_u$ 使用 $t$ 转移，否则会重算。
$dp_{u,i+j,1}$ 和 $dp_{u,i+j,2}$ 由于 $u$ 本身被控制所以在 $i>0$ 时才能转移。
$dp_{u,i+j,2}$ 在转移时 $j-1$ 可能为负数，所以只有 $j>0$ 时才能加上 $dp_{u,i,2} \times dp_{v,j-1,0}$ 。
记得取模。

主要代码

CPP

void dfs(int u, int fa){
	sz[u] = 1; 
	dp[u][0][0] = 1, dp[u][1][2] = 1;
	for(int v : e[u]){
		if(v == fa) continue;
		dfs(v, u);
		for(int i = 0; i <= sz[u] + sz[v]; i ++)
			t[i][0] = t[i][1] = t[i][2] = 0;
		for(int i = sz[u]; i >= 0; i --)
			for(int j = sz[v]; j >= 0; j --){
				t[i + j][0] = (t[i + j][0] + dp[u][i][0] * (dp[v][j][0] + dp[v][j][1])) % MOD;
				if(i > 0) t[i + j][1] = (t[i + j][1] + dp[u][i - 1][0] * dp[v][j][2] % MOD + dp[u][i][1] * (dp[v][j][0] + dp[v][j][1] + dp[v][j][2]) % MOD) % MOD;
				if(i > 0) t[i + j][2] = (t[i + j][2] + dp[u][i][2] * ((j > 0 ? dp[v][j - 1][0] : 0) + dp[v][j][1] + dp[v][j][2])) % MOD;
			}
		for(int i = 0; i <= sz[u] + sz[v]; i ++)
			dp[u][i][0] = t[i][0], dp[u][i][1] = t[i][1], dp[u][i][2] = t[i][2];
		sz[u] += sz[v];
	}
}

题解：AT_abc207_f [ABC207F] Tree Patrolling

文章操作

主要代码

相关推荐

评论

题解：AT_abc207_f [ABC207F] Tree Patrolling