3614: 牛半仙的魔塔(第三轮04)
题目描述
牛半仙的妹子被大魔王抓走了，牛半仙为了就他的妹子，前往攻打魔塔。 魔塔为一棵树，牛半仙初始在一号点。
牛半仙有攻击，血量两个属性，并且牛半仙有一套盔甲，会为他增加防御。
除一号点外每个点都有魔物防守，魔物也有攻击，血量两个属性，并且魔物皮糙 肉厚，有一定的防御。
每打死一个魔物后牛半仙会获得一些经验，并且升级，每升一级牛半仙的盔甲能 增加 1 的防御。
牛半仙具有突袭属性，所以遇到魔物后会率先发动攻击，然后牛半仙和魔物轮换 地攻击对方。
一个角色被攻击一次减少的血量是对方的攻击减去自己的防御。 当一个角色的血量小于等于 0 时，他就会死亡。
当牛半仙第一次到达某个节点时会与这个节点的魔物发生战斗。
当一个魔物死亡后，这个魔物所在的节点就不会再产生新的魔物。 现在牛半仙想知道他打死魔塔的所有魔物后的最大血量。
输入
第一行一个 n 代表节点数。
随后 n − 1行，每行两个数 i,j，表示 i 与 j 节点有边相连。
随后一行，三个数，依次为勇士的血量、攻击、盔甲的防御。
随后 n − 1 行，每行四个数，依次为怪物的血量、攻击、防御， 和打完怪后提升 的等级。
输出
一个数，代表最大血量。如果牛半仙在打死魔塔的所有魔物之前血量就已经死亡 了，则输出-1。
样例输入 复制
6
1 2
1 3
1 4
4 5
5 6
50000 10 0
35 54 2 4
25 55 3 5
21 51 4 5
20 64 5 3
43 64 6 1样例输出 复制
48901提示
样例 1 说明】
打怪的顺序依次为 4， 3， 5， 2， 6 可以证明不存在更优的方案。
【数据范围】
对于 20%的数据：n ≤ 15。
又有 30%的数据：n ≤ 1000，且保证对于每一条边 (i,j)， 一定满足 i = 1。
对于前 90%的数据：n ≤ 1000，且保证对于每一条边(i,j)，一定满足 j = i + 1 或 i = 1。
对于最后 10%的数据：n ≤ 100000，且保证对于每一条边(i,j)，一定满足 j = i +1 或 i = 1 。
对于 100%的数据：有王半仙血量=1018，攻击=2000，盔甲防御=0。怪物血量为 3000~106，攻击 5×105 -7×10^5，防御≤ 1000，打完一只怪后提升的等级为 1~5。