{"problem":{"name":"[UESTCPC 2024] 打字","description":{"content":"给定一颗 $n$ 个节点的 trie 树，以 $1$ 号节点为根，其余每个节点到父亲的边上都有一个字符，且父亲相同的节点到父亲的边上的字符互不相同。从根到每个节点的路径都代表一个单词，这个单词由路径上的字符顺序拼接而成。在每个节点 $i$ 处有一个权值 $c_i$，表示该节点所代表的单词需要写出的次数。 你有一个 cache，可以选择任意个单词放在 cache 里面。写单词时，每写一个字符需要花","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10333"},"statements":[{"statement_type":"Markdown","content":"给定一颗 $n$ 个节点的 trie 树，以 $1$ 号节点为根，其余每个节点到父亲的边上都有一个字符，且父亲相同的节点到父亲的边上的字符互不相同。从根到每个节点的路径都代表一个单词，这个单词由路径上的字符顺序拼接而成。在每个节点 $i$ 处有一个权值 $c_i$，表示该节点所代表的单词需要写出的次数。\n\n你有一个 cache，可以选择任意个单词放在 cache 里面。写单词时，每写一个字符需要花费 $a$ 的代价。当写出一个完整的单词时，就可以选择结束当前单词，转而拼写下一个单词。而 cache 会根据当前已经写出的字符，把 cache 中以这一部分字符为前缀且字典序最小的单词提示出来。此时你可以花费 $b$ 的代价直接写出这个单词，**并结束当前单词的拼写**，转而拼写下一个单词。注意一个字符串本身也看作它自己的前缀。\n\n求完成 trie 树上所有单词的拼写所需的最小代价。\n\n## Input\n\n第一行输入三个整数 $n,a,b$ $(1\\leq n\\leq 2\\times 10^5,0\\leq a,b\\leq 10^4)$，分别表示 trie 树的大小、写一个字符的代价和使用 cache 写出单词的代价。\n\n接下来 $n$ 行，其中第 $i$ 行首先输入两个整数 $c_i,k_i$ $(0\\leq c_i\\leq 10^4,0\\leq k_i<n)$，分别表示第 $i$ 个节点上的权值和第 $i$ 个节点的儿子节点的个数。接下来输入 $k_i$ 个整数 $son_{i,1},son_{i,2},\\ldots,son_{i,k_i}$，表示第 $i$ 个节点的儿子节点编号，按照第 $i$ 个节点到儿子节点的边上的字符之间的字典序从小到大依次给出。\n\n保证 $c_1=0$。\n\n## Output\n\n输出一行一个整数，表示完成 trie 树上所有单词的拼写所需的最小代价。\n\n[samples]\n\n## Note\n\n**【样例解释】**\n\n假设每个节点的子节点按字典序从小到大按 $a,b,\\ldots$ 编码。最优方案为将 $aa$ 放在 cache 中，于是 $aa$ 可以花费 $3\\times 4$\n的代价利用提示打出来，$a$ 和 $b$\n都直接打出来。总代价为 $3\\times 4+2\\times 1\\times 2+2\\times 1\\times 3=22$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10333","tags":["2024","O2优化","斜率优化","高校校赛"],"sample_group":[["4 2 3\n0 2 3 2\n3 0\n2 1 4\n4 0","22"]],"created_at":"2026-03-03 11:09:25"}}