WA80分求助

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<cstdio>
using namespace std;
#define ll long long
ll n, m, h[100005], f[100005], fh[100005];
ll ft[100005], ch[100005][20][2], u[100005][20], vis[500005];
ll dp[100005], s, longa, longb;
ll pq[100005], f1, f2, f3, f4;
int zuxian(int x) {
	if(x==f[x]) return x;
	return f[x]=zuxian(f[x]);
}
struct AB {
	int a, b, c, n;
	bool operator < (const AB &A) const {
		return c < A.c;
	}
} d[1000005], mp[1000005];
//vector<int> mp[100005];
void charu(int a,int b,int c,int i) {
	d[i].a=a, d[i].b=b, d[i].c=c;
	d[i].n=h[a], h[a]=i;
}
void dfs(int k,int fa) {
	for(int i=fh[k]; i; i=mp[i].n) {
		if(!pq[i])continue;
		int p=mp[i].b;
		if(p!=fa) {
			dp[p]=dp[k]+1;
			ft[p]=k;
			u[p][0]=k;
			ch[p][0][0]=mp[i].c;
			dfs(p,k);
		}
	}
}
int LCA(int a,int b) {
	if(dp[a]<dp[b]) {
		int t=a;
		a=b;
		b=t;
	}
	for(int i=20; i>=0; i--) {
		if(dp[a]-(2<<i-1)>=dp[b]) a=u[a][i];
	}
	if(a==b) return a;
	for(int i=20; i>=0; i--) {
		if(u[a][i]!=u[b][i]) a=u[a][i], b=u[b][i];
	}
	return u[a][0];
}
void suan(int p,int a,int b) {
	int id=a; 
	for(int i=longa; i>=0; i--) {
		if(dp[id]-(2<<i-1)>dp[p]) {
			if(ch[id][i][0]>=f1) f1=ch[id][i][0];
			id=u[id][i];
		}
	}
	for(int i=longa; i>=0; i--) {
		if(dp[a]-(2<<i-1)>=dp[p]) {
			if(ch[a][i][0]<f1) f3=max(f3,ch[a][i][0]);
			else f3=max(f3,ch[a][i][1]);
			a=u[a][i];
		}
	}
	id=b; 
	for(int i=longb; i>=0; i--) {
		if(dp[id]-(2<<i-1)>=dp[p]) {
			if(ch[id][i][0]>f2) f2=ch[id][i][0];
			id=u[id][i];
		}
	}
	for(int i=longb; i>=0; i--) {
		if(dp[b]-(2<<i-1)>=dp[p]) {
			if(ch[b][i][0]<f2) f4=max(f4,ch[b][i][0]);
			else f4=max(f4,ch[b][i][1]);
			b=u[b][i];
		}
	}
}
int main() {
	freopen("tree4.in","r",stdin);
	int a, b, c;
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		charu(a,b,c,i);
	}
	for(int i=1; i<=n; i++) f[i]=i;
	sort(d+1,d+m+1);
	int k=0;
	for(int i=1; i<=m; i++) {
		a=d[i].a, b=d[i].b, c=d[i].c;
		if(zuxian(a)!=zuxian(b)) {
			s+=d[i].c;
			vis[i]=1;
			f[zuxian(a)]=zuxian(b);
			++k;
			pq[k]=pq[k+n]=1;
			mp[k].a=a,mp[k].b=b,mp[k].c=c,mp[k].n=fh[a],fh[a]=k;
			mp[k+n].a=b,mp[k+n].b=a,mp[k+n].c=d[i].c,mp[k+n].n=fh[b],fh[b]=k+n;
		}
	}
	u[1][0]=1, dp[1]=1;
	dfs(1,1);
	for(int i=1; i<=20; i++) {
		for(int j=1; j<=n; j++) {
			if(dp[j]-(2<<i-1)<1)continue;
			ch[j][i][0]=max(ch[j][i-1][0],ch[u[j][i-1]][i-1][0]);
			if(ch[j][i-1][0]==ch[u[j][i-1]][i-1][0]) ch[j][i][1]=max(ch[j][i-1][1],ch[u[j][i-1]][i-1][1]);
			else if(ch[j][i-1][0]>ch[u[j][i-1]][i-1][0]) ch[j][i][1]=max(ch[j][i-1][1],ch[u[j][i-1]][i-1][0]);
			else ch[j][i][1]=max(ch[j][i-1][0],ch[u[j][i-1]][i-1][1]);
			u[j][i]=u[u[j][i-1]][i-1];
		}
	}
	ll q=1e18;
	for(int i=1; i<=m; i++) {
		if(!vis[i]) {
			a=d[i].a, b=d[i].b, c=d[i].c;
			int p=LCA(a,b);
			longa=(int)log2(dp[a]-dp[p]), longb=(int)log2(dp[b]-dp[p]);
			suan(p,a,b);
			int first, second;
			if(f1>f2) first=f1, second=max(f2,f3); 
			else if(f1==f2) first=f1, second=max(f3,f4);
			else first=f2, second=max(f1,f4);
			if(first<c) q=min(q,s+c-first);
			else q=min(q,s+c-second);
		}
	}
	cout<<q;
}