传送门

这道题真的是坑，竟然用ull，ll都会爆。

首先这是一个仙人掌图。题意让求任意两点最大流，再进行异或。先说最大流，对于环上任意两点最大流，就是两条路径最小的边和，这就等效于求出环中最小的边，使环上任意一条边都加上这条边，然后去掉最小边。这样会求出一棵树。我们将边按从大到小排序，每次向空图里加一条边（用并查集维护），那么加的这条边就是两个连通分量的最大流。

还是老方法。对于仙人掌图，（可以看这里），跑一边tarjan。对于树边，直接将他放入边集里，对于环，写一个函数单独处理，去掉环中最小边，加到其他边上去。将其他边加入边集（细节在代码中注释）。

最后就是 计算异或值得问题。本来应该是n^2，枚举两个连通分量的值，但由于n太大，由于w是32位，我们可以枚举每一位，看两个联通分量中这一位有多少个0和1，能够使答案异或为1的组合的数量，就对答案贡献了多少这一位的权值。

最后注意ull

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10;struct Edg{int u, v, nxt;ll w;
}e[N<<1], edg[N<<2], tmp[N<<1];int n, m, dfs_clock, dfn[N], low[N], head[N], cn, cnt;
int f[N], fa[N], pos[N];//pos是用来记录该点对应的那条边，这个点是这条边的指向。ull ans;
ll c[N][40][2];int _find(int x){return f[x]==x?x:f[x]=_find(f[x]);
}void init(){dfs_clock=0;cn=0; cnt=0; ans=0;for(int i=1; i<=n; i++){head[i]=-1, dfn[i]=0;f[i]=i;for(int j=0; j<=30; j++){c[i][j][0]=((i>>j)&1)^1;c[i][j][1]=(i>>j)&1;}}
}void addEdg(int u, int v, ll w){edg[cnt].u=u, edg[cnt].v=v, edg[cnt].w=w;edg[cnt].nxt=head[u],head[u]=cnt++;
}void cal_cir(int fir, int las, int q){int num=0, id=las;while(id!=fir){tmp[++num]=edg[pos[id]];//tmp是暂时存放环上的边id=fa[id];}tmp[++num]=edg[q];ll mn=llINF;for(int i=1; i<=num; i++){if(tmp[i].w<mn){mn=tmp[i].w; id=i;//找最小边}}for(int i=1; i<=num; i++){if(i!=id){e[++cn]=tmp[i];//加入边集e[cn].w+=mn;}}
}void tarjan(int u, int f){dfn[u]=low[u]=++dfs_clock;fa[u]=f;for(int i=head[u]; ~i; i=edg[i].nxt){int v=edg[i].v;if(v==f) continue;if(!dfn[v]) pos[v]=i, tarjan(v, u), low[u]=min(low[u], low[v]);else low[u]=min(low[u], dfn[v]);}for(int i=head[u]; ~i; i=edg[i].nxt){int v=edg[i].v;if(low[v]>dfn[u])e[++cn]=edg[i];//树边else if(dfn[v]>dfn[u]&&fa[v]!=u)cal_cir(u, v, i);//环}}bool cmp(Edg a, Edg b){return a.w>b.w;
}int main()
{int T;scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);init();int u, v;ll w;for(int i=1; i<=m; i++){scanf("%d%d%lld", &u, &v, &w);addEdg(u, v, w);addEdg(v, u, w);}tarjan(1, -1);sort(e+1, e+1+cn, cmp);//边值排序for(int i=1; i<=cn; i++){int ta=_find(e[i].u), tb=_find(e[i].v);ll w=e[i].w;for(int j=0; j<=30; j++){if (w & (1ll << j)) {ans += c[ta][j][0] * c[tb][j][0] * (1ll << j);ans += c[ta][j][1] * c[tb][j][1] * (1ll << j);}else {ans += c[ta][j][0] * c[tb][j][1] * (1ll << j);ans += c[ta][j][1] * c[tb][j][0] * (1ll << j);}}f[ta]=tb;for(int j=0; j<=30; j++){c[tb][j][0]+=c[ta][j][0];//将每一位的数量统计到祖先节点上c[tb][j][1]+=c[ta][j][1];}}printf("%llu\n", ans);}return 0;
}
/*
100
3 3
1 2 5
2 3 6
3 1 5
5 4
1 2 1
2 3 2
3 4 3
4 5 4
10 13
1 2 1
2 3 2
2 4 4
3 4 5
4 10 8
10 9 6
4 9 7
4 5 11
5 6 13
6 4 7
4 7 1
4 8 1
7 8 1
8 10
1 2 1
2 3 2
2 4 4
4 5 4
4 6 4
5 6 5
6 7 6
6 8 6
7 8 7
3 4 3
*/