$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

结论：

$f[u][0]=\sum_{}\min(f[j][1],f[j]][2])$

$f[u][2]=\sum_{}\min(\min(f[j][0],f[j]][1]),f[j][2])$

$f[u][1]=f[k][2]+\sum\limits_{j\ne k}\min(f[j][1],f[j]][2])=f[k][2]+f[u][0]-\min(f[k][1],f[k]][2])$

思路：

1. f[u][0] 表示当前点可以被父节点看到，f[u][1] 表示可以被子节点看到，f[u][2] 表示在当前点放一个警卫
2. f[u][0]：则 j 可以被子节点看到或者直接放一个警卫
3. f[u][2]：则 j 可以被父节点或子节点看到，也可以直接放一个警卫
4. f[u][1]：枚举所有子节点，其中一个子节点必须放一个警卫，其他子节点可以被其子节点看到或者直接放一个警卫

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1510;

int n;
int h[N],e[N],w[N],ne[N],idx;
int f[N][3];
bool st[N];

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

void dfs(int u)
{
    f[u][2]=w[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][0]+=min(f[j][1],f[j][2]);
        f[u][2]+=min(min(f[j][0],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[j][2]+f[u][0]-min(f[j][1],f[j][2]));
    }
}

int main()
{
    cin>>n;

    memset(h,-1,sizeof h);

    for(int i=0;i<n;i++)
    {
        int id,cost,cnt;
        cin>>id>>cost>>cnt;
        w[id]=cost;
        while(cnt--)
        {
            int ver;
            cin>>ver;
            add(id,ver);
            st[ver]=true;
        }
    }

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

    dfs(root);

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

    return 0;
}