当前没有测试数据。

星际导航 (navi)

题目描述

Y 同学正在指挥一场跨星系的物资传输任务。星系间的交通网络被构建为一棵拥有 $N$ 个节点的树形结构，其中 $1$ 号节点为中央指挥部（根节点）。每条星际航道（边）上都标注了一个传输频率（字符），且从同一个星站出发的所有航道对应的传输频率均互不相同。

从指挥部到任意星站 $i$ 的唯一路径编码 $S_i$ 是由路径上所有航道的频率按顺序拼接而成的字符串。在任务中，每个星站 $i$ 都有一个物资需求权重 $c_i$，代表该星站对应的路径编码 $S_i$ 需要被完整激活的次数。

激活一个路径编码有以下两种方式：

1. 手动校准：逐个激活编码中的字符，每激活一个字符需要消耗 $a$ 单位能量。
2. 全息导航：Y 同学可以预先在全球导航数据库 $\mathcal{F}$ 中存储若干个编码（可以是字典树中不存在的编码）。在校准过程中，若当前已手动激活的前缀为 $P$，且数据库 $\mathcal{F}$ 中存在以 $P$ 为前缀的编码，系统会自动锁定 $\mathcal{F}$ 中路径编码字典序最小的那个目标。此时，Y 同学可以花费 $b$ 单位能量直接完成该目标的激活。

注：一个编码本身也被视为其自身的前缀。

已知星际网络的结构、手动激活代价 $a$、导航激活代价 $b$ 以及各节点的物资需求权重 $c_i$。请你计算完成所有激活任务所需的最小总能量消耗。

输入格式

第一行包含三个整数 $N, a, b$，分别表示星站总数、手动激活单个字符的代价、以及使用全息导航的固定代价。

接下来 $N$ 行，按节点编号 $1 \sim N$ 依次给出每个节点的信息： 每行首先包含两个整数 $c_i, k_i$，分别表示节点 $i$ 的需求权重和该节点的子节点数量。 随后紧跟 $k_i$ 个整数 $son_{i,1}, son_{i,2}, \dots, son_{i,k_i}$，表示节点 $i$ 的所有子节点编号。这些子节点已按照其父边频率的字典序升序排列。

数据保证 $c_1 = 0$。

输出格式

输出一行一个整数，表示完成任务的最小总能量代价。

样例

样例输入 #1

4 2 3
0 2 3 2
3 0
2 1 4
4 0

样例输出 #1

22

数据范围与约定

对于 $100\%$ 的数据，满足 $1 \le N \le 2 \times 10^5$，$0 \le a, b \le 10^4$，$0 \le c_i \le 10^4$。

• 特殊性质 A：保证所有节点的子节点个数 $k_i \le 1$，即交通网络是一条链。
• 特殊性质 B：保证除了根节点外，其余所有节点的权重满足 $c_i = 1$。