BZOJ 1977([BeiJing2010组队]次小生成树 Tree-LCA的位运算)(二)
t &nowdp,int &nowdp0,int c)
{
if (c<=nowdp0) return;
else if (nowdp0
else if (c==nowdp) return;
else if (nowdp
}
int lca(int x,int y,int &nowdp,int &nowdp0)
{
nowdp=nowdp0=-1;
if (deep[x]
int t=deep[x]-deep[y];
for (int i=0;t;i++)
if (t&bin[i])
{
check(nowdp,nowdp0,dp[x][i]);
check(nowdp,nowdp0,dp0[x][i]);
x=f[x][i];
t-=bin[i];
}
int i=Li-1;
while (x^y)
{
while (f[x][i]==f[y][i]&&i) i--;
check(nowdp,nowdp0,dp[x][i]);
check(nowdp,nowdp0,dp0[x][i]);
check(nowdp,nowdp0,dp[y][i]);
check(nowdp,nowdp0,dp0[y][i]);
x=f[x][i];y=f[y][i];
}
}
int father[MAXN];
long long sum_edge=0;
int getfather(int x)
{
if (father[x]==x) return x;
father[x]=getfather(father[x]);
return father[x];
}
void union2(int x,int y)
{
father[father[x]]=father[father[y]];
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) father[i]=i;
memset(b,0,sizeof(b));
memset(next,0,sizeof(next));
for (int i=0;i
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
sort(e+1,e+1+m);
for (int i=1;i<=m;i++)
{
if (getfather(e[i].u)!=getfather(e[i].v)) {union2(e[i].u,e[i].v);addedge2(e[i].u,e[i].v,e[i].w);sum_edge+=e[i].w; }
else b[i]=1;
}
bfs();
long long mindec=-1;
for (int i=1;i<=m;i++)
if (b[i])
{
int nowdp,nowdp0;
lca(e[i].u,e[i].v,nowdp,nowdp0);
if (nowdp==e[i].w) nowdp=nowdp0;
if (nowdp==-1) continue;
if (mindec==-1||mindec>e[i].w-nowdp) mindec=e[i].w-nowdp;
}
printf("%lld\n",sum_edge+mindec);
return 0;
}