Serval and Rooted Tree（CF1153D）-DP

題目鏈接；
參考；

題目大意

對於一個有 k 個葉子的max min操作樹，在 k 個葉子中填入1~k，求樹根的最大值；

思路

由於題目中不要求輸出填充結果，我們可以使用“第幾大”來標記大小：對於max節點，其節點值為子節點的最小值，對於min節點，其節點值為子節點的和；在這個過程中，我們壓縮掉了很多無用的信息，簡化了問題；

定義狀態錶示：$f[i]$ 為在以 i 為根節點的子樹中，i 的值為子樹中的第幾大；

定義初值：對於葉子節點 i ，$f[i]=1$ ；

定義狀態轉移方程：
對於max節點，$f[i]={\text{min}}_{j\text{ is son}}f[j]$ ；
對於min節點，$f[i]={\sum }_{j\text{ is son}}f[j]$ ；

代碼

#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;
}