题解：AT_abc207_f [ABC207F] Tree Patrolling

JHR100330 · 2025-08-29 13:06:04 · 题解

显然树上背包，但是每个点的贡献至多为 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，转移方程如下：

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

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

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

初始化：

显然对于每个点 i，若不染本身，dp_{i,0,0} = 1。

若染本身，dp_{i,1,2} = 1。

注意一些细节：

1. 枚举 i,j 时要倒序枚举，否则会重算。

2. 计算前要将 dp_u 复制到 t 中，然后 dp_u 使用 t 转移，否则会重算。

5. 记得取模。

主要代码

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];
    }
}