「Codechef」PRUNING-树形DP

发布于 26 天前  86 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codechef」PRUNING-树形DP

Description

给定一棵树,要求砍去边权总和最小的边,使得这分割出的每棵树满足:

在这棵树能找到一个点,使得其他点到它的距离 $\leq d$。

$n \leq 100, d \leq 10^7$

Solution

考虑如何合并两个合法的状态,肯定与这两个子树中最深的点有关。

设 $f_{i,j,k}$ 表示在原树中以$i$为根的子树,当前选定为根的节点是$j$,最深的节点是$k$的最小删除边权。

每次合并两个合法的状态得到新的合法状态即可。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codechef」PRUNING-树形DP


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!