ps：今天真是石乐志，改了一下午bug，结果是忘了排序。。。。。。。。。。这题姿势较多，坑点就一个。
题解：有个结论，任意两点之间如果至多存在两条不相交路径，那么每一条边至多出现在一个环中（very important !）。如果一个s - t割要割掉某个环中的边，那么割掉的边顶多只能是两条，且这个环中最小容量的边一定会被割掉。所以我们可以割掉每个环中的最小容量边，并把其容量加到这个环中的其它边上。这样并不会影响任意两点间的最大流，且把图降为一棵树，而最大流也简化成了两点之间路径上的容量最小的。考虑将容量按降序插入空树中，那么当前要加的边必然是两个联通块A,B的最小割，话句话说，割掉这条边，A，B集合中的点一定不联通，所以这条边的容量就是 u - v 的最大流（u ∈ A， v∈B）。位运算一般都要考虑二进制，算每一位的贡献，所以枚举权重就好了。注意爆long long
#include<bits/stdc++.h> #define ull unsigned long long #define ll long long #define P pair<int, int> #define pb push_back #define mp make_pair #define pp pop_back #define lson root << 1 #define INF (int)2e9 + 7 #define rson root << 1 | 1 #define LINF (unsigned long long int)1e18 #define sc(x) scanf("%d", &x) #define pr(x) printf("%d\n", x) #define mem(arry, in) memset(arry, in, sizeof(arry)) using namespace std;inline void upd(int &x, int y) {x < y && (x = y); }const int N = 300005;ull ans, cnt[N][32][2]; int T, n, m, dep[N], pa[N], fa[N], id[N]; bool use[N];struct mode { int u, v, w; } eg[N], sg[N];inline bool cmp(mode& a, mode& b) {return a.w > b.w; }int getFa(int a) {return (a == fa[a] ? a : fa[a] = getFa(fa[a])); }bool Union(int a, int b) {int x = getFa(a);int y = getFa(b);if (x != y) {fa[x] = y;return true;}return false; }vector<P> g[N];void Inite() {for (int i = 1; i <= n; ++i) {g[i].clear();for (int j = 0; j < 32; ++j) {cnt[i][j][0] = ((i >> j) & 1) ^ 1;cnt[i][j][1] = ((i >> j) & 1);}} }void DFS(int u, int p) {pa[u] = p;for (auto v : g[u]) if (p != v.first) {id[v.first] = v.second;dep[v.first] = dep[u] + 1;DFS(v.first, u);} }void change(int u, int v, int w) {if (u == v) return;if (dep[u] < dep[v]) swap(u, v);while (dep[u] != dep[v]) {eg[id[u]].w += w;u = pa[u];}while (u != v) {eg[id[u]].w += w, eg[id[v]].w += w;u = pa[u], v = pa[v];} }void compute(int u, int v, int w) {u = getFa(u);v = getFa(v);for (ull i = 0; i < 31; ++i) {if (w & (1ull << i)) {ans += cnt[u][i][0] * cnt[v][i][0] * (1ull << i);ans += cnt[u][i][1] * cnt[v][i][1] * (1ull << i);}else {ans += cnt[u][i][0] * cnt[v][i][1] * (1ull << i);ans += cnt[u][i][1] * cnt[v][i][0] * (1ull << i);}}fa[u] = v;for (int i = 0; i < 31; ++i) {cnt[v][i][0] += cnt[u][i][0];cnt[v][i][1] += cnt[u][i][1];} }int main() {//freopen("D:\\1001.in","r",stdin);//freopen("D:\\1.txt","w",stdout); sc(T);while (T--) {sc(n), sc(m);Inite();for (int i = 1; i <= m; ++i) {use[i] = 0;scanf("%d %d %d", &eg[i].u, &eg[i].v, &eg[i].w);}sort(eg + 1, eg + m + 1, cmp);for (int i = 1; i <= n; ++i) fa[i] = i;for (int i = 1; i <= m; ++i) if (Union(eg[i].u, eg[i].v)) {use[i] = 1;g[eg[i].u].pb(P(eg[i].v, i));g[eg[i].v].pb(P(eg[i].u, i));}dep[1] = 0;DFS(1, -1);for (int i = 1; i <= m; ++i) if (!use[i]) change(eg[i].u, eg[i].v, eg[i].w);int tot = 0;for (int i = 1; i <= m; ++i) if (use[i]) sg[++tot] = eg[i];sort(sg + 1, sg + tot + 1, cmp); // 一定要重排一道，因为边的权重发生了变化，WA了一下午 ans = 0;for (int i = 1; i <= n; ++i) fa[i] = i;for (int i = 1; i <= tot; ++i) compute(sg[i].u, sg[i].v, sg[i].w);printf("%llu\n", ans);}return 0; }
