题目链接；
参考；
题目大意
对于一个有 k 个叶子的max min操作树，在 k 个叶子中填入1~k，求树根的最大值；
思路
由于题目中不要求输出填充结果，我们可以使用“第几大”来标记大小：对于max节点，其节点值为子节点的最小值，对于min节点，其节点值为子节点的和；在这个过程中，我们压缩掉了很多无用的信息，简化了问题；
定义状态表示：f[i] 为在以 i 为根节点的子树中，i 的值为子树中的第几大；
定义初值：对于叶子节点 i ，f[i]=1 ；
定义状态转移方程：
对于max节点，f[i]=minj is sonf[j] ；
对于min节点，f[i]=∑j is sonf[j] ；
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int op[300005], f[300005];
vector<int> sn[300005];
void dfs(int x)
{
if (sn[x].empty())
{
f[x] = 1;
return;
}
int fmx = 1000006, fmn = 0;
for (auto m : sn[x])
{
dfs(m);
fmx = min(fmx, f[m]);
fmn += f[m];
}
if (op[x])
f[x] = fmx;
else
f[x] = fmn;
}
int main()
{
int n, tmp;
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%d", &op[i]);
for (int i = 2; i <= n; i++)
scanf("%d", &tmp), sn[tmp].push_back(i);
int k = 0;
for (int i = 1; i <= n; i++)
if (sn[i].empty())
k++;
dfs(1);
cout << k - f[1] + 1;
return 0;
}
|