3638: 牛半仙的魔塔（增强版）(第三轮04)
题目描述
牛半仙的妹子被大魔王抓走了，牛半仙为了就他的妹子，前往攻打魔塔。 魔塔为一棵树，牛半仙初始在一号点。
牛半仙有攻击，防御，血量三个属性。
除一号点外每个点都有魔物防守，魔物也有攻击，防御，血量三个属性。 每个怪物后面都守着一些蓝宝石，获得 1 蓝宝石可增加 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 可以证明不存在更优的方案。
【数据范围】
对于 10%的数据:n ≤ 15，树
另有 10%的数据:n ≤ 10^5， 只存在边(1,i)
另有 10%的数据:n≤10^5， 只存在边(i − 1, i), (1, i) 另有 30%的数据:n≤10^3， 树
对于 100%的数据:n≤10^5， 树
对于 100%的数据：有牛半仙血量<5*1018,攻击=2000，盔甲防御=0。怪物血量为 3000~10^6，攻击 5×10^5 -7×10^5， 防御≤1000，打完一只怪后获得的蓝宝石数量 为 1 至 5。