[BeiJing2010组队][BZOJ 1977]次小生成树 Tree

#include <cstdio>
#include <algorithm>
typedef long long llint;
const int inf=0x7FFFFFFF;
const int sizeOfN=;
const int sizeOfM=; namespace IOspace
{
inline int getint()
{
register int num=;
register char ch;
do ch=getchar(); while (ch<'' || ch>'');
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
return num;
}
inline void putint(llint num, char ch='\n')
{
char stack[];
register int top=;
if (num==) stack[top=]='';
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
if (ch) putchar(ch);
}
} int N, M; struct node {int u, v, c;};
node a[sizeOfM];
bool b[sizeOfM];
inline bool operator < (node i, node j)
{return i.c<j.c;} struct edge {int point, dist; edge * next;};
edge MEM[sizeOfM], * PORT=MEM;
edge * E[sizeOfN];
inline edge * newedge(int _point, int _dist, edge * _next)
{edge * ret=PORT++; ret->point=_point; ret->dist=_dist; ret->next=_next; return ret;}
inline void build(int u, int v, int c)
{E[u]=newedge(v, c, E[u]); E[v]=newedge(u, c, E[v]);} int r[sizeOfN];
int find(int x) {return r[x]==x?x:r[x]=find(r[x]);} int f[sizeOfN][], l[][sizeOfN][], h[sizeOfN];
bool vis[sizeOfN];
int top, stack[sizeOfN]; edge * temp[sizeOfN];
inline void search(); inline int max(int x, int y) {return x>y?x:y;}
inline int min(int x, int y) {return x<y?x:y;}
inline void swap(int & x, int & y) {int t=x; x=y; y=t;}
inline int lg(int x) {int i; for (i=;x>;i++) x>>=; return i;}
inline int lowbit(int x) {return x & -x;}
inline int lca(int, int, int);
inline llint kurskal();
inline void prepare();
inline int calc(); int main()
{
llint ans=; N=IOspace::getint(); M=IOspace::getint();
for (int i=;i<M;i++) a[i].u=IOspace::getint(), a[i].v=IOspace::getint(), a[i].c=IOspace::getint(); ans=kurskal();
prepare();
ans+=calc(); IOspace::putint(ans); return ;
}
inline void search()
{
f[][]=; h[]=;
for (stack[++top]=, temp[top]=E[];top; )
{
int & u=stack[top]; edge *& i=temp[top];
if (!vis[u]) vis[u]=;
for ( ;i;i=i->next) if (!vis[i->point])
{
f[i->point][]=u; h[i->point]=h[u]+;
l[][i->point][]=i->dist; l[][i->point][]=-inf;
stack[++top]=i->point; temp[top]=E[i->point];
break;
}
if (i) continue;
top--;
}
}
inline llint kurskal()
{
llint ret=;
int tot=N-; std::sort(a, a+M);
for (int i=;i<=N;i++) r[i]=i; for (int i=;i<M;i++)
{
int u=find(a[i].u), v=find(a[i].v);
if (u!=v)
{
build(a[i].u, a[i].v, a[i].c); ret+=a[i].c;
b[i]=;
r[u]=v;
if (!--tot) break;
}
} return ret;
}
inline void prepare()
{
search();
for (int j=;j<;j++)
for (int i=;i<=N;i++) if (h[i]>=(<<j))
{
f[i][j]=f[f[i][j-]][j-];
l[][i][j]=l[][i][j-]; l[][i][j]=l[][i][j-];
if (l[][f[i][j-]][j-]>l[][i][j]) l[][i][j]=l[][i][j], l[][i][j]=l[][f[i][j-]][j-];
else if (l[][f[i][j-]][j-]<l[][i][j])
if (l[][f[i][j-]][j-]>l[][i][j]) l[][i][j]=l[][f[i][j-]][j-];
}
}
inline int lca(int u, int v, int x)
{
int ret=-, dis; if (h[u]<h[v]) swap(u, v);
while (dis=h[u]-h[v])
{
int up=lg(lowbit(dis));
ret=max(ret, l[l[][u][up]==x][u][up]);
u=f[u][up];
}
if (u==v) return ret; for (int i=;i>=;i--)
if (f[u][i]!=f[v][i])
{
ret=max(ret, l[l[][u][i]==x][u][i]);
ret=max(ret, l[l[][v][i]==x][v][i]);
u=f[u][i]; v=f[v][i];
}
ret=max(ret, l[l[][u][]==x][u][]);
ret=max(ret, l[l[][v][]==x][v][]); return ret;
}
inline int calc()
{
int ret=inf;
for (int i=;i<M;i++)
if (!b[i])
ret=min(ret, a[i].c-lca(a[i].u, a[i].v, a[i].c));
return ret;
}