这是一家公司提出的编码问题：
给定一个具有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 （不确定此输出）
1 回答
如果权重不能为负数，那么最佳解决方案显然是切断一片叶子 . 假设总树重为 S ，我们可以在 O(n) 中找到它，如下所示：
2.对于每个顶点v，ans：= max（ans，abs（S - 2 * weight [v]））//剩余部分与叶子之间的差异
3.返回ans