c++ 树形DP

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


const int N=1505;
const int INF=0x3f3f3f3f;
int n;
int f[N][3];
bool st[N];
vector<int> G[N];
int cost[N]; // 记录在点放置守卫的花费

void dfs(int node){
    f[node][2]=cost[node];
    int d=INF;
    for(auto &v: G[node]){
        dfs(v);
        f[node][0]+=min(f[v][1], f[v][2]);
        f[node][1]+=min(f[v][1], f[v][2]);
        d=min(d, f[v][2]-min(f[v][2], f[v][1])); // 某个子节点的情况, 或者子节点放置守卫(f[v][2])或者被其子节点看到(f[v][1])
        f[node][2]+=min(min(f[v][0],f[v][1]), f[v][2]);
    }
    f[node][1]+=d;
    // f[node][1]=1e9;
    // for(auto &v: G[node]){
    //     f[node][1]=min(f[node][1], f[v][2]+f[node][0]-min(f[v][1], f[v][2]));
    // }
}

int main(){
    memset(f, 0x00, sizeof f);
    memset(st, 0x00, sizeof st);
    memset(cost, 0x00, sizeof cost);
    cin>>n;
    for(int i=1; i<=n; ++i){
        int node, _cost, cnt;
        cin>>node>>_cost>>cnt;
        cost[node]=_cost;
        while(cnt--){
            int _node;
            cin>>_node;
            G[node].push_back(_node);
            st[_node]=true;
        }
    }
    int root=1;
    while(st[root]) root++;
    dfs(root);
    cout<<min(f[root][1], f[root][2])<<endl;

    return 0;
}