回到这题。我们发现连通块的贡献独立，也就是说只要对每个连通块单独处理再求和就行了。
接下来我们关心单个连通块怎么做。由于题目让我们求的是所有 \(s\) 之和而不是三元组个数，故而考虑拆贡献（对每一位分别考虑）。之后，就可以沿用 CF845G 那题利用线性基来维护路径的思路来计数了。
假设当前处理到第 \(i\) 位、有 \(n_0\) 个 \(u\) 满足 \(dis_u[i]=1\)、有 \(n_1\) 个 \(u\) 满足 \(dis_u[i]=0\)（\(dis_u[i]\) 表示 \(dis_u\) 这个数二进制的第 \(i\) 位是多少）。那么我们根据组合常识不难求出以下值：
-
边权异或和的第 \(i\) 位为 \(0\) 的路径数（记为 \(p_0\)）。
根据 CF845G 那题中阐述的引理，对于一条路径 \(u\to v\) 的边权异或和，它等价于 \(dis_u\oplus dis_v\)。
于是它变成了找 \((dis_u\oplus dis_v)[i]=1\) 的点对数。
即 \(\frac{s(s-1)}{2}\)，其中 \(s\) 是当前连通块大小。
-
边权异或和的第 \(i\) 位为 \(1\) 的路径数（记为 \(p_1\)）。
即 \(n_0\times n_1\)。
当然也可以用容斥求得：\(\frac{n(n-1)}{2}-(\dbinom {p_0} 2+\dbinom {p_1} 2)\)。
接下来就可以直接统计答案了。分两种情况：
-
假设当前线性基内存在一个数，满足它的第 \(i\) 位为 \(1\)
钦定线性基大小为 \(sz\)，那么对答案的贡献为 \(p\times 2^{sz-1}\times 2^i\)。
其中 \(2^{sz-1}\) 那一项采用了一个经典的组合套路：我们在线性基中任意地取出一个第 \(i\) 位为 \(1\) 的元素。对于其它元素任意选（有 \(2^{sz-1}\) 种方案），而选出的元素则根据我们最终想得到的值来决定选不选。
-
不存在这样一个元素
显然只有那些 \((dis_u\oplus dis_v)[i]=1\) 的点对会在第 \(i\) 位产生贡献。此外，线性基中的每个元素选和不选都是合法的。
钦定线性基大小为 \(sz\)，那么贡献为 \(p_1\times 2^{sz}\times 2^{i}\)。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7, inv2 = 500000004;
struct E{int v; ll w;}; vector<E> e[N];
int n, m, sz, vis[N]; vector<ll> s;
ll ans, dis[N], sum, a[65];
void insert(ll x){
FR(i, 62, 0) if((x >> i) & 1){
if(!a[i]){sum |= a[i] = x; sz++; return;}
else x ^= a[i];
}
}
ll query(ll ret = 0){
FR(i, 62, 0){
ll n[2] = {0}, p1, p;
ll c = (1ll << i) % mod * ((1ll << sz) % mod) % mod;
for(const ll &x: s) n[(x >> i) & 1]++;
p1 = n[0] * n[1] % mod;
p = s.size() * (s.size() - 1ll) / 2 % mod;
if((sum >> i) & 1)
(ret += p * c % mod * inv2) %= mod;
else (ret += p1 * c) %= mod;
}
return ret;
}
void dfs(int u, int fa){
vis[u] = 1, s.emplace_back(dis[u]);
for(const auto &p: e[u]) if(p.v != fa){
if(!vis[p.v]) dis[p.v] = dis[u] ^ p.w, dfs(p.v, u);
else insert(dis[u] ^ dis[p.v] ^ p.w);
}
}
int main(){
scanf("%d%d", &n, &m);
FL(i, 1, m){
int u, v; ll w;
scanf("%d%d%lld", &u, &v, &w);
e[u].emplace_back((E){v, w});
e[v].emplace_back((E){u, w});
}
FL(i, 1, n) if(!vis[i]){
vector<ll>().swap(s);
fill(a, a + 63, 0ll), sum = sz = 0;
dfs(i, 0), ans = query(ans);
}
printf("%lld\n", ans);
return 0;
}