Serval and rooted Tree (cf1153d) - DP

Liens vers les sujets;
RÉFÉRENCES;

Objet

Pour quelqu'un qui a k Une feuillemax minArbre des opérations,In k Remplir les feuilles1~k,Trouvez la valeur maximale pour la racine de l'arbre;

Idées

Comme la sortie des résultats de remplissage n'est pas requise dans la question,On peut utiliser“Quel est le plus grand?”Pour marquer la taille：PourmaxNoeud,Sa valeur de noeud est la valeur minimale du noeud Enfant,PourminNoeud,Dont la valeur du noeud est la somme des noeuds enfants;Dans ce processus,,Nous avons compressé beaucoup d'informations inutiles,Simplifie les problèmes;

Définir la représentation de l'état：$f[i]$ Pour i Dans le Sous - arbre du noeud racine,i La valeur de est la plus élevée des sous - arbres;

Définir les valeurs initiales：Pour les noeuds de feuilles i ,$f[i]=1$ ;

Définir l'équation de transfert d'état：
PourmaxNoeud,$f[i]={\text{min}}_{j\text{ is son}}f[j]$ ;
PourminNoeud,$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;
}