保安站岗（树形DP）

分析

点覆盖点的问题涉及祖孙三代，所以要定义三个状态

f[u][0]:节点u被自己覆盖的最小花费
f[u][1]:节点u被儿子覆盖的最小花费
f[u][2]:节点u被父亲覆盖的最小花费 

状态转移方程：
f[u][0]+=min(f[son][0],f[son][1],f[son][2])
f[u][2]+=min(f[son][0],f[son][1]); 
f[u][1]= f[t][0]+∑其他子节点的 min(f[son][0],f[son][1]) 
所以要找最优的 t,使得f[u][1]最小

如果当前儿子v比已知儿子t更优，则一定有
 f[t][0]+∑其他子节点的 min(f[son][0],f[son][1]) 
>f[v][0]+∑其他子节点的 min(f[son][0],f[son][1]) 

等价于
 f[t][0]+∑min(f[son][0],f[son][1])-min(f[t][0],f[t][1])
>f[v][0]+∑min(f[son][0],f[son][1])-min(f[v][0],f[v][1])

等价于
f[t][0]-min(f[t][0],f[t][1]) > f[v][0]-min(f[v][0],f[v][1])

C++代码

#include<iostream>
#include<vector>
using namespace std; 
const int N=1510;
vector<int> e[N];
int f[N][3],pay[N];
int n;
void dfs(int u,int fa){
    f[u][0]=pay[u];
    int t=0;
    for(auto v:e[u]){
        if(v==fa)continue;
        dfs(v,u);
        f[u][0]+=min(f[v][0],min(f[v][1],f[v][2]));
        f[u][2]+=min(f[v][0],f[v][1]);
        if((f[t][0]-min(f[t][0],f[t][1]))>(f[v][0]-min(f[v][0],f[v][1])))
            t=v;
        f[u][1]+=min(f[v][0],f[v][1]);
    }
    f[u][1]+=(f[t][0]-min(f[t][0],f[t][1]));  
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int id,w,k,x;
        cin>>id>>w>>k;
        pay[id]=w;
        while(k--){
            cin>>x;
            e[id].push_back(x);
            e[x].push_back(id);
        }
    }
    f[0][0]=2e9;
    dfs(1,-1);
    cout<<min(f[1][1],f[1][0])<<endl;
    return 0;
}