CF1153D Serval and Rooted Tree

题目地址：CF1153D Serval and Rooted Tree

挺好玩儿也挺考思维的一道题

思路：树形DP+贪心

数组 (d) 维护这样一个值：

对于一个节点 (x) ，它的值最大可以为以 (x) 为根的子树中叶子节点的数值中排名第 (d_x) 大的数值。

感性的理解就是，假如这个节点下有 (n) 个叶子节点，儿这个节点的 (d) 值为 (k) ，那么这个节点最大可以是 (n+1-k) 。

假设现在在节点 (x) ：

如果 (x) 是叶子节点，那么 (d_x = 1) ；

如果 (x) 是 (min) 节点，那么 (d_x = sum_{y in son_x} d_y) ；

如果 (x) 是 (max) 节点，那么 (d_x = min_{y in son_x} d_y) 。

那么显然 (ans = cnt + 1 - d_1) ，其中 (cnt) 为叶子节点个数。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 6;
int n,a[N],d[N],cnt;
vector<int> e[N];

void dfs(int x) {
    if (!e[x].size()) {
        d[x] = 1;
        ++cnt;
        return;
    }
    d[x] = a[x] ? n : 0;
    for (unsigned int i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        dfs(y);
        if (a[x]) d[x] = min(d[x],d[y]);
        else d[x] += d[y];
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
    for (int i = 2,f; i <= n; i++) {
        scanf("%d",&f);
        e[f].push_back(i);
    }
    dfs(1);
    cout << cnt + 1 - d[1] << endl;
    return 0;
}