树上DP与树上背包

i_am_std · 2025-10-06 09:55:24 · 个人记录

树上DP

消防局的设立

问题描述

由题意知，及给定一颗树，若节点内建立消防站，周围两个内均不需要建立消防站，问至少需要多少个消防站才能让整个树不发生不可控的火灾？

思路

·f[x][0]：至少让x向上2层之下都覆盖信号的答案。
·f[x][1]：至少让x向上1层之下都覆盖信号的答案。
·f[x][2]：至少让x自己及之下覆盖信号的答案。
·f[x][3]：至少让x向下1层之下都覆盖信号的答案。
·f[x][4]：至少让x向下2层之下都覆盖信号的答案。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=INT_MAX;
int n,f[1010][5];
vector<int> G[1010];
void dfs(int x) {
    if(G[x].empty()) {
        f[x][0]=1,f[x][1]=1,f[x][2]=1;
        return;
    }
    for(int i:G[x]) dfs(i);
    f[x][0]=1;
    int mi=N,mn=N;
    for(int i:G[x]){
        f[x][0]+=f[i][4];
        f[x][1]+=f[i][3];
        f[x][2]+=f[i][2];
        f[x][3]+=f[i][2];
        f[x][4]+=f[i][3];
        mi=min(mi,f[i][0]-f[i][3]);
        mn=min(mn,f[i][1]-f[i][2]);
    }
    f[x][1]+=mi;
    f[x][2]+=mn;
    f[x][1]=min(f[x][1],f[x][0]);
    f[x][2]=min(f[x][2],f[x][1]);
    f[x][3]=min(f[x][3],f[x][2]);
    f[x][4]=min(f[x][4],f[x][3]);
}
int main() {
    cin>>n;
    for(int i=2; i<=n; i++) {
        int u;
        cin>>u;
        G[u].emplace_back(i);
    }
    dfs(1);
    cout<<f[1][2];
}