这道题目的大意是这样的：在一个游戏中，有 N 个敌人等着我去杀掉（N ≤ 1000）；杀掉每个敌人所需的时间分别是 T_i；这 N 个敌人之间有父子关系，形成棵树，树的根节点是最终 Boss，一但杀掉他，游戏立即结束；在每一步中，我都可以任选一个敌人杀掉；一但有一个节点的两个儿子被杀掉，我的下一步就不能选择，必须立即杀掉该节点。问，游戏的时间最长可以持续多久。

    看似简单，但是开始做的时候，才发现有一些复杂的情况。比如，当一个节点被杀后，如果它的子树中还存在没有被杀掉的，可以全杀掉，以拖延整体的时间；对于任何一个节点，把它的儿子只杀掉一个，这不会迫使我必须杀掉它本身，而对于它的其它没有被杀的儿子，我还可以分别只杀掉它们的一个儿子，这也可以拖延时间；等等……

    分析到最后，应该有这三个状态：

• die_i：如果只杀以节点 i 为根的子树中的敌人，则 i 被杀的时间的最大值。
  
• noDie_i：如果只杀以节点 i 为根的子树中的敌人，则最长可以拖延多久，使 i 还活着，并且我下一步还可以自由选择。可见，在这个时间之后，如果我再杀掉该子树中的任何一个敌人，就会引起连锁反映，迫使我无法选择，最终必须在时间 die_i 杀掉 i。
• clear_i：如果只杀以节点 i 为根的子树中的敌人，则当我在时间 die_i 杀掉 i 之后，需要再花多少时间，把该子树中剩下的节点全杀光（其实就是所有剩下的节点的 T 值的总和）。
  

    最终要求的案答就是 die_Boss。

    对于一个节点 v，求 die_v、 noDie_v 和 clear_v 的过程分为以下三种情况：

    1. 如果 v 是叶节点，则 die_v = T_v， noDie_v = clear_v = 0。

    2. 如果 v 只有一个子节点 x，则 noDie_v = die_x + clear_x， die_v = noDie_v + T_v， clear_v = 0。

    3. 如果 v 有多个子节点，则：

• 先把每个子节点 i 的时间都拖延到 noDie_i 。此时，v 子节点都还活着，并且下一步我可以自由选择。记此时的时间为 sumNoDie。
• 选取一个子节点 i，花 kill_i = (die_i - noDie_i) + clear_i 的时间把 i 这棵子树全部清理掉。此时的时间是 sumNoDie + kill_i， v 的节点只死了一个，且下一步我还可以自由选择。在 v 的所有子节点中， sumNoDie + kill_i 的最大值就是 noDie_v。
• 清理掉一个子节点 i 之后，再选一个子节点 j，用 kill_j = die_j - noDie_j 的时间杀掉 j。此时， v 已经有两个儿子被杀，必须立即花 T_v 的时间杀掉 v，那么 v 死时间就是 sumNoDie + kill_i + kill_j + T_v。在所有选取 i、 j 的方案中， sumNoDie + kill_i + kill_j + T_v 的最大值就是 die_v。
• 最后求 clear_v。在确定了以上 i、 j 的最佳选取方案，并在时间 die_v 杀掉 v 之后，还需要花 clear_j 的时间清理子树 j，然后对于 v 的其它剩下的子节点 x，再分别花 (die_x - noDie_x) + clear_x 的时间把它们的子树都杀光。这些时间的总和就是 clear_v。