题目地址：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;}
