请尝试把数组开大一点。

顺便问一下为什么开大就对了？

77pts

100pts

77pts


#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define int long long
//#define double long double
#define FOR(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,r,l) for(int i=r;i>=l;--i)
#define mkp make_pair
#define fr first
#define se second
#define pb push_back
#define pk pop_back
#define pf push_front
#define pt pop_front
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
void IOS() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}
void Document() {
	freopen("P4180_12.in","r",stdin);
//	freopen(".out","w",stdout);
}
inline int read(){
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}
	return s*w;
}
inline void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
void Tell() {
	//写数据结构注意初始化！
	//浮点数类题目过不了优先考虑精度！
	//vector动态开点注意内存重分配！
	//有本地写freopen！没本地别写！！！
	//最后几分钟给我老老实实坐那里，别手贱！！！
	//long long 级别的常数运算一定要用 xll！！！
	//一定要手玩几组极限数据，防止爆数。
	//大数据关同步流！ 大数据关同步流！ 大数据关同步流！
	//删调试！删调试！删调试！删调试！删调试！
	//注意数据类型！注意数据类型！注意数据类型！不要把存 int 的数组开成 char 类型！
	//注意数组大小的上界，不要把 5e6 打成 6e5！
}
const int N=1e5+10,M=3e5+10;
int n,m,vis[N],dep[N],dp[N][40],lg,fa[N],f[N][40][2];//1zui 0ci
LL ans,Ans=1e15;
struct edge {
	int u,v,w;
}e[M];
vector<pair<int,int> >G[N];
void Con(int i,int j,int tmp) {
	if(f[i][j][1]<tmp) {
		f[i][j][0]=f[i][j][1];
		f[i][j][1]=tmp;
	} else if(f[i][j][0]<tmp&&f[i][j][1]>tmp) f[i][j][0]=tmp;
	return ;
}
void dfs(int x,int fat,int val) {
	dep[x]=dep[fat]+1;
	dp[x][0]=fat;
	f[x][0][1]=val;
	FOR(i,1,lg) {
		dp[x][i]=dp[dp[x][i-1]][i-1];
		FOR(j,0,1) {
			Con(x,i,f[x][i-1][j]);
			Con(x,i,f[dp[x][i-1]][i-1][j]);
		}
	}
	for(auto o:G[x]) {
		int y=o.fr;
		if(y==fat) continue;
		dfs(y,x,o.se);
	} 
}
int lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	ROF(i,lg,0) if(dep[dp[x][i]]>=dep[y]) x=dp[x][i];
	if(x==y) return x;
	ROF(i,lg,0) if(dp[x][i]!=dp[y][i]) x=dp[x][i],y=dp[y][i];
	return dp[x][0];
}
int cmp(edge x,edge y) {
	return x.w<y.w;
}
int Get(int x) {
	if(x==fa[x]) return x;
	return fa[x]=Get(fa[x]);
}
main() {
//	Document();
	cin>>n>>m;lg=log(n)/log(2); 
	FOR(i,1,m) {
		int u=read(),v=read(),w=read();
		e[i]={u,v,w};
	}
	memset(f,-0x3f,sizeof f);
	FOR(i,1,n) fa[i]=i;
	sort(e+1,e+m+1,cmp);
	int ct=0;
	FOR(i,1,m) {
		int w=e[i].w,u=e[i].u,v=e[i].v;
		if(Get(u)==Get(v)) continue;
		fa[Get(u)]=Get(v);
		vis[i]=1;
		G[u].pb({v,w});
		G[v].pb({u,w});
		ans+=w;++ct;
	}
	dfs(1,0,-1e9);
	FOR(o,1,m) {
		if(vis[o]) continue;
		int x=e[o].u,y=e[o].v,z=e[o].w;
		if(x==y) continue;
		int la=lca(x,y);
		f[0][0][0]=-1e12;f[0][0][1]=-1e12;
		if(la==y) swap(x,y);
		if(la==x) {
			ROF(i,lg,0) {
				if(dep[dp[y][i]]>=dep[la]) {
					FOR(j,0,1) Con(0,0,f[y][i][j]);
					y=dp[y][i];
				}
			}
			if(z==f[0][0][1]) cmin(Ans,(ans-f[0][0][0]+z));
			else cmin(Ans,(ans-f[0][0][1]+z));
		} else {
			ROF(i,lg,0) {
				if(dep[dp[x][i]]>=dep[la]) {
					FOR(j,0,1) Con(0,0,f[x][i][j]);
					x=dp[x][i];
				}
			}
			ROF(i,lg,0) {
				if(dep[dp[y][i]]>=dep[la]) {
					FOR(j,0,1) Con(0,0,f[y][i][j]);
					y=dp[y][i];
				}
			}
			if(z==f[0][0][1]) cmin(Ans,(ans-f[0][0][0]+z));
			else cmin(Ans,(ans-f[0][0][1]+z));
		}
	}
	cout<<Ans<<"\n";
	return 0;
}

AC只需要把50行的 $N$ 开到 $3\times 10^5$，$M$ 开到 $6\times 10^5$ 即可。