【每日一题】4月1日题目精讲 树型dp
题号 NC22598
来源 牛客小白月赛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值应为一个极大值。
注意备注里面说：M=N-1（读题一定要看备注！），题面说是个无向联通图，这就告诉我们实际上这就是一棵树。而题目中说到的度数为1的点实际上就的叶子节点。
现在问题就变成了：在以S为根的树上删掉权值和尽量小的一些边使得根和每一个叶子节点都不连通。
这是一个典型的树型dp，而树型dp本质上可以说是个搜索——遍历这棵树，在返回的时候维护相关的值。
不管是写dp还是写搜索其实都是要分析原问题和子问题分别是什么的，我们的原问题是以S为根的子树删掉权值和尽量小的一些边使得S和每一个叶子节点都不连通，那么子问题也很简单，就是求以x为根的子树删掉一些边使得S和x的子树上每个叶子节点都不连通。要想在考虑x这个点的子树的时候就实现子树上每个叶子都和S不连通，那么有两种情况：把x和他的儿子断开，或者是，在x的子树上去把所有叶子节点都断开。如果我们用f[x]表示x的子树上的所有叶子和根断开的最小代价的话，
注意f的初值——所有的叶子节点f值应为一个极大值。
看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！
活动奖励：
在牛客博客中写出题解，并回复地址审核通过可获得10-50牛币（依据题目难度和题解的内容而定）
本道题目4月8日中午12：00之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴
投递阿里巴巴集团等公司10个岗位
查看13道真题和解析