首页 > 杀树
开通博客写题解
头像 sunrise__sunrise
发表于 2020-05-02 11:32:54
D、杀树 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 牛牛学习了树。 给出一棵节点数为 n 的树，删去一个点 i 的代价为 ，一条链的长度定义为路径上 点 的个 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 18duangduang
发表于 2020-05-02 12:22:59
题意：给定一棵树,第i个结点有 权值,删除一些结点的代价是删除结点的权值和,求满足树上任何一条链长度小于等于l的删除方案代价最小.(n<=5000, <=5000 )分析: 从n的范围可以知道复杂度可以是n^2,那么可以搞树形二维dp. 表示以第i个结点为根节点的子树满足最长链小于等于 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 兰陵大大
发表于 2020-05-02 16:35:59
这到题目需要的知识点是最短路和dp的知识点，之后返回来再进行修改吧https://ac.nowcoder.com/acm/contest/5389/D
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”