原题链接
1 题目
1.1 题目所需求出内容
对于本题,最终要求:一个最小值
1.2 题目背景、允许、禁止与限制
背景:
一棵树有 nnn 个点和一个给定的树根 rootrootroot
一条边 (a,b,c)(a,b,c)(a,b,c) 表示 a,ba,ba,b 两点间有一条边权为 ccc 的边
允许:
求割开这棵树的最小代价
> 割开一棵有根树:删除若干条边,使得任何叶子节点和根节点不连通
> 割一条边的代价就是这条边的边权
1.3 题目数据范围与猜测
n≤105,c≤106⟶O(n)n \le 10^5, c \le 10^6\longrightarrow O(n)n≤105,c≤106⟶O(n)
1.4 一句话概括题意
给定一棵有根树,求割开这棵树的最小代价
2 题目破题推导
2.1 第一步:分情况讨论
对于每个不为叶子节点的点,为了使其子孙中的叶子结点与根节点断开,有两种操作可选
* 让子树内部断
* 自己连着子树的这条边断
但是会引出一个问题:要是全程不断(因为这样无花费)怎么办
可以将初始不断的花费设置为 ∞\infty∞,这样不论如何总得断一条
3 模型匹配
比较简单的树形dp
主要:
* 排除叶子结点(没法转移)
* 根节点是给定的,而非 111
* 每个节点的所有子树断开代价要累加(每个子树是 max(子树若自身断开代价,子树与该点连接的那条边断开的代价)max(子树若自身断开代价,子树与该点连接的那条边断开的代价)max(子树若自身断开代价,子树与该点连接的那条边断开的代价))
4 最终代码(禁止抄袭,仅用于参考)