【UR #17】滑稽树上滑稽果 - 题目

“滑稽树上滑稽果，滑稽树下你和我” 听到这熟悉的句子，他猛然忆起年少时最喜欢的节目，彼时单纯而简单的生活，以及那幼稚而天真的苦恼。

幼年的他常常苦恼这么一个问题：

他有 $n$ 个滑稽果，第 $i$ 个滑稽果的大小为 $a_{i}$ 。

他现在想把它们构成一棵任意形态的有根树，每个点的滑稽度为它的大小和它父亲的滑稽度的 $and$ ，其中 $and$ 表示按位与运算，例如 $2 and 3 = 2 ， 1 and 0 = 0 ， 1 and 1 = 1$ 。特别地，根的滑稽度等于他的大小。

为了世界的和平，他希望能最小化这棵树上所有滑稽果的滑稽度之和。请问你能帮他解决这个问题吗？

滑稽树上滑稽果

第一行一个正整数 $n$ 。

接下来一行有 $n$ 个正整数 $a_{i}$ ，表示 $i$ 个滑稽果的大小。

一行一个整数，表示最小的滑稽度之和。

5
12 9 14 17 15

10
42256 116359 103553 58560 49680 99204 37408 57353 110732 33797

见样例数据下载。

子任务	分值	$n$ 的规模	$a_{i}$ 的规模	特殊性质
1	5	$n \leq 9$	$1 \leq a_{i} \leq 2 \times 10^{5}$	无
2	10	$n \leq 12$		保证存在合法的最优解是一条链
3	10	$n \leq 100$		保证存在合法的最优解是一条链。并且从根开始的每个滑稽值构成了一个序列，保证解的这个序列的字典序，在所有链对应的序列中最小
4	15	$n \leq 10^{5}$
5	30	$n \leq 100$		无
6	30	$n \leq 10^{5}$		无

时间限制： $1 s$

空间限制： $256 MB$

Universal Online Judge