首页 > 货物收集
开通博客写题解
头像 白菜茄子
发表于 2020-03-12 17:16:01
题目网址：https://ac.nowcoder.com/acm/problem/54148 题目描述： Venn想要收集一些货物。Venn有一颗n个节点的树，一开始Venn在1号节点，其他每个节点都有一定的货物储备，Venn只要经过那些节点，就可以收集到节点的所有货物。每个节点的货物只能收集一次。 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 DXD99
发表于 2023-05-05 11:20:03
这道题可以使用二分法+DFS来解决。可以二分答案 midmidmid，表示 Venn 最少需要多少武力值才能收集到至少 WWW 个货物。 具体做法是，我们首先遍历整棵树，计算出每个点向下子树（不包括父亲节点）的货物储备之和。然后从根节点开始 DFS，维护一个父节点fafafa表示当前已经经过的点，以 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”