algorithm - 树划分（基于算法）

Question

这是一家公司提出的编码问题：

给定一棵具有 N 个节点的树，并且给定与每个节点和边相关的权重（存在于树中）。您必须删除一条边，以使所创建的两棵树的权重之和之差最大。

输入：

第一行包含 N 个编号。节点的第二行包含 N 个整数，表示每个节点的权重，然后是 N-1 行显示存在的边缘。

输出：

创建树的最大权重差。

例子：

输入：

第一个测试用例：

3
8 7 8
10
21

输出：7

第二个测试用例：

9
5 5 4 1 8 8 3 5 2
10
20
31
41 
53 
60
75
81

输出：（13不确定这个输出）

Answer 1

如果权重不能为负，那么很明显最佳解决方案将是切掉一片叶子。假设树的总权重为S，我们可以在O(n)中找到它，如下所示：

1. ans := 0
2. 对于每个顶点v，ans := max ( ans , abs ( S - 2 * weight [ v ] )) // 剩余部分和叶子的区别
3. return ans