某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有n个节点，编号分别为1、2、3、..... n。 为了实时记录道路情况，需要在某些节点部署监控设备，当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。 给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到的最少花费是多少？ 例如：n=8，表示有8个节点(即道路交叉点或端点)，1到8号节点部署监控设备的费用分别为33、12、30、22、18、10、31、28。道路分布图如下： 根据观察可得，在2号和3号节点处部署监控设备，可以使所有道路都 能被监控到，并且花费最少，最少花费为42。 输入格式 第一行输入一个整数n (2≤n≤104)，表示城市中节点(即道路交叉点或端点)的数量； 第二行输入n个整数(1<整数≤105) ，分别表示1号到n号节点部署监控设备的费用； 接下来n-1行，每行输入两个整数a, b,表示节点a和节点b之间有一条道路。 输出格式 输出一个整数，表示要使所有道路均能被监控到的最少花费。 输入样例 8 33 12 30 22 18 10 31 28 1 2 1 3 2 4 2 5 2 6 3 7 3 8 输出样例 42
正确答案：树上加权最小边覆盖(顶点覆盖)。树形DP三态：dp[u][0]=选u(含cost[u])，dp[u][1]=不选u由孩子覆盖，dp[u][2]=不选u由父亲覆盖。dp[u][0]=cost[u]+sum(min(dp[v][0],dp[v][1]));dp[u][1]=sum(dp[v][0]);dp[u][2]=sum(min(dp[v][0],dp[v][2]))。根取min(dp[1][0],dp[1][1])。
试卷来源：202409(第15届)蓝桥杯C++编程青少组(国赛_中高级)真题