A6006 · 蓝宝石魔塔

题目描述

你在玩一个奇怪的魔塔，这个魔塔的设定是这样的： - 地图为一张 $n$ 个点，$n-1$ 条边的简单无向连通图； - 你初始在 $1$ 号点，该位置为空地，而其它的点要么有一个蓝宝石，要么有一个怪物； - 你初始具有 $A$ 点攻击和 $D$ 点防御，每个蓝宝石能够给你增加一定的防御； - 当你与怪物接触时会发生战斗，若怪物具有 $h$ 点生命、$a$ 点攻击和 $d$ 点防御，则你在此次战斗中会受到 $(\lceil\frac h{A-d}\rceil-1)\times(a-D)$ 点伤害。**注意：这个公式与一般的魔塔有所不同，当 $D>a$ 时该伤害应为负值而不是 $0$ ，相当于给你回复相应的生命值** - 当一个非空地节点的蓝宝石被吃掉或怪物被打败时，该节点也会变成空地； - 你可以沿着边在空地上任意穿梭，或从空地走向相连的蓝宝石节点或怪物节点并触发对应事件； - 当所有节点都变为空地时，游戏结束。 现在，你拥有无限的生命值，他想知道游戏结束时受到的伤害总和的最小值。

第一行：一个整数 $c$ ，表示测试点编号。特殊地，样例的测试点编号为 $0$ 。 第二行：三个整数 $n$ 、$A$ 、$D$ ，分别表示节点数目、初始攻击和初始防御。 接下来的 $n-1$ 行，每行两个整数 $x_i$ 和 $y_i$ ，表示 $x_i$ 和 $y_i$ 之间有一条无向边。保证给出的是一棵树。 接下来的 $n-1$ 行，每行若干个整数，分别表示 $2\sim n$ 号节点的类型。具体地： - 第一个数 $\text{opt}$ ，表示节点类型； - 若 $\text{opt}=1$ ，接下来输入一个整数 $v_i$ ，表示该点处有一个增加 $v_i$ 防御的蓝宝石；若 $\text{opt}=2$ ，接下来输入三个整数 $h_i$ 、$a_i$ 、$d_i$ ，表示该点处有一个 $h_i$ 生命、$a_i$ 攻击、$d_i$ 防御的怪物。

输出一行一个整数，表示最小伤害总和。

输入 #1

输出 #1

输入 #2

输出 #2