P12669 「TFXOI Round 2」最小价值最大树

公元前 278 年的今天，伟大的诗人屈原投汨罗江自尽，距今已有 2303 年。 有一颗江边的树想要纪念他，所以请你来对这棵树做一些装饰。

有一个 $n$ 个点的树，点的编号从 $1$ 到 $n$。 第 $i$ 个点的点权是 $a_i$。 定义 $f(x,y) = x \land (x \oplus y)$。 定义 $all(i)$ 为点 $i$ 的所有能通过一条边到达的点的集合。 定义如下操作： > 先选定一个点 $i$，以及一个其直接连接的点集 $s \subseteq all(i)$。 然后，收益加上 $\sum\limits_{v\in s}f(a_i,a_v) - \sum\limits_{v\in all(i)}(a_v\land a_i)$。 然后，$a_i \leftarrow 0 $。 定义树的价值为对其执行任意次以上操作能获得的最大收益（假设一开始收益为 $0$，上述操作仅用于定义树的价值，不会真的执行）。 定义森林的价值为其中所有树的价值的总和**减去**附加代价，森林中的两个点属于同一棵树，当且仅当两个点之间存在一条路径连接。 一开始，附加代价等于 $0$。 你可以执行以下两种操作，其中第一种操作次数没有限制，第二种操作最多执行 $k$ 次： 1. 选定两个点 $u,v$，使得 $u,v$ 之间有直接连边，令 $x=a_u,y=a_v$，附加代价减去 $x+y$，然后将 $u,v$ 之间的边断开。 2. 选定一个点 $u$，将 $u$ 点删除，并断开 $u$ 连接的所有边。 答案为经过上述操作之后，题目给定的树形成的森林的最小价值。 你需要对于 $k \in [0,lim]$ 都计算出这个答案。 **注释一：$a \land b$ 的意思是 $a$ 和 $b$ 的按位与值**。 **注释二：$a \oplus b$ 的意思是 $a$ 和 $b$ 的按位异或值**。 **注释三：$a \leftarrow 0$ 的意思是将 $a$ 赋值为 $0$**。

无

无

本题样例水的有点过分，故在赛后提供数据生成器，可在附件下载，运行前需要先将 std.cpp 编译为名为 std 的可执行文件，以及使用 python 包管理器安装 cyaron 库。 **对于 C++ 语言，答案可能会超过 long long 范围，请使用 128 位整型，或者其他高精度**。 对于全部的数据：$0 \le lim \le n \le 2000$，$\forall i \in [1,n],0 \le a_i \le 2^{63}-1$，详细数据范围见下表。 | Subtask 编号 | 特殊限制 | 分值 | | :----------: | :--------------: | :----:| | #1 | $lim=0,n\le 10$ | $10$ | | #2 | $lim=0,n \le 20$ | $15$ | | #3 | $lim=0$ | $20$ | | #4 | $n\le 6$ | $15$ | | #5 | $n \le 100$ | $30$ | | #6 | 无 | $10$ |