756 字
4 分钟
Evensgn 剪树枝
2017-08-10

题目描述#

繁华中学有一棵苹果树。苹果树有 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
样例输入 2
6
0 1 1 0 4
1 1 0 0 1 0
样例输入 3
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1

样例输出#

样例输出 1
2
样例输出 2
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% 中各有一个点,树的形态是一条链。

题解#

题解链接Evensgn 剪树枝 树规 Ivan

f[x][0]表示与其父边相连的连通块内没有黑苹果的方案数,
f[x][1]则表示有黑苹果,
如果父边被切断,相当于没有黑苹果
初始化时,假设切掉父边,f[x][0]=1,f[x][1]=0;
递归回时转移,每递归回一个子树,f[x][1]=f[x][1]*f[v][0]+f[x][0]*f[v][1],f[x][0]=f[x][0]*f[v][0];
最后处理完每个子树时,若其为黑苹果f[x][1]=f[x][0],否则f[x][0]=f[x][0]+f[x][1](可以切掉)

Mycode

/**
******************************************************************************
* @file Evensgn
* @author WildRage
* @version v 1.0
* @date  2017-5-10 10:55:23
* @brief 
******************************************************************************
*/
#include <cstdio>
#include <cstring>
#include <vector>
const int P = 1e9 + 7;
namespace Mine_WorkSpace
{
struct data
{
    struct edge
    {
        int END, next;
    } v[200005];
    int first[100005], p;
    data()
    {
        memset(first, -1, sizeof(first));
        p = 0;
    }
    void add(int a, int b)
    {
        v[p].END = b;
        v[p].next = first[a];
        first[a] = p++;
    }
} Edge;
bool color[100005];
long long f[100005][2];
void  DP(int rt, int fa)
{
    f[rt][0] = 1;
    f[rt][1] = 0;
    for (int i = Edge.first[rt]; i != -1; i = Edge.v[i].next)
    {
        if (fa != Edge.v[i].END)
        {
            DP(Edge.v[i].END, rt);
            f[rt][1] = (f[rt][1] * f[Edge.v[i].END][0]) % P;
            f[rt][1] = (f[rt][1] + f[Edge.v[i].END][1] * f[rt][0]) % P;
            f[rt][0] = (f[rt][0] * f[Edge.v[i].END][0]) % P;
        }
    }
    if (color[rt])
        f[rt][1] = f[rt][0];
    else
        f[rt][0] = (f[rt][1] + f[rt][0]) % P;
}
int Main()
{
    int n;
    scanf("%d", &n);
    int a, b;
    for (int i = 1; i < n; i++)
    {
        scanf("%d", &b);
        Edge.add(i + 1, b + 1), Edge.add(b + 1, i + 1);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a);
        if (a)
            color[i] = 1;
    }
    DP(1,0);
    printf("%lld\n", f[1][1]);
    // Print_tree(1);
    // while(1);
}
}
int main() { Mine_WorkSpace::Main(); }
Evensgn 剪树枝
https://www.nekomio.com/posts/84/
作者
NekoMio
发布于
2017-08-10
许可协议
CC BY-NC-SA 4.0