[HNOI2003] 消防局的设立 - 树形dp

仍然是点覆盖集问题，但覆盖半径变成了\(2\)

延续上一题的思路，只是式子更加复杂了

想体验一下min_element大法于是不想优化了

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

vector <int> g[N];
int fa[N],n,f[N][5];

void dfs(int p) {
    for(int i=0;i<g[p].size();i++) {
        dfs(g[p][i]);
    }
    f[p][0]=1;
    f[p][1]=f[p][2]=1e+18;
    for(int i=0;i<g[p].size();i++) {
        int q=g[p][i];
        f[p][0]+=*min_element(f[q],f[q]+5);
        f[p][3]+=*min_element(f[q],f[q]+3);
        f[p][4]+=*min_element(f[q],f[q]+4);
        int tmp1=f[q][0],tmp2=f[q][1];
        for(int j=0;j<g[p].size();j++) {
            if(j!=i) {
                int k=g[p][j];
                tmp1+=*min_element(f[k],f[k]+4);
                tmp2+=*min_element(f[k],f[k]+3);
            }
        }
        f[p][1]=min(f[p][1],tmp1);
        f[p][2]=min(f[p][2],tmp2);
    }
}


signed main() {
    cin>>n;
    for(int i=2;i<=n;i++) {
        cin>>fa[i];
        g[fa[i]].push_back(i);
    }
    dfs(1);
    cout<<min(f[1][0],min(f[1][1],f[1][2]));
}

[HNOI2003] 消防局的设立 - 树形dp

原文：https://www.cnblogs.com/mollnn/p/12260620.html