Evensgn剪树枝(tree.*) 树形DP

发布于 2017-08-10  6.31k 次阅读


[toggle hide="yes" title="题目" color=""]

Evensgn 剪树枝

出题人:Vincent

时间限制:1s 空间限制:128MB

题目描述

繁华中学有一棵苹果树。苹果树有 n 个节点(也就是苹果),n − 1 条边(也就

是树枝)。调皮的 Evensgn 爬到苹果树上。他发现这棵苹果树上的苹果有两种:一

种是黑苹果,一种是红苹果。Evensgn 想要剪掉 k 条树枝,将整棵树分成 k + 1 个

部分。他想要保证每个部分里面有且仅有一个黑苹果。请问他一共有多少种剪树枝

的方案?

输入格式

第一行一个数字 n,表示苹果树的节点(苹果)个数。

第二行一共 n − 1 个数字 p0, p1, p2, p3, ..., pn−2,pi 表示第 i + 1 个节点和 pi 节

点之间有一条边。注意,点的编号是 0 到 n − 1。

第三行一共 n 个数字 x0, x1, x2, x3, ..., xn−1。如果 xi 是 1,表示 i 号节点是黑

苹果;如果 xi 是 0,表示 i 号节点是红苹果。

输出格式

输出一个数字,表示总方案数。答案对 109 + 7 取模。

样例输入 1

3

0 0

0 1 1

6

样例输出 1

2

样例输入 2

6

0 1 1 0 4

1 1 0 0 1 0

样例输出 2

1

样例输入 3

10

0 1 2 1 4 4 4 0 8

0 0 0 1 0 1 1 0 0 1

样例输出 3

27

数据范围

对于 30% 的数据,1 ≤ n ≤ 10。

对于 60% 的数据,1 ≤ n ≤ 100。

对于 80% 的数据,1 ≤ n ≤ 1000。

对于 100% 的数据,1 ≤ n ≤ 105

对于所有数据点,都有 0 ≤ pi ≤ n − 1,xi = 0 或 xi = 1。

特别地,60% 中、80% 中、100% 中各有一个点,树的形态是一条链。
[/toggle]

又是一道树形DP,考试打暴力期望60,然而只骗到了30。思路非常不显然,至今懵逼。设f[i][0]表示i点上方的连通块中不包含黑点,在i的子树中的方案数;f[i][1]相反。这样设计状态,可以考虑砍i点的父边。

设当前考虑的是u点,先不考虑u点的颜色,递归处理u的子树,递归完成后,再考虑f[u]的取值。对于f[u][1],当u为黑色时,子树只能取f[v][0],表示切掉v的父边。当u不黑时,子树有且只有一个可以取1。对于f[u][0],且u黑,即表示砍掉u的父边,那么子树必须取0。若u不黑,要么砍掉u父边选一个子节点为1,要么不砍父边子树均为0(大雾)。

可以看看这个大佬的博客:http://www.cnblogs.com/OIerShawnZhou/p/7298762.html

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974