CF 1153D Serval and Rooted Tree

题目描述

https://codeforces.com/contest/1153/problem/D

Solution

我们考虑二分答案 $x$，然后我们进行 $dp$

令 $f[u]$ 表示 $u$ 的子树内达到 $x$ 所用的最少的大于等于 $x$ 的数的个数

那么对于取 $min$，我们有 $f[u]=\sum f[v]$

对于取 $max$，我们有 $f[u]=min\lbrace f[v]\rbrace$

然后我们突然发现好像二分没啥用，直接做一遍 $dp$ 就行了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <numeric>
#define maxn 300010
#define INF 1000000000
using namespace std;

int n, a[maxn];

struct Edge {
    int to, next; 
} e[maxn]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int f[maxn], num;
void dfs(int u) {
    vector<int> A;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; dfs(v);
        A.push_back(f[v]);
    }
    if (A.empty()) return (void) (f[u] = 1, ++num);
    if (!a[u]) f[u] = accumulate(A.begin(), A.end(), 0); 
    else f[u] = *min_element(A.begin(), A.end());
} 

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    for (int i = 2; i <= n; ++i) { int x; cin >> x; add_edge(x, i); }
    dfs(1); cout << num - f[1] + 1 << "\n";
    return 0;
}