Description

给出一个$n$个点$m$条边的无向图，任意两点之间至多两条路径，以$flow(s,t)$表示$s,t$两点之间的最大流，求$\sum\limits_{1\le s<t\le n}s\oplus t\oplus flow(s,t)$

Input

第一行一整数$T$表示用例组数，每组用例首先输入两个整数$n,m$表示点数和边数，最后$m$行每行输入三个整数$u,v,w$表示$u,v$之间有一条流量为$w$的边

$(1\le T\le 100,1\le n\le 10^5,n-1\le m\le \frac{3}{2}(n-1),0\le w\le 10^9)$

Output

输出结果

Sample Input

2
3 3
1 2 5
2 3 6
3 1 5
5 6
1 2 5
2 3 6
3 1 5
3 4 6
4 5 5
5 3 6

Sample Output

27
116

Solution

由于两点之前至多两条路径，显然可知每条边至多属于一个环（否则两个环上的点之间至少有四条路径），两点之间最大流等于最小割，两点之间如果只有一条路径那么必然会割掉这条路径上边权最小值，两点之间如果有两条路径，那么有两种情况，一种是依旧断一条边权最小的边使得两点不可达，一种是断掉环上的两条边使得两点不可达. 同时注意到如果断环上两条边，那么其中一条必然是环上边权最小值，另一条需要根据两点的可达情况来选择，那么我们把每个环上边权最小的边删掉，将其边权加到该环所有剩余边的边权上，将该图变成一棵树，则该树上两点之间的最小割与原图这两点之间的最小割等价. 而求树上两点的最小割，只需类似$Kruskal$，按边权从大到小加入边，用并查集维护连通分量，当前加入的边$u\rightarrow v$的边权必然是$u$所处集合点到$v$所处集合点的最小割，由于结果是要累加编号与最小割的异或和，故每个联通分量里需要维护二进制第$j$位为$0,1$的数量，每次根据边权在第$j$位的值来判断需要两个点集在该位的状态，注意到结果会爆$long\ long$，要用$unsigned\ long\ long$

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef unsigned long long ull;
#define maxn 100005
struct Edge
{int u,v,w,flag,next;
}edge[3*maxn];
int tot,head[maxn];
void add(int u,int v,int w)
{edge[tot].u=u,edge[tot].v=v,edge[tot].w=w,edge[tot].flag=0;edge[tot].next=head[u],head[u]=tot++;
}
int T,n,m,vis[maxn],pre[maxn];
vector<int>s,e; 
void dfs(int u,int id)
{vis[u]=1;for(int i=head[u];~i;i=edge[i].next){if(edge[i].flag)continue;edge[i].flag=edge[i^1].flag=1;int v=edge[i].v,w=edge[i].w;s.push_back(i);if(vis[v]){int mn=w;for(int i=s.size()-1;i>=0;i--){mn=min(mn,edge[s[i]].w);edge[s[i]].flag=2;//环边 if(edge[s[i]].u==v)break;}int flag=0;while(1){int temp=s.back();s.pop_back();if(!flag&&edge[temp].w==mn)flag=1;else{edge[temp].w+=mn;e.push_back(temp);}if(edge[temp].u==v)break;}continue;}dfs(v,i);}if(id!=-1&&edge[id].flag!=2){e.push_back(s.back());s.pop_back();}
}
bool cmp(int x,int y)
{return edge[x].w>edge[y].w;
}
int fa[maxn],num[maxn][31],Size[maxn];
int find(int x)
{if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);tot=0;memset(head,-1,sizeof(head));while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w),add(v,u,w);}e.clear();memset(vis,0,sizeof(vis));dfs(1,-1);sort(e.begin(),e.end(),cmp);for(int i=1;i<=n;i++){fa[i]=i;Size[i]=1;for(int j=0;j<=30;j++)if((i>>j)&1)num[i][j]=1;else num[i][j]=0;}ull ans=0;for(int i=0;i<e.size();i++){int u=edge[e[i]].u,v=edge[e[i]].v,w=edge[e[i]].w;u=find(u),v=find(v);for(int j=0;j<=30;j++){ull res=0;if((w>>j)&1){res+=(ull)num[u][j]*num[v][j];res+=(ull)(Size[u]-num[u][j])*(Size[v]-num[v][j]);}else{res+=(ull)num[u][j]*(Size[v]-num[v][j]);res+=(ull)(Size[u]-num[u][j])*num[v][j];}ans+=(1ull<<j)*res;}for(int j=0;j<=30;j++)num[v][j]+=num[u][j];fa[u]=v,Size[v]+=Size[u];}printf("%llu\n",ans);}return 0;
}