题目链接：Codeforces 1153D

Serval 在一棵有根树上玩数字游戏。这棵有根树有 $n$ 个节点，节点 $1$ 是根节点，节点 $i$ 的父亲节点用 $f_i$ 表示。所有非叶子节点上有一个操作 $\max$ 或 $\min$，这意味着这个节点上的值为其所有儿子节点的最大值或最小值。

假设这棵树上有 $k$ 个叶子节点，Serval 会把 $1, 2, \dots, k$ 写在这 $k$ 个节点上（每个数字恰好使用 $1$ 次），并且他想要最大化根节点的值。作为他的好朋友，请你帮他求出根节点的最大值。

数据范围：$2 \le n \le 3 \times 10 ^ 5​$，$1 \le f_i \le i - 1​$。

Solution

我们考虑树形 $\text{DP}$，设 $f(i)$ 表示节点 $i$ 上的最大数字是子树内叶子里第 $f(i)$ 大的数字。那么对于 $\max$ 节点，$f(u) = \min_{v \in \text{son}(u)} f(v)$；对于 $\min$ 节点，$f(u) = \sum_{v \in \text{son}(u)} f(u)$；对于叶子节点，$f(u) = 1​$。

很显然答案就是 $k - f(1) + 1​$。

时间复杂度：$\mathcal O(n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 3e5 + 5;

int n, a[N], fa[N], sz[N], f[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 2; i <= n; i++) scanf("%d", &fa[i]);
    std::fill(sz + 1, sz + n + 1, 1);
    for (int i = n; i >= 2; i--) sz[fa[i]] += sz[i];
    int k = 0;
    for (int i = 1; i <= n; i++) {
        sz[i] == 1 ? k++, f[i] = 1 : f[i] = (a[i] ? N : 0);
    }
    for (int i = n; i >= 2; i--) {
        int p = fa[i];
        a[p] ? f[p] = std::min(f[p], f[i]) : f[p] += f[i];
    }
    printf("%d\n", k - f[1] + 1);
    return 0;
}