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