$n leq 1e5$个点，每个点有个权值$a_i leq 2e5$。现将点连成树，每个点$i$的链接代价为$a_i and i父亲的代价$，这里的$and$是二进制按位与，求最小总代价。
日常被坑。。。
首先肯定是要把这些点连成一条链，尽量使得代价andand就and成0了。然后呢。。。
方法一：贪心，从小到大排。错误！
5
56499 113007 129845 126701 56282
一组错误数据。
方法二：这个想法还是可以有的，俗话说，贪心不成就DP。看一下那些二进制位化成0的代价。
首先有些位上永远是1，先把这些位提出来，其他位做一个DP，$f(i)$表示集合$i$变成0的代价。
如果直接枚举$a_i$来转移就傻了。。枚举$a_i$转移不如去枚举$i$的子集，对每个状态预处理出是否存在一个数$a_j$，使得$i and a_j=0$.这样在算$i$的答案时，我们就知道$i$的每个子集是否可以通过$and$某个数直接挂掉，然后剩下一个补集，带来一个补集的代价。
1 //#include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 //#include<vector> 6 //#include<queue> 7 //#include<time.h> 8 //#include<complex> 9 #include<algorithm> 10 #include<stdlib.h> 11 using namespace std; 12 13 int n; 14 #define maxn 262222 15 int a[maxn],f[maxn]; 16 bool can[maxn]; 17 int main() 18 { 19 scanf("%d",&n); 20 int ss=(1<<18)-1,tt=0; 21 for (int i=1;i<=n;i++) scanf("%d",&a[i]),ss&=a[i],tt|=a[i]; 22 for (int i=1;i<=n;i++) can[a[i]^tt]=1; 23 tt^=ss; 24 for (int i=tt;i;i--) 25 for (int j=0;j<=18;j++) 26 can[i]|=can[i|(1<<j)]; 27 f[0]=0; 28 for (int i=1;i<=tt;i++) 29 { 30 if ((i&tt)!=i) continue; 31 f[i]=0x3f3f3f3f; 32 for (int j=i;;j=(j-1)&i) {if (can[i^j]) f[i]=min(f[i],f[j]+j); if (j==0) break;} 33 } 34 printf("%lld ",1ll*ss*n+f[tt]); 35 return 0; 36 }