很丁真的一个题，权当复习下树上倍增的写法了
考虑先给图求出一个MST，那么很容易发现对于每条非树边\((u,v)\)，它的权值必须严格大于MST上\(u,v\)之间所有边的权值，否则就可以用这条非树边来替换某一条树边
因此直接倍增维护树上两点间最大边权即可，复杂度\(O(n\log n)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
struct edge
{
int x,y,z;
friend inline bool operator < (const edge& A,const edge& B)
{
return A.z<B.z;
}
}E[N]; int n,m,fa[N],used[N],ans; vector <pi> v[N];
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
namespace LCA_solver
{
int dep[N],anc[N][20],mx[N][20];
inline void DFS(CI now=1,CI fa=0)
{
dep[now]=dep[fa]+1; anc[now][0]=fa; for (RI i=0;i<19;++i)
if (anc[now][i]) anc[now][i+1]=anc[anc[now][i]][i],mx[now][i+1]=max(mx[now][i],mx[anc[now][i]][i]); else break;
for (auto [to,w]:v[now]) if (to!=fa) mx[to][0]=w,DFS(to,now);
}
inline int query(int x,int y,int ret=0)
{
RI i; if (dep[x]<dep[y]) swap(x,y);
for (i=19;~i;--i) if (dep[anc[x][i]]>=dep[y]) ret=max(ret,mx[x][i]),x=anc[x][i];
if (x==y) return ret;
for (i=19;~i;--i) if (anc[x][i]!=anc[y][i]) ret=max({ret,mx[x][i],mx[y][i]}),x=anc[x][i],y=anc[y][i];
return max({ret,mx[x][0],mx[y][0]});
}
};
using namespace LCA_solver;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%lld%lld",&n,&m),i=1;i<=m;++i)
scanf("%lld%lld%lld",&E[i].x,&E[i].y,&E[i].z);
for (i=1;i<=n;++i) fa[i]=i;
for (sort(E+1,E+m+1),i=1;i<=m;++i)
{
int x=getfa(E[i].x),y=getfa(E[i].y);
if (x==y) continue; used[i]=1; fa[x]=y;
v[E[i].x].push_back(pi(E[i].y,E[i].z));
v[E[i].y].push_back(pi(E[i].x,E[i].z));
}
for (DFS(),i=1;i<=m;++i) if (!used[i]) ans+=max(0LL,query(E[i].x,E[i].y)-E[i].z+1);
return printf("%lld",ans),0;
}