找到访问树的所有节点的最小成本
Find minimum cost to visit all nodes of a tree
给定树的根，其中每条边都有相关的成本。找到访问树的每个节点的最小成本。
我想到的递归解决方案是：
- 节点是叶子时的基本情况return 0.
- 对节点的每个 child c 递归计算成本。
- 将所有这些成本相加，并将边成本从节点添加到 child 两次（因为我们需要回溯）。
- 减去具有最大成本的 child 的边缘成本。（"greedy" - 我们不想从具有最大成本的 child 回溯）。
这种方法正确吗？
有没有更好的方法解决问题？
- 从一个节点访问所有子树，returns到该节点，会花费
edges * 2属于该子树的所有子树。
- 所以我们应该在树中找到一条路径成本最大的路径。我们只是通过路径，如果我们遇到一些不在路径中的节点，我们只是访问它并且returns。
所以路径中的边只会访问一次，剩下的边会访问两次。
- 如何找到成本最大的路径？既然是树，就可以递归的找。
答案应该是：
sum(cost(edge)*2) - sum(edge which in the path)
我检查了你的方案，我认为是错误的（如果我误解了你的方案，请发表评论）：
subtract the edge cost of the child that has maximum cost.("greedy" - we > don't want to backtrack from the child that has maximum cost).
那child会是一棵树，有些边必须访问两次。例如：
A
/ \
B C
/ \
D E
您不能一次访问该子树的所有边来访问所有节点。
1-除最后一个叶节点外，所有节点路径将被访问两次。
2-我们需要找出哪个叶节点访问根节点的附加成本最高。
3-一旦我们找到它，我们就需要进行遍历，使得这个叶节点是最后访问的节点。
给定树的根，其中每条边都有相关的成本。找到访问树的每个节点的最小成本。
我想到的递归解决方案是：
- 节点是叶子时的基本情况return 0.
- 对节点的每个 child c 递归计算成本。
- 将所有这些成本相加，并将边成本从节点添加到 child 两次（因为我们需要回溯）。
- 减去具有最大成本的 child 的边缘成本。（"greedy" - 我们不想从具有最大成本的 child 回溯）。
这种方法正确吗？
有没有更好的方法解决问题？
- 从一个节点访问所有子树，returns到该节点，会花费
edges * 2属于该子树的所有子树。 - 所以我们应该在树中找到一条路径成本最大的路径。我们只是通过路径，如果我们遇到一些不在路径中的节点，我们只是访问它并且returns。 所以路径中的边只会访问一次，剩下的边会访问两次。
- 如何找到成本最大的路径？既然是树，就可以递归的找。
答案应该是：
sum(cost(edge)*2) - sum(edge which in the path)
我检查了你的方案，我认为是错误的（如果我误解了你的方案，请发表评论）：
subtract the edge cost of the child that has maximum cost.("greedy" - we > don't want to backtrack from the child that has maximum cost).
那child会是一棵树，有些边必须访问两次。例如：
A
/ \
B C
/ \
D E
您不能一次访问该子树的所有边来访问所有节点。
1-除最后一个叶节点外，所有节点路径将被访问两次。
2-我们需要找出哪个叶节点访问根节点的附加成本最高。
3-一旦我们找到它，我们就需要进行遍历，使得这个叶节点是最后访问的节点。