Codeforces461B Appleman and Tree

原题链接:Codeforces461B

题目大意:给定一棵树,每个点是白色或者黑色,保证至少有一个点是黑色。求将这棵树通过删边划分成,保证每个部分有且仅有一个黑色结点的方案数。

树形 DP

状态表示不看题解想不到,但分类讨论完推出来正确的转移方程,真是神清气爽。

解法

状态表示:$f[u][1]$ 表示对以 $u$ 为根的子树划分,$u$ 所在连通块有且一个黑色点的方案数,$f[u][0]$ 表示对以 $u$ 为根的子树划分,$u$ 所在连通块全是全是白色节点的方案数。

任选一个点作为根结点,这里选择 $0$ 作为根,那么答案就是 $f[0][1]$。

如果 $u=\texttt{black}$,那么初始化 $f[u][1]=1,f[u][0]=0$;如果 $u=\texttt{white}$,那么初始化 $f[u][0]=1,f[u][1]=0$ 。简化写就是 $f[u][\text{color}[u]]=1$ 。

下面我们考虑 $u$ 的所有子结点 $j$,看这条边 $u\rightarrow j$ 是否删去,能对 $f[u][0],f[u][1]$ 作出什么贡献。

一、$u=\texttt{black}$(显然此时 $f[u][0]$ 恒为 $0$,只要计算 $f[u][1]$ 即可)

  1. 如果 $u$ 的子树 $j$ 所在的连通块中全是白色,那么边 $u\rightarrow j$ 必须保留,为 $f[u][1]$ 贡献的方案数为:$f[u][1]\times f[j][0]$ 。
  2. 如果 $u$ 的子树 $j$ 所在连通块有一个黑色,那么边 $u\rightarrow j$ 必须删掉,因为一个连通块中只能有 $1$ 个黑色,而 $u$ 已经是黑色了。由于删边,让 $u$ 和 $j$ 相互独立了,那么能为 $f[u][1]$ 贡献的方案数:$f[u][1]\times f[j][1]$ 。

二、$u=\texttt{white}$( $f[u][0]$ 和 $f[u][1]$ 均需要计算)

  1. 如果 $j$ 的连通块全是白色,若选择保留边 $u\rightarrow j$,就能为 $f[u][0]$ 贡献的方案数:$f[u][0]\times f[j][0]$ 。
  2. 如果 $j$ 的连通块有一个黑色,若删去这条边,那么为 $f[u][0]$ 贡献方案数:$f[u][0]\times f[j][1]$。若保留这条边,那么就可以和 $u$ 合并,为 $f[u][1]$ 贡献的方案数:$f[u][0]\times f[j][1]$ 。

转移方程
$$ f[u][1]=f[u][1]\times(f[j][0]+f[j][1])+f[u][0]\times f[j][1] $$

$$ f[u][0]=f[u][0]\times(f[j][0]+f[j][1]) $$

细节问题:由于 $f[u][1]$ 计算时需要用到上一层状态的 $f[u][0]$。因此,需要先计算第一个转移,再计算第二个转移。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100100, mod = 1e9 + 7;

int n;
int color[N];
int h[N], e[N << 1], ne[N << 1], idx;
LL f[N][2]; // f[u][1]表示对以u为根的子树划分,u所在连通块有且一个黑色点的方案数
// f[u][0]表示...没有黑色点的方案数

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa) {
    f[u][color[u]] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        f[u][1] = ((f[u][1] * (f[j][1] + f[j][0])) % mod + f[u][0] * f[j][1] % mod) % mod;
        f[u][0] = f[u][0] * (f[j][1] + f[j][0]) % mod;    
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int x; scanf("%d", &x);
        add(i + 1, x), add(x, i + 1);
    }
    for (int i = 0; i < n; i++) scanf("%d", &color[i]);
    dfs(0, -1);
    cout << f[0][1] << endl;
    return 0;
}
updatedupdated2020-05-282020-05-28
加载评论
点击刷新