算法

(树形DP)

树形dp问题往往考虑以当前节点作为根节点的子树在所求问题上的局部最优性，
状态表示往往都要默认加上满足当前节点作为根节点的最好状态，并且尽量做到不重，不漏。

f[u][2]表示 u不放看守 ,且u点被父亲节点监视,且以u为根节点的子树全部被看到(此状态下子节点有无都可以)
易得在这类情况下子节点只能被自己或者孩子保护,由于有多个子节点，为使得所有子节点都被看守，
所以每个节点的最小值累加求和
f[u][2] = sigma(min(f[j][0] , f[j][1])) 

f[u][0]表示u放看守,且以u为根节点的子树全部被看到：
既然u已经放上了看守，说明子节点必然已经被看到，
因此需求得 对于所有子节点，以他们作为根节点的子树全都被看守到所需的最小代价，
每个子节点的状态都保存在f[j][0],f[j][1],f[j][2]中，因此只需取最小再求和即可
f[u][0] = sigma(f[j][0],f[j][1],f[j][2])

注意：由于我们的状态表示虽然可能记录了有父节点的状态，但此时并未将父节点的代价加入进来，
因此其实只是计算了没有父节点的价值，但是有当前节点的价值的最小代价

这一步只是为了让 下一步有当前节点(即上一步的父节点) 的状态更加清晰好求


最后一种也是最复杂的一种：
f[u][1]表示 u不放看守 ,且u点被儿子监视,且以u为根节点的子树全部被看到(至少有一个儿子看到)
首先我们可以枚举当前哪一颗子树看到了u节点，那么其余节点就可有可无，
我们先 求出所有以子节点为根节点的树全被看到的最小值之和，
注意子节点的父节点不能用，不然与定义矛盾（其实f[u][0]就是）
即：sum = sigma(min(f[j][0] , f[j][1])) ，再枚举哪个子节点看到即可

得：f[u][1] = min(f[u][1] , f[u][2] - min(f[j][1],f[j][0]) + f[j][0]);
取min得原因是为了减去原来，因为我们之前取的是小者

C++ 代码

#include <iostream>
#include <cstring>

using namespace std ;

const int N = 1510 ; 
const int INF = 0x3f3f3f3f ;

int idx , h[N] , ne[N] , e[N] ;
int n , t ; 
int a , b , c ;
int st[N] , w[N];
int f[N][3] ;   


void add(int a , int b )
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx++ ;
}

void dfs(int u)
{
    f[u][0] = w[u] ;
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i] ;
        dfs( j );
        f[u][2] += min(f[j][0] , f[j][1]) ;
        f[u][0] += min(f[j][0] , min(f[j][1] , f[j][2]));
    }

    f[u][1] = 1e9;
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        f[u][1] = min(f[u][1] , f[u][2] - min(f[j][1],f[j][0]) + f[j][0]);
    }

    return ;
}

int main()
{
    cin >> n ; 
    memset(h , -1 , sizeof h);
    for(int i = 0 ; i < n ; i++ )
    {
        cin >> a >> c >> t ;
        w[a] = c ;
        while( t -- ){
            cin >> b ;
            add(a , b);
            st[b] = true;
        }
    }

    int root = 1 ;
    while( st[root] )   root++ ;

    dfs( root );

    cout << min( f[root][0] , f[root][1] ) << endl;

    return 0;
}