Siyuan

「Codeforces 1153D」Serval and Rooted Tree
「Codeforces 1153D」Serval and Rooted Tree
扫描右侧二维码阅读全文
29
2019/04

「Codeforces 1153D」Serval and Rooted Tree

题目链接: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;
}
最后修改:2019 年 06 月 28 日 01 : 11 PM

发表评论