【每日一题】4月1日题目精讲 树型dp

题号 NC22598

名称 Rinne Loves Edges

来源 牛客小白月赛11

戳我进入往期每日一题汇总贴~

昨天的题似乎有点难，写题解的人都少了……今天来个简单一点的基础题。

注意备注里面说：M=N-1（读题一定要看备注！），题面说是个无向联通图，这就告诉我们实际上这就是一棵树。而题目中说到的度数为1的点实际上就的叶子节点。

现在问题就变成了：在以S为根的树上删掉权值和尽量小的一些边使得根和每一个叶子节点都不连通。

这是一个典型的树型dp，而树型dp本质上可以说是个搜索——遍历这棵树，在返回的时候维护相关的值。

不管是写dp还是写搜索其实都是要分析原问题和子问题分别是什么的，我们的原问题是以S为根的子树删掉权值和尽量小的一些边使得S和每一个叶子节点都不连通，那么子问题也很简单，就是求以x为根的子树删掉一些边使得S和x的子树上每个叶子节点都不连通。要想在考虑x这个点的子树的时候就实现子树上每个叶子都和S不连通，那么有两种情况：把x和他的儿子断开，或者是，在x的子树上去把所有叶子节点都断开。如果我们用f[x]表示x的子树上的所有叶子和根断开的最小代价的话， (y是x的儿子，dis[x] [y]是x到y的边长)。 dfs在返回的时候维护这些值就好。

注意f的初值——所有的叶子节点f值应为一个极大值。

代码可戳我查看~

活动奖励：

在牛客博客中写出题解，并回复地址

审核通过可获得10-50牛币（依据题目难度和题解的内容而定）