2022.11.14模拟赛题解

树的覆盖

\(dp_{i,j,0/1/2}\) 表示以 \(i\) 为根的子树中覆盖 \(j\) 个点的方案数。其中 \(0/1/2\) 分别表示了 \(3\) 种情况。

• \(0\) 表示示当前节点和子节点都没被选中
• \(1\) 表示当前节点被选中，子节点选中与不选中都归于这一类
• \(2\) 表示存在子节点被选中且当前节点不选中

考虑 \(\rm dp\) 转移

枚举已遍历子树中选择几个，再枚举正在遍历的子树中选择几个，根据乘法原理相乘即可。

核心代码：

for (auto v : E[x]) {
    if (v == fa) continue;
    dfs(v, x);
    R(i, 0, sz[x]) {
        R(j, 0, sz[v]) {
            R(t1, 0, 2) {
                R(t2, 0, 2) {
                    int sum = i + j, p = t1;
                    if (!t1 && t2 == 1) p = 2, ++sum;
                    if (t1 == 1 && !t2) ++sum;
                    tmp[sum][p] += dp[x][i][t1] * dp[v][j][t2];
                    tmp[sum][p] %= P;
                }
            }
        }
    }
    sz[x] += sz[v];
    R(i, 0, sz[x]) {
        R(j, 0, 2) {
            dp[x][i][j] = tmp[i][j];
            tmp[i][j] = 0;
        }
    }
}

其中 \(sum\) 表示在已遍历子树与正在遍历的子树的选择下会在 \(x\) 的子树中覆盖几个点。
在这里你会发现一些变化，if (!t1 && t2 == 1) p = 2, ++sum; !t1 的意思是 \(x\) 不选且它没有儿子选中，然而 t2==1 的意思是 \(x\) 的正在遍历的点要选，所以两个状态矛盾，现在的状态变为了 \(x\) 不选且它有儿子要选，变为状态 \(2\)。两个 ++sum 的意思是有一个点选了而它相邻的点没选，所以覆盖的总数要 \(+1\)。
还有一个细节，代码中用了一个临时数组来存储当前的 \(dp\)，否则会用到现在的信息就会发生错误。

几乎完整的代码：

const int N = 2005, P = 1e9 + 7;
int n, sz[N], dp[N][N][3], tmp[N][3];
vector <int> E[N];
void dfs(int x, int fa) {
    sz[x] = 1;
    dp[x][1][1] = dp[x][0][0] = 1;
    for (auto v : E[x]) {
        if (v == fa) continue;
        dfs(v, x);
        R(i, 0, sz[x]) {
            R(j, 0, sz[v]) {
                R(t1, 0, 2) {
                    R(t2, 0, 2) {
                        int sum = i + j, p = t1;
                        if (!t1 && t2 == 1) p = 2, ++sum;
                        if (t1 == 1 && !t2) ++sum;
                        tmp[sum][p] += dp[x][i][t1] * dp[v][j][t2];
                        tmp[sum][p] %= P;
                    }
               }
            }
        }
        sz[x] += sz[v];
        R(i, 0, sz[x]) {
            R(j, 0, 2) {
                dp[x][i][j] = tmp[i][j];
                tmp[i][j] = 0;
            }
        }
    }
}
signed main() {
    read(n);
    R(i, 1, n - 1) {
        int u, v;
        read(u, v);
        E[u].pb(v), E[v].pb(u);
    }
    dfs(1, 0);
    int ans = 0;
    R(i, 0, n) {
        ans = dp[1][i][0] + dp[1][i][1] + dp[1][i][2]; ans %= P;
        write(ans), ptc('\n');
    }
    return 0;
}