考场自证了局部最优解就是全局最优解，但是总感觉哪里不太对，求大佬指正一下.

​ 定义：

点 $i$ 不分的代价为 $a_i$.

儿子数量为 $s_i$ ，儿子中的最大值 $S_i$.

$S_i\times s_i =A,S_j\times s_j = B$.

$S_i\times s_j=C,S_j\times s_i=D$.

证明：

对于点 $i$

• 分的价值为 $A$.

• 不分的价值为 $a_i$.

对于他的父亲 $f$ 的任意两个儿子 $i,j$，若 $i,j$ 的结果会互相影响.

那必定有一个是分，另一个是不分，令原先结果是 $i$ 分 $j$ 不分.

就有：

• $A < a_i$.

• $a_j < B$.

设 $S_i > S_j$ ，也就是分了的那边的最大值比较大，就有 $A>D,C>B$.

1. 假如合并后更好的选择是两个都分

就有 $S_i\times (s_i + s_j) < s_i\times S_i + a_j$.

即 $C<a_j$.

$\because C>B,B>a_j$.

$\therefore C>a_j$.

$\therefore$ 得出矛盾.

2. 假如合并后更好的是两个都不分

就有 $a_i+a_j <s_i\times S_i+a_j$.

即 $a_i<A$.

$\because A < a_i$.

$\therefore$ 得出矛盾.

设 $S_i < S_j$，也就是没分的那边的最大值比较大，就有 $A<D,C<B$.

1. 假如合并和更好的选择是两个都分.

就有 $S_j\times(s_i+s_j)<s_i\times S_i+a_j$.

即 $D+B<A+a_j$.

$\because a_j<B,A<D$.

$\therefore$ 得出矛盾.

2. 假如合并后更好的选择是连个都不分.

就有 $a_i+a_j<s_i\times S_i+a_j$.

即 $a_i<A$.

$\because A<a_i$.

$\therefore$ 得出矛盾.