Serval and Rooted Tree（CF1153D）-DP

Topic link ;
Reference resources ;

The main idea of the topic

For one there is k A leaf max min Operation tree , stay k Fill the leaves with 1~k, Find the maximum value of tree root ;

Ideas

Because the title does not require the output of filling results , We can use “ What is the largest ” To mark the size ： about max node , The node value is the minimum value of the child node , about min node , The node value is the sum of the child nodes ; In the process , We have compressed a lot of useless information , Simplify the problem ;

Define the state representation ：$f[i]$ For at i In the subtree of the root node ,i Is the largest value in the subtree ;

Define the initial value ： For leaf nodes i ,$f[i]=1$ ;

Define the state transfer equation ：
about max node ,$f[i]={\text{min}}_{j\text{ is son}}f[j]$ ;
about min node ,$f[i]={\sum }_{j\text{ is son}}f[j]$ ;

Code

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