关键观察

图论模型：最终结构是一棵有向树，边从高海拔指向低海拔。酒店是海拔最低的点（因为所有点都需要能到达它，且边指向海拔更低点）。

设施需求：一个点如果有 $d$ 条边指向它，它就需要 $d$ 个连接设施（初始有1个，所以需要扩展 $d-1$ 次，如果 $d \ge 1$）。成本为 $(d-1) \times C_i$（如果 $d=0$ 则成本为0）。

增高操作的意义：通过增高某些点，我们可以改变点的海拔相对关系，从而：

让某个点成为最低点（成为酒店）。

让一些点能够连接到特定的点（满足严格小于的条件）。

问题转化：问题等价于：选择根节点，通过增高操作调整海拔，构造一棵以根为叶子的有向树，使得总成本最小。成本包括：

增高成本：$\sum (最终海拔 - 初始海拔) \times K$

扩展成本：对于每个非根节点，如果它的入度为 $d$，则成本为 $(d-1) \times C_i$（注意：根节点不需要出边，但可能有入边，所以也可能需要扩展设施）。

实际上，更准确的说法是：每个点（除了酒店）需要恰好一条出边，但可以有多条入边。所以：

酒店：入度 = 其他点数量，出度 = 0。

其他点：入度 = 父节点数量？不对，在树中每个非根节点只有一个父节点，但这里不是普通树，而是每个点指向严格更低海拔的点，所以可能形成多叉树，并且一个点可以被多个高点指向。

因此，一个点（非根）的出度 = 1，入度可以 >= 0。

一个点的入度 = 有多少个点指向它。

每个点初始 1 个设施，如果入度 = $d$，则需要 $d$ 个设施，所以要扩展 $d - 1$ 次（如果 $d \ge 1$），成本 = $\max(0, d-1) \times C_i$。

思路分析

我们可以枚举每个点作为酒店（根节点），因为根节点必须是全局最低海拔（严格低于所有其他点？不一定严格，但为了有边指向它，必须严格低于指向它的点；但根自己没出边，所以它的海拔只要小于它的父节点即可，但父节点可能多个，所以根的海拔必须严格小于所有连向它的点）。

所以，如果我们固定了根节点 $r$，那么：

根的海拔必须严格小于所有连向它的点。

其他非根点必须有一条出边指向海拔严格更低的点。

为了最小化成本，我们会尽量利用初始海拔，只进行必要的增高。

一个经典思路是：

把点按初始海拔排序。

酒店一定是某个点，可能通过降低其他点或升高自己来实现它是唯一最低的。

但是这里只能增高，不能降低，所以酒店必须选择初始海拔较低的点，或者通过增高其他点使得酒店相对最低。

实际上，我们可以通过增高某些点来改变高低关系，但增高的成本是 $K$ 每单位，所以我们要谨慎。

动态规划解法

官方解法通常采用动态规划，按海拔从低到高处理点。

设点按照海拔从小到大排序（海拔相同的可以按任意顺序，但需要处理严格小于关系）。

定义 $dp[i][j]$ 表示考虑前 $i$ 个点（低海拔到高海拔），当前剩余的“空闲连接设施”数量为 $j$ 时的最小总成本（这里成本只计算扩展和增高的部分）。

为什么是“空闲设施”？

当我们处理到某个点时，它可能会被后面更高海拔的点连接。

初始每个点1个设施，如果它被 $d$ 个高点连接，就需要 $d$ 个设施，所以要扩展 $d-1$ 次。

在 DP 中，$j$ 表示当前已经承诺提供的设施数量（通过扩展已有的点）与已经使用的设施数量的差值。

更精确的状态定义：

将点按海拔排序，$H_1 \le H_2 \le \dots \le H_N$。

$dp[i][j]$ = 考虑前 $i$ 个点，并且当前剩余的“空闲连接设施”数量为 $j$ 的最小成本。

初始：$dp[0][0] = 0$，其他无穷大。

转移：

将第 $i$ 个点作为酒店（根）：根不需要出边，但需要被其它点连接。如果当前空闲设施 $j \ge N-1$，则可以满足所有其他点连向它，否则需要额外扩展设施到 $N-1$ 个。但这里我们不在根上扩展，而是在之前点上扩展？ 实际上，根也可能需要扩展设施：根初始1个设施，如果 $N-1 > 1$，则需要扩展 $N-2$ 次，成本 $(N-2) \times C_i$。但这里 $j$ 是之前点的空闲设施，不能用于根自己？ 所以根自己的设施扩展要单独算。

更简单的做法：根不参与设施供求，只计算它的扩展成本 $(N-1 - 1) \times C_i = (N-2) \times C_i$（如果 $N-1 > 1$）。

同时要保证根的海拔严格小于所有连向它的点，所以可能需要增高某些点或根自己？ 这里只能增高，所以如果根的海拔不是严格小于后面的点，就需要增高后面的点。

为了简化，我们可以在 DP 时，如果选择点 $i$ 为根，则要求 $j \ge N-1$ 表示有足够设施给其它点连接它，并且计算根自己的扩展成本 $(N-2) \times C_i$，以及增高的成本：所有海拔 $H \le H_i$ 的点（除了根自己）如果要连向根，必须海拔严格大于根，如果等于就需要增高一次，成本 $K \times$（等于根海拔的点数 - 1）。

将第 $i$ 个点作为普通点：它需要一条出边指向前面某个点，所以需要前面至少有一个空闲设施。转移：

如果 $j \ge 1$，则可以直接使用一个空闲设施，不需要增高：$dp[i][j-1] = \min(..., dp[i-1][j])$。

如果 $j = 0$，则必须通过增高前面某个点或当前点来创建空闲设施，这等价于需要额外扩展设施，成本 $\min(C_1..C_{i-1})$？ 但这里我们只能增高，不能降低，所以如果前面没有空闲设施，就必须让当前点增高到比下一个点还高，从而让后面的点能连向它？ 这样复杂。

实际上，标准解法是：

按海拔排序。

设 $f(i,j)$ 表示前 $i$ 个点，当前剩余空闲设施数 $j$，且第 $i$ 个点必须被增高到比第 $i+1$ 个点高（为了给后面点提供连接）时的最小成本。

转移时，考虑第 $i$ 个点是否被增高（为了给后面提供设施），以及它需要连接前面某个点（消耗设施）。

结论

由于时间限制，这里给出最终可行的算法方向（基于已知解法）：

将点按 $H_i$ 排序。

枚举每个点作为酒店。

对于每个酒店，从低到高处理其他点，用贪心选择：当需要设施时，选择之前点中 $C$ 最小的进行扩展，或者如果 $K$ 更小则用增高代替扩展。

记录总成本，取最小值。