例4答案：+31防后怪物伤害仍然全为正，且目前怪物伤害之和低于勇士生命，因此限制条件E满足。（血瓶无用）
楼上图片为：初始点图，第一次合并坏点组，第二次合并坏点组
答案：10,12,13,14,7,8,9,15,6,1,2,3,4,5,11

四，树结构
此处与图论中的树定义相同。连通性我们默认他有，因此图中没有圈的结构称为树。易知八爪鱼结构是树结构的子集。下图加上了一点看起来复杂的结构，但实际上还是一棵树。（勇士在左下角）

根据树的性质，所有结点到勇士都只有一条路径，定义结点的距离为这条路径的长度。
结点A的后代结点指所有到勇士路径经过A的结点。
一个结点处的子树定义为它和它的所有后代结点形成的树。
结点A的子结点定义为所有到勇士路径经过A且距离比A大1的结点。
定义4：一个结点处的子树定义为“阳光树”，如果它的所有结点均满足：该结点的特征<=该结点的子结点的特征。（如果没有子节点，也算他满足）如果一个结点处的子树是阳光树，称这个节点为阳光结点。
显然，所有的叶结点（没有子节点的结点）都是阳光结点。如果一个节点是阳光结点，则他的所有后代节点都是阳光结点。
我们的目标是在不剪掉最优解的情况下，把一棵树变成阳光树。

定理5（阳光子结点连续定理）：如果一个结点A的所有子结点都是阳光结点，且节点A的特征是a，节点A的子树中特征最小点B的特征b<a，根据假设这个点一定是A的子结点（如果有好几个，至少有一个是），那么至少一个最优解打完A后立刻把这个点打掉。
证明：假设不是，最优解打完A后又打了一系列点，然后打B，把这串点的特征写出来形成一个数列，第一个数是a，最后一个数是b。
从第二个数开始，如果这个点不属于A的子树，染成红色，如果属于A的子树，染成蓝色。
最后一个b是蓝色。b前面那个如果是蓝色，则一定>=b，根据交换基本定理，b和前面那个交换更优或不变，由于B是A的子结点，这个交换可以进行。因此可以把b交换到前面是红色为止，还是最优解。故不妨假设b前面那个是红色。
数列中如果有连续的蓝色或者红色，我们把这个操作看成一个大操作，合并成一个点。（此处用到坏点组连续定理的技巧，大操作和这几个操作血量差一个固定值）这个数用那个合并操作的特征替代。
这样，a之后的数一定是红蓝相间。
注意到，a之后的数如果不是单调不减的，若有相邻的两数c>d,则c和d交换后更优。注意到c和d一个在子树里面，一个在子树外面，因此这样的交换是可以进行的，矛盾。
a后面那个数如果是蓝色，一定>=b，如果>b,但最后一个是b，与单调不减性矛盾。因此a后面所有数都是b。易知结点B的操作与前面所有操作可交换，故可以把B交换到A后面，还是最优解。
a后面那个数如果是红色，一定>=a,否则A与这个操作交换更优，矛盾。但是b<a,与单调不减性矛盾。

根据阳光子节点连续定理，若一个结点A不是阳光结点，但它的所有子结点都是了，那么打完A后一定要再打他的一个子结点B。我们可以把B合并到A里面，B的子结点变成A的子结点。（A的特征将变化）这样A的所有子结点也是阳光结点，如果A还不是阳光结点，可以继续操作。由于每次操作A的子树至少少掉一个点，若干次后A必然是阳光结点，且最优解未被剪掉。
一开始所有叶结点都是阳光结点。从勇士出发，如果这个点的所有子结点还有不是阳光节点的，则进入那个点，重复操作，一定会遇到一个点，它的所有子结点都是阳光结点。按照上述操作若干次这个点就会变成阳光结点。每次操作后非阳光结点个数减少1，若干次后必然会把勇士也变成阳光结点。
此时根据星型定理易知按照特征从小到大开始打即可。
定理6（树定理）：在限制条件E下，一个树结构中，为获得最优解，应当按照上一段描述的，将勇士变为阳光结点。这时，只需要按点的特征从小到大开始打就可以了。假如几个点特征相同，那么这几个点可以随便安排顺序。

定理6包括了星定理，八爪鱼定理，是一个比较强的定理。
我们再考虑能否将限制条件E放松一下。
定理7（大树定理）：一个树结构中，不管是否满足限制条件E，先按照定理6的方法得出一条路线，实际操作此路线，如果勇士没死，并且勇士打的怪物伤害为正或恰好为0（即少1防增伤*2=少2防增伤），则这就是最优路线。
这是本文的最强结果，定理7很显然，因为在没有限制条件E时，蓝宝石的减伤效果必定 <=W（见5楼）,而我们已得到W的最大值，并且确保这个值能达到，因此这必然是最优路线。
本文基本结束了，因为有圈的图太困难，我不知道怎么处理。有建议和想法欢迎留言！

例5解答：易知勇士不缺血，+38防御后其他怪物伤害还是正的，只有冥灵魔王是0，但是冥灵魔王后面有15防御，+23防御后其伤害还是正的，因此限制条件E满足。
答案：3,7,1,2,13,4,5,6,9,10,11,8,12

注：此理论虽是蓝宝石转换理论，对于只有绿宝石的塔显然一样适用。对于蓝绿宝石混合的塔，我暂时想不出什么处理手段。如果有想法可以留言。

发现前面的定义部分还是有一点不严谨，在把魔塔地图转变成图的地方……此外对于一般的图，可以用穷举生成树的办法得到最优解，但是计算量较大。有兴趣再更新吧

好久没更新了，更新一下吧！之前的文章中提到的算法不是最优的，worcher将此题改编为ACM黑龙江省赛题后发现了一个更优的算法，时间复杂度可以降低为O(nlgn)，n为结点个数。
我们计算完所有特征之后，直接观察最小点A，看看它是否有父亲。如果它没有父亲，我们取这个最小点,然后在剩下的树上重复操作。如果有父亲，由最小性，它的父亲B的特征>=A的特征。我们证明：在至少一条最优路径中，取了B之后，立即取A。
我们假设取B之后，进行了另一些操作C之后，再取A。则由A的最小性，C的平均特征>=A的特征。易证明：BAC不劣于BCA。因此得证。
因此我们直接把A并入B中。然后重复操作。这样纸笔算可以简化很多流程。下面证明这个算法的时间复杂度是O(nlgn)。
这里除了取最值之外的操作时间复杂度为O(n)。取动态最小值的时候，可以构造一个小根堆，把所有点放入堆之后，给每个点加上一个时间参数1。每次取堆顶就是最小数。如果有结点合并，把父亲加入小根堆，并给这个点的时间参数+1。（堆中可能有多个同一点，但时间参数不同。）每次取堆顶时，检查时间参数是否是最新，不是的话直接扔掉。易知结点个数<=n,每次删除或添加结点的时间复杂度都是O(lgn)。扔掉无效结点的次数不会超过n次，因为一个新节点被加入时才会增加一个无效结点，新结点被加入仅当合并结点，不会超过n次。取出最小结点的次数也不会超过n次，因此时间复杂度是O(nlgn)。感谢worcher提供的优秀算法!