克鲁斯卡尔求最小生成树+倍增维护最大值次大值

lg过，loj WA 了最后一个点，求调。

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct nodee{
	int fromm,too,nextt;
	long long w;
	bool chos;
	int data;
}a[600007],e[200007];
int headd[100007],heedd[100007],js,js2;
inline void add(int qw,int wq,int qwq)
{
	++js;
	a[js].fromm=qw;
	a[js].too=wq;
	a[js].w=qwq;
	a[js].nextt=headd[qw];
	a[js].data=js;
	headd[qw]=js;
}
bool cmp2(nodee x,nodee y)
{
	return x.w<y.w;
}
bool cmp3(nodee x,nodee y)
{
	return x.data<y.data;
}
long long ans=0;
int fa[100007];
int find(int x)
{
	if(fa[x]==x)
	return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
int lg[100007];
int fa2[100007][19],maxn[100007][19],cmaxn[100007][19],depth[100007];
long long sum=1e18;
inline void edd(int qw,int wq,int qwq)
{
	++js2;
	e[js2].fromm=qw;
	e[js2].too=wq;
	e[js2].w=qwq;
	e[js2].nextt=heedd[qw];
	e[js2].data=js2;
	heedd[qw]=js2;
}
void dfs(int x,int faa)
{
	depth[x]=depth[faa]+1;
	fa2[x][0]=faa;
	for(register int i=1;i<=lg[depth[x]];++i)
	{
		fa2[x][i]=fa2[fa2[x][i-1]][i-1];
		if(maxn[x][i-1]<maxn[fa2[x][i-1]][i-1])
		{
			maxn[x][i]=maxn[fa2[x][i-1]][i-1];
			cmaxn[x][i]=max(maxn[x][i-1],cmaxn[fa2[x][i-1]][i-1]);
		}
		else if(maxn[x][i-1]>maxn[fa2[x][i-1]][i-1])
		{
			maxn[x][i]=maxn[x][i-1];
			cmaxn[x][i]=max(cmaxn[x][i-1],maxn[fa2[x][i-1]][i-1]);
		}
		else
		{
			maxn[x][i]=maxn[x][i-1];
			cmaxn[x][i]=max(cmaxn[x][i-1],cmaxn[fa2[x][i-1]][i-1]);
		}
	}
	for(register int i=heedd[x];i;i=e[i].nextt)
	{
		if(e[i].too==faa)
		continue;
		maxn[e[i].too][0]=e[i].w;
		dfs(e[i].too,x);
	}
}
inline long long chan(int x,int y,int lca,int k)
{
	int maxnn=0;
	int cmaxnn=0;
	if(x!=lca)
	{
		for(register int i=lg[depth[x]];i>=0;--i)
		{
		//	cout<<x<<" "<<depth[x]<<" "<<depth[fa2[x][i]]<<" "<<depth[lca]<<" "<<maxnn<<" "<<cmaxnn<<" "<<k<<endl;
			if(depth[fa2[x][i]]>=depth[lca])
			{
				if(maxnn<maxn[x][i])
				{
					cmaxnn=max(cmaxn[x][i],maxnn);
					maxnn=maxn[x][i];
				}
				else if(maxnn>maxn[x][i])
				{
					cmaxnn=max(maxn[x][i],cmaxnn);
				}
				else
				{
					cmaxnn=max(cmaxnn,cmaxn[x][i]);
				}
				x=fa2[x][i];
			}
		}
	}
	x=y;
	if(x!=lca)
	{
		for(register int i=lg[depth[x]];i>=0;--i)
		{
		//	cout<<x<<" "<<depth[x]<<" "<<depth[fa2[x][i]]<<" "<<depth[lca]<<" "<<maxnn<<" "<<cmaxnn<<" "<<k<<endl;
			if(depth[fa2[x][i]]>=depth[lca])
			{
				if(maxnn<maxn[x][i])
				{
					cmaxnn=max(cmaxn[x][i],maxnn);
					maxnn=maxn[x][i];
				}
				else if(maxnn>maxn[x][i])
				{
					cmaxnn=max(maxn[x][i],cmaxnn);
				}
				else
				{
					cmaxnn=max(cmaxnn,cmaxn[x][i]);
				}
				x=fa2[x][i];
			}
		}
	}
	if(k==maxnn)
	maxnn=cmaxnn;
	if(!maxnn)
	return 1e18;
	return k-maxnn;
}
inline long long LCA(int x,int y,int k)
{
	int jlx=x,jly=y;
	if(depth[x]<depth[y])
	swap(x,y);
	while(depth[x]>depth[y])
	x=fa2[x][lg[depth[x]-depth[y]]];
	if(x==y)
	return chan(jlx,jly,y,k);
	for(register int i=lg[depth[x]];i>=0;--i)
	{
		if(fa2[x][i]!=fa2[y][i])
		{
			x=fa2[x][i];
			y=fa2[y][i];
		}
	}
	x=fa2[x][0];
	y=fa2[y][0];
	return chan(jlx,jly,y,k);
}
int main()
{
//	freopen("tree10.in","r",stdin);
	scanf("%d%d",&n,&m);
	int qw,wq,qwq;
	for(register int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&qw,&wq,&qwq);
	//	if(qw==wq)
	//	continue;
		add(qw,wq,qwq);
		add(wq,qw,qwq);
	}
	sort(a+1,a+js+1,cmp2);
	for(register int i=1;i<=n;++i)
	fa[i]=i;
	int k=0;
	for(register int i=1;i<=js;++i)
	{
		int fa1=find(a[i].fromm),fa2=find(a[i].too);
		if(fa1==fa2)
		continue;
		fa[fa1]=fa2;
		ans+=a[i].w;
		edd(a[i].fromm,a[i].too,a[i].w);
		edd(a[i].too,a[i].fromm,a[i].w);
		a[i].chos=1;
		++k;
		if(k==n-1)
		break;
	}
	for(register int i=1;i<=n;++i)
	lg[i]=log2(i);
	dfs(1,0);
	sort(a+1,a+js+1,cmp2);
	m=js/2;
	for(register int i=1;i<=m;++i)
	{
		qwq=i*2,wq=i*2-1;
		if(a[qwq].chos||a[wq].chos)
		continue;
		qw=a[qwq].fromm;
		wq=a[qwq].too;
		qwq=a[qwq].w;
	//	cout<<qw<<" "<<wq<<" "<<qwq<<endl;
		sum=min(sum,LCA(qw,wq,qwq));
	}
//	cout<<ans<<endl;
	printf("%lld",ans+sum);
	return 0;
}