CF1153D Pigeon d'Or

Description

给一棵树，每个点是子节点的最大值或最小值，将叶子节点填上整数，使这棵树的根最大。

Solution

明显的\(dp\)题，代码很短。

分类讨论如下：

1、如果是叶子节点，\(d_x = 1\)

2、如果是\(min\)节点，\(d_x =\sum_{y \in son_x} d_y\)

3、如果是\(max\)节点，\(d_x = min_{y \in son_x} d_y\)

#include <bits/stdc++.h>

using namespace std;

const int N = 300005;

int n, a[N], b[N], x, k, ans[N], c[N];

int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {

        scanf("%d", &a[i]);

        ans[i] = a[i] ? n + 1 : 0, c[i] = -1;

    }

    for (int i = 2; i <= n; i++) {

        scanf("%d", &x);

        b[i] = x, c[x] = i;

    }

    for (int i = n; i > 1; i--) {

        if (c[i] == -1)

            ans[i] = 1, k++;

        x = b[i];

        ans[x] = a[x] ? std::min(ans[x], ans[i]) : ans[x] + ans[i];

    }

    printf("%d\n", k + 1 - ans[1]);

    return 0;

}

巴特西

CF1153D Pigeon d'Or

Description

Solution

最新文章

热门文章