题解

思路

一个快速拨号串只有作为某个电话号码的前缀时才可能有用，而且可把它缩短到字典树中的某个节点而不变差。因此将全部号码插入十叉字典树。根节点表示不使用快速拨号，深度是已经自动输入的数字个数；终止节点的权值是对应号码每天的拨打次数之和。

若终止节点 $x$ 最近的已选祖先为 $p$，它的贡献是

问题转化为：在字典树上选至多 $k$ 个节点，使所有带权终止节点到最近已选祖先的加权距离和最小。根节点视为免费选中。

做法

子任务 1 枚举字典树节点的所有至多 $k$ 元子集。对每个集合，从每个终止节点向上找到第一个被选祖先并计算代价。

子任务 2 中 $k=1$。不选快速拨号时的总代价为 $\sum_x m_x\operatorname{dep}(x)$。若唯一按键绑定在节点 $u$，其子树中所有号码各节省 $\operatorname{dep}(u)$ 次数字键，因此只需计算每个节点的子树权值和，取 $\operatorname{dep}(u)\cdot W_u$ 的最大值。

满分算法设 $F(u,p,b)$ 为处理 $u$ 的整棵子树、最近的已选严格祖先为 $p$、还可选至多 $b$ 个节点时的最小代价。

• 不选择 $u$：节点自身贡献为 $m_u(\operatorname{dep}(u)-\operatorname{dep}(p))$，把 $b$ 个名额用树上背包分配给各个孩子，孩子状态仍以 $p$ 为最近已选祖先。
• 选择 $u$：消耗一个名额，节点自身贡献为零，再把剩余名额分配给孩子，且孩子状态的最近已选祖先改为 $u$。

两种方案取最小。根节点免费视为已选，只执行孩子合并即可。

复杂度

令字典树节点数为 $V\le501$。子任务 1 的时间复杂度为 $O(2^V\cdot V)$，只在 $V\le16$ 时使用；子任务 2 为 $O(V)$。满分算法只有祖先对 $(u,p)$ 会形成状态，结合至多 $10$ 个名额的树上背包，时间复杂度为 $O(V^2k^2)$，空间复杂度为 $O(V^2k)$。

正确性证明

任意有用的快速拨号串都是某些号码的公共前缀，对应字典树节点。固定最近已选祖先后，某个节点是否被选择只有上述两种互斥情形；选择结果对不同孩子子树的影响仅是可用名额的分配，树上背包枚举了所有分配。由子树大小归纳，$F$ 对每个状态取到其完整可行域内的最小代价。根节点代表完全用数字键输入且不占名额，所以根状态即原问题最优解。