求助90分 TLE#10

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
int xl(int x)
{
	if(x&1) return x+1;
	else return x-1;
}
int n,m;
int mm1,mm2;
struct lsqxx
{
	struct ee
	{
		int next;
		int to;
		bool can;
		int val;
	};
	int head[maxn],cnt;
	ee bb[maxn*6];
	lsqxx()
	{
		memset(head,0,sizeof head);
		cnt=0;
	}
	void jb(int q,int z,int v)
	{
		bb[++cnt].to=z;
		bb[cnt].val=v;
		bb[cnt].can=0;
		bb[cnt].next=head[q];
		head[q]=cnt;
	}
};
lsqxx b1;
struct bcj
{
	int fa[maxn];
	void init()
	{
		for(int i=1;i<=n;i++)
			fa[i]=i;
	}
	int cz(int x)
	{
		int r=x;
		while(fa[x]!=x) x=fa[x];
		return fa[r]=x;
	}
	bool hb(int x,int y)
	{
		x=cz(x),y=cz(y);
		if(fa[x]==fa[y]) return 0;
		fa[x]=y;
		return 1;
	}
};
bcj bc;
struct eb
{
	int q;
	int z;
	int val;
	int cnt;
	bool can;
	eb()
	{
		q=z=val=0;can=0;
	}
	eb(int _q,int _z,int _v)
	{
		q=_q,z=_z,val=_v;can=0;
	}
	friend bool operator <(eb a,eb b)
	{
		return a.val<b.val;
	}
};
struct zxscs
{
	eb ed[maxn*6];
	int solve()
	{
		sort(ed+1,ed+1+m);
		int ans=0;
		for(int i=1;i<=m;i++)
		{
			eb t=ed[i];
			if(bc.hb(t.q,t.z)==1)
				b1.bb[t.cnt].can=1,b1.bb[t.cnt+1].can=ed[i].can=1,ans+=ed[i].val;
		}
		return ans;
	}
};
zxscs sc;
int dfn[maxn],lfa[maxn],fdfn[maxn];
int m1,m2;
void gx(int tt,int &_m1,int &_m2)
{
	if(tt>_m1)
		_m2=_m1,_m1=tt;
	else if(tt>_m2&&tt!=_m1)
		_m2=tt;
}
struct xds
{
	struct trr{
		int le;
		int ri;
		int max1,max2;
	};
	trr tr[maxn*4];
	int sz(int x)
	{
		return x<<1;
	}
	int sy(int x)
	{
		return (x<<1)|1;
	}
	void up(int rt)
	{
		gx(tr[sz(rt)].max1,tr[rt].max1,tr[rt].max2);
		gx(tr[sz(rt)].max2,tr[rt].max1,tr[rt].max2);
		gx(tr[sy(rt)].max1,tr[rt].max1,tr[rt].max2);
		gx(tr[sy(rt)].max2,tr[rt].max1,tr[rt].max2);
	}
	void build(int le,int ri,int rt)
	{
		tr[rt].le=le,tr[rt].ri=ri;
		if(le==ri)
		{
			tr[rt].max1=lfa[fdfn[le]];
			tr[rt].max2=0;
			return;
		}
		int mid=(le+ri)>>1;
		build(le,mid,sz(rt));
		build(mid+1,ri,sy(rt));
		tr[rt].max1=tr[rt].max2=0;
		up(rt);
	}
	void cz(int le,int ri,int rt)
	{
		if(le>ri)
			return;
		if(tr[rt].le>=le&&tr[rt].ri<=ri)
		{
			gx(tr[rt].max1,m1,m2);
			gx(tr[rt].max2,m1,m2);
			return;
		}
		int mid=(tr[rt].le+tr[rt].ri)>>1;
		if(mid>=le)
			cz(le,ri,sz(rt));
		if(mid<ri)
			cz(le,ri,sy(rt));
		return;
	}
};
xds tr;
struct spp
{
	int fa[maxn],size[maxn],son[maxn];
	int top[maxn],sd[maxn],dnt;
	void init()
	{
		dnt=0;
		memset(son,0,sizeof son);
	}
	void dfs(int x,int f,int ss)
	{
		fa[x]=f;size[x]=1;sd[x]=ss;
		for(int i=b1.head[x];i;i=b1.bb[i].next)
		{
			int sx=b1.bb[i].to;
			if(b1.bb[i].can&&sx!=f)
			{
				dfs(sx,x,ss+1);lfa[sx]=b1.bb[i].val;
				size[x]=size[sx]+size[x];
				if(size[sx]>size[son[x]])
					son[x]=sx;
			}
		}
	}
	void dfs2(int x)
	{
		//printf("++%d\n",x);
		if(x==son[fa[x]])
		{
			top[x]=top[fa[x]];
			//mp[top[x]]=max(mp[top[x]],lfa[x]);
		}
		else top[x]=x;
		dfn[x]=++dnt;fdfn[dnt]=x;
		if(son[x])
			dfs2(son[x]);
		for(int i=b1.head[x];i;i=b1.bb[i].next)
		{
			int sx=b1.bb[i].to;
			if(b1.bb[i].can&&sx!=son[x]&&sx!=fa[x])
				dfs2(sx);
		}
	}
	int lca(int x,int y)
	{
		while(top[x]!=top[y])
		{
			//cout<<x<<y<<endl;
			if(sd[top[x]]<sd[top[y]]) swap(x,y);
			x=fa[top[x]];
		}
		if(sd[x]>sd[y]) swap(x,y);
		return x;
	}
	void cz_low(int x,int y)
	{
		int t=lca(x,y);//printf("%d %d %d\n",x,y,t);
		mm1=0,mm2=0;
		while(x!=t)
		{
			int tt=lfa[x];
			if(tt>mm1)
				mm2=mm1,mm1=tt;
			else if(tt>mm2&&tt!=mm1)
				mm2=tt;
			x=fa[x];
		}
		while(y!=t)
		{
			int tt=lfa[y];
			if(tt>mm1)
				mm2=mm1,mm1=tt;
			else if(tt>mm2&&tt!=mm1)
				mm2=tt;
			y=fa[y];
		}
		return;
	}
	void jp(int &x,int t)
	{
		if(top[x]!=top[t])
		{
			gx(lfa[x],mm1,mm2);
			x=t;
			return;
		}
		m1=0,m2=0;
		tr.cz(dfn[t],dfn[x],1);
		gx(m1,mm1,mm2);gx(m2,mm1,mm2);
		x=t;
		return;
	}
	void cz(int x,int y)
	{
		int t=lca(x,y);//printf("%d %d %d\n",x,y,t);
		mm1=0,mm2=0;
		for(int i=1;i<=2;i++)
		{
			if(top[x]==top[t]&&x!=t)
			{
				m1=0,m2=0;
				tr.cz(dfn[t]+1,dfn[x],1);
				//printf("%d %d:%d %d\n",x,t,m1,m2);
				gx(m1,mm1,mm2);gx(m2,mm1,mm2);
			}
			else if(x!=t)
			{
				while(top[x]!=top[t])
				{
					jp(x,top[x]);
					jp(x,fa[x]);
				}
				m1=0,m2=0;
				tr.cz(dfn[t]+1,dfn[x],1);
				//printf("%d %d:%d %d\n",x,t,m1,m2);
				gx(m1,mm1,mm2);gx(m2,mm1,mm2);
			}
			x=y;
		}
		return;
	}
};
spp sp;
signed main()
{
	scanf("%lld%lld",&n,&m);
	bc.init();
	sp.init();
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&sc.ed[i].q,&sc.ed[i].z,&sc.ed[i].val);
		sc.ed[i].cnt=i*2-1;
		b1.jb(sc.ed[i].q,sc.ed[i].z,sc.ed[i].val);
		b1.jb(sc.ed[i].z,sc.ed[i].q,sc.ed[i].val);
	}
	int maxz=sc.solve();//cout<<maxz;
	sp.dfs(1,1,1);
	sp.dfs2(1);
	tr.build(1,n,1);
	//for(int i=1;i<=n;i++)
	//	printf("%d: fa:%d top:%d size:%d son:%d\n",i,sp.fa[i],sp.top[i],sp.size[i],sp.son[i]);
	int minz=LONG_LONG_MAX;
	for(int i=1;i<=m;i+=1)
	{
		mm1=mm2=0;
		eb w=sc.ed[i];
		if(w.can==0)
		{
			//printf("%d %d\n",w.q,w.z);
			sp.cz(w.q,w.z);
			//printf("%d %d\n",mm1,mm2);
			int mq;
			if(mm1==w.val)
				mq=maxz-mm2+w.val;
			else mq=maxz-mm1+w.val;
			//if(mm1==mm2) cout<<"what???"<<mm1<<endl;
			if(mq<minz)
				minz=mq;
		}
	}
	//m1=0,m2=0;
	//tr.cz(dfn[1],dfn[5],1);
	//cout<<m1<<" "<<m2<<endl;
	//cout<<dfn[1]<<" "<<dfn[4]<<endl;
	//cout<<min1<<min2;
	//for(int i=1;i<=n;i++)
	//	printf("%d ",dfn[i]);
	printf("%lld",minz);
	return 0;
}