P2465 [SDOI2008] 山贼集团

某山贼集团在绿荫村拥有强大的势力。整个绿荫村由 $n$ 个连通的小村落组成，并且保证对于每两个小村落有且仅有一条简单路径相连。将小村落从 $1$ 至 $n$ 编号，山贼集团的总部设在编号为 $1$ 的小村落中。 山贼集团除了老大坐镇总部以外，其他的 $p$ 个部门希望在村落的其他地方（洛谷注：其实也包括总部）建立分部。$p$ 个分部可以在同一个小村落中建设，也可以分别建设在不同的小村落中，在不同的村落建设不同的分部需要花费不同的费用。 每个分部到总部的路径称为这个部门的管辖范围，于是这 $p$ 个分部的管辖范围可能重叠，或者完全相同。当多个分部管辖同一个村落时，他们之间可能发生矛盾，从而损失一部分利益，也可能相互合作，从而获取一部分利益。 请注意，如果相同的分部同时管辖多个村落，那么对于每个村落，都会计算一次收益损失/获取。 现在请你编写一个程序，确定 $p$ 个分部的位置，使得山贼集团能够获得最大的收益。

无

无

#### 样例输入输出 1 解释 在 $2$ 号节点建立 $1$ 号分部，花费为 $1$，则分部集合 $\{1\}$ 可以管辖 $1, 2$ 两个节点，根据第一条信息，该集合每管辖一个节点会产生 $3$ 的收益，因此总共产生了 $2 \times 3 = 6$ 的收益，减去建立分部的花费，最大的收益为 $6 - 1 = 5$。可以证明不存在更优的方案。 #### 数据规模与约定 对于 $40\%$ 的数据，保证 $1 \leq p \leq 6$。 对于 $100\%$ 的数据，保证： - $1 \leq p \leq 12$，$1 \leq n \leq 100$。 - $1 \leq s,t \leq n$，$1 \leq a_{i, j} \leq 10^8$。 - $1 \leq t \leq 2^p$，$1 \leq |v| \leq 10^8$，$1 \leq c \leq p$，$1 \leq x_i \leq p$ 且 $x_i$ 互不相同。 - 答案的绝对值不超过 $10^8$。