UOJ Logo Universal Online Judge

UOJ

#370. 【UR #17】滑稽树上滑稽果

统计

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

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

他有 $n$ 个滑稽果,第 $i$ 个滑稽果的大小为 $a_i$。

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

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

滑稽树上滑稽果

输入格式

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

接下来一行有 $n$ 个正整数 $a_i$,表示 $i$ 个滑稽果的大小。

输出格式

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

样例一

input

5
12 9 14 17 15

output

10

样例二

input

10
42256 116359 103553 58560 49680 99204 37408 57353 110732 33797

output

328709

样例三

见样例数据下载。

限制与约定

子任务 分值 $n$的规模 $a_i$的规模 特殊性质
15$n \leq 9$$1 \leq a_i \leq 2 \times 10^5$
210$n \leq 12$保证存在合法的最优解是一条链
310$n \leq 100$保证存在合法的最优解是一条链。并且从根开始的每个滑稽值构成了一个序列,保证解的这个序列的字典序,在所有链对应的序列中最小
415$n \leq 10^5$
530$n \leq 100$
630$n \leq 10^5$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载