原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：求一个最小值
1.2 题目背景、允许、禁止与限制
背景：有一个有 nnn 个结点的树
允许：放置尽可能低的保安花费，在结点 iii 放置保安需要花费一定金额并且可以使所有与结点 iii 相连的结点被看守
禁止：
限制：最后要使整棵树的每条点都会被看守
1.3 题目数据范围与猜测
1≤d,n≤1500⟶O(n2)1 \le d,n \le 1500 \longrightarrow O(n^2)1≤d,n≤1500⟶O(n2)
1.4 一句话概括题意
有一个树，在结点 iii 放置保安需要花费一定金额并且可以使所有与结点 iii 相连的结点被看守。最终求使整棵树的每个点都会被看守到的情况下需放置的最低保安花费
2 题目破题推导
2.1 第一步：分情况讨论
* 可以尝试让自己覆盖自己
* 可以尝试让儿子覆盖自己
那一个结点有多个儿子怎么办呢？一定是选择那个耗费最低的孩子
* 可以尝试让父亲覆盖自己
2.2 第二步：数学（如何选择耗费最低的孩子）
我们可以记录一个总价值，并且将差额也记录，最终选取最小的差额对总价值进行影响（代码中具体看）
3 模型匹配
提取关键词：
树+动态影响，是树形dp
4 具体方案
4.1 动态规划定义（重点）
首先，建立一个dp 数组
设置 dpi0{dp_i}_0dpi 0 代表用自己覆盖自己时的最小耗费
设置 dpi1{dp_i}_1dpi 1 代表用儿子覆盖自己时的最小耗费
设置 dpi2{dp_i}_2dpi 2 代表用父亲覆盖自己时的最小耗费
4.2 初始化
dpi0←ai{dp_i}_0 \leftarrow a_idpi 0 ←ai
dpi1←极大值{dp_i}_1 \leftarrow 极大值dpi 1 ←极大值
dpi2←0{dp_i}_2 \leftarrow 0dpi 2 ←0
4.3 状态转移方程
对于 dpi0{dp_i}_0dpi 0 我既然这一点已经覆盖了，就不需要再麻烦任何人了，那不用管了，与我相邻的子节点
dpi2{dp_i}_2dpi 2 只有可能从上一项的 j=0/1j=0/1j=0/1 转移过来，否则中间就会空出一个点（我自己不覆盖，孩子还得依靠我）
dpi1{dp_i}_1dpi 1 本质上可以先正常记录所有孩子最小值，然后额外记录一个最小差额；如果发现所有孩子都不选择的是 dpi0{dp_i}_0dpi 0 ，那就要让 dpi0{dp_i}_0dpi 0 差值最小的人强制变成 dpi0{dp_i}_0dpi 0
这里可能不太清楚，可以看代码中的第二个注释应该就比较容易明白了
5 最终代码（禁止抄袭，仅用于参考）
