题目大意
略
解题思路
n=1e5的数据规模肯定是不能直接枚举两个相连的点的。既然题目中用到了位运算，就要从二进制的角度来考虑。
对于一个连通分量，我们将其中的所有点按照权值排序，这时候再暴力枚举的话，肯定是最大的点和其他点分别来做与运算，然后次大的点和比它小的点做与运算。。。从位运算的角度思考，只有两个数相同二进制位上的数字都是1的时候，这位与运算的结果才是1，把每个数字按二进制位分解，然后按二进制位取前缀和，就能优化枚举的时间。
代码
const int maxn = 1e5+10;
const int maxm = 1e5+10;
vector<int> bcc[maxn];
int p[maxn], v[maxn], tmp[maxn], pre[maxn][32];
int n, m;
int find(int x) {
return p[x]==x? p[x]:p[x]=find(p[x]);
}
int main() {
int T; cin >> T;
while(T--) {
cin >> n >> m;
for (int i = 1; i<=n; ++i) scanf("%d", &v[i]), p[i] = i;
for (int i = 1, a, b; i<=m; ++i) {
scanf("%d%d", &a, &b);
p[find(a)] = find(b);
}
for (int i = 1; i<=n; ++i) bcc[find(i)].push_back(v[i]);
ll ans = 0;
for (int i = 1; i<=n; ++i)
if (bcc[i].size()>1) {
int tp = 1;
for (auto num : bcc[i]) tmp[tp++] = num;
sort(tmp+1, tmp+tp, greater<ll>());
for (int j = 1; j<tp; ++j)
for (int k = 0; k<=30; ++k) {
pre[j][k] = pre[j-1][k];
if (tmp[j]>>k&1) ++pre[j][k];
}
for (int j = 1; j<tp-1; ++j)
for (int k = 0; k<=30; ++k)
if (tmp[j]>>k&1) ans = (ans+tmp[j]*((1LL<<k)*(pre[tp-1][k]-pre[j][k])%MOD)%MOD)%MOD;
}
cout << ans << endl;
for (int i = 0; i<=n; ++i) bcc[i].clear();
}
return 0;
}