解题思路
\(\qquad\) 题目就不再复述了，我们这题和上一题类似，可以采用树形DP + 状态机
状态表示
\[f[i][j], j\in[0,2]表示的是第 i 个点，第 j 种状态 \]对于三种状态，有如下分类
\[f[i][0]表示的是不选当前节点，但是选择了父节点 \]\[f[i][1]表示的是不选当前节点，但是选择了子节点 \]\[f[i][2]表示的是选择当前节点 \]状态转移
\(\qquad\)首先看\(f[i][0]\)，假设 \(j\) 是 \(i\) 的一个子节点，\(i\) 并没有选择，所以 \(f[j][0]\) 这个状态是无法转移到 \(f[i][0]\) 的（\(i\) 就是 \(j\) 的父亲， \(i\) 都不选自己，那就是不选 \(j\) 的父亲）。所以 \(j\) 只能自给自足或者选择自己的儿子，因此：
\[\large f[i][0] = \sum_{j\in son[i]} \min\{f[j][1], f[j][2]\} \]\(\qquad\)接下来要考虑的是 \(f[i][1]\)，因为这个状态需要整颗子树的信息，所以放到后面处理
\(\qquad\) 对于 \(f[i][2]\)，因为 \(i\) 已经选择了自己，所以不管子节点怎么样，都是合法的，因此可以由子节点的三种状态转移而来
\[\large f[i][2] = \sum_{j\in son[i]} \min\{f[j][1], f[j][2], f[j][0]\} \]\(\qquad\) 问题回到了 \(f[i][1]\)的身上，我们可以进行如下分析：
\(\qquad\) 枚举 \(i\) 的所有子节点 \(j\)，假设 \(j\) 是我们最终要选择的子节点，那么如果是选了这个儿子，其它儿子仍然是没有被父亲选的，所以其它儿子的代价也要加上，也就是总和去掉 \(f[j][2]\)，因为前面有类似的情况 \(f[i][0]\) 已经保存了总和，那这里就不用另外处理了。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1510;
int h[N], e[N], ne[N], w[N], idx;
int st[N], root, n, 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][1] = 1e9, 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]); //同时用作sum
f[u][2] += min({f[j][1], f[j][0], f[j][2]});
}
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
f[u][1] = min(f[u][1], f[u][0] + f[j][2] - min(f[j][1], f[j][2]));
}
}
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
int id, m, r, c;
scanf("%d%d%d", &id, &c, &m);
w[id] = c;
while (m -- )
{
scanf("%d", &r);
add(id, r);
st[r] = 1;
}
}
root = 1;
while (st[root]) root ++ ;
dfs(root);
printf("%d\n", min(f[root][1], f[root][2]));
return 0;
}