一句话题意：3e5个点、5e5条边的无向有权图，求删去每个点及其连边后的最小生成树边权和（不连通就是-1，答案在longlong范围）

我是这么想的：先求一个MST，然后在树上做事情，把树上节点u的fa（就是u子树之外的部分）及其每个儿子v缩点，然后对缩点们求MST，加上之前每个缩点部分的MST值，就是该结点的答案。

我赛时狂调两小时还是没写好，终于在比赛结束后一个半小时过了中样例。。。

有无神牛帮忙指出做法是否正确？谢谢啦。

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mx=1e6+5,mn=3e5+5;
int n,m,u,v,w,f[mx],head[mx],nxt[mx],val[mx],to[mx],cnt,dfn[mx],idx,sz[mx],_head[mx],_nxt[mx],_val[mx],_to[mx],_cnt,_tree[mx];
ll init,ans=0,mst[mx][2];
struct edge{
	int from,to,val;
	inline bool operator < (const edge &x)const{return x.val>val;}
}e[mx],E[mx];int ctr=0;
vector <edge> G[mn];set <pii> g;
inline int read(){int x=0;char ch=getchar();while(ch<'0' || ch>'9')ch=getchar();while(ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x;}
inline void wt(ll x){if(x>9)wt(x/10);putchar(x%10|48);}
inline void add_edge(int u,int v,int w){to[++cnt]=v;nxt[cnt]=head[u];val[cnt]=w;head[u]=cnt;}//tree edge
inline void add_edge_(int u,int v,int w,int x){_to[++_cnt]=v;_nxt[_cnt]=_head[u];_val[_cnt]=w;_tree[_cnt]=x;_head[u]=_cnt;}//to find connections in dfs2
inline void add(int u,int v,int w){e[++ctr]=(edge){u,v,w};}//to build initial MST
inline int find(int x){while(x!=f[x])x=f[x]=f[f[x]];return x;}
inline void merge(int x,int y){int u=find(x),v=find(y);if(u!=v)f[u]=v;}
inline ll kruskal_init(){
	sort(e+1,e+1+ctr);for(int i=1;i<=n;++i)f[i]=i;
	ll ret=0,cnt=0;
	for(int i=1;i<=ctr;i++){
		int u=e[i].from,v=e[i].to,w=e[i].val;
		if(find(u)==find(v)){add_edge_(u,v,w,0);continue;}//its a non-tree-edge
		ret+=e[i].val;merge(u,v);
		add_edge_(u,v,w,1);//its a tree-edge
		add_edge(u,v,w),add_edge(v,u,w);//add_to_real_tree
	}
	return ret;
}
inline void dfs(int u,int fa,int w){//get subtree_mst & subtree_sz & point_dfn
	dfn[u]=++idx;sz[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i],w=val[i];if(v==fa)continue;
		dfs(v,u,w);
		mst[u][1]+=mst[v][1]+w;sz[u]+=sz[v];
	}
}
inline bool check(int &x,int &y,int u,int fa){
	if(dfn[x]<=dfn[u] || dfn[x]>dfn[u]+sz[u]-1)x=fa;else x=(*g.lower_bound(make_pair(-dfn[x],0))).second;
	if(dfn[y]<=dfn[u] || dfn[y]>dfn[u]+sz[u]-1)y=fa;else y=(*g.lower_bound(make_pair(-dfn[y],0))).second;
	pii a=*g.lower_bound(make_pair(-dfn[x],0)),b=*g.lower_bound(make_pair(-dfn[y],0));//belong_column
	return a.second!=b.second;//same_column,continue
}
inline void dfs2(int u,int fa,int w){
	int sons=0;ll ret=init-(mst[u][1]+w);//ret+=mst[fa]
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;sons++;
		dfs2(v,u,val[i]);
		ret+=mst[v][1];//ret+=mst[son]
	}
	g.clear();//store columns
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		g.insert(make_pair(-dfn[v],v));//insert column_judgements
		for(int _i=0;_i<G[v].size();++_i)G[u].push_back(G[v][_i]);//transfer edge
		for(int _i=_head[v];_i;_i=_nxt[_i]){//to add_edge(v,anotherson or fa)
			int des=_to[_i];if(des==u || _tree[_i])continue;//v->des(son_of_v)
			int a=v,b=des;if(!check(a,b,u,fa))continue;
			G[u].push_back((edge){v,des,_val[_i]});G[u].push_back((edge){des,v,_val[_i]});
		}
	}
	
	//to get new_MST
	sort(G[u].begin(),G[u].end());for(int i=1;i<=n;++i)f[i]=i;
	int cnt=0,maxx=sons+(fa!=0);//maxx=points,cnt=now_edges
	if(cnt==maxx-1){ans+=ret;return;}//no need to mst
	
	for(int i=0;i<G[u].size();++i){
		int x=G[u][i].from,y=G[u][i].to,w=G[u][i].val;
		if(!check(x,y,u,fa) || find(x)==find(y))continue;
		ret+=w;merge(x,y);
		if(++cnt==maxx-1){ans+=ret;return;}//get MST
	}
	ans+=-1;return;
}
int main()
{
	//freopen("secret.in","r",stdin);
	//clock_t beg=clock();
	n=read();m=read();while(m--)u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);	
	init=kruskal_init();dfs(1,0,0);dfs2(1,0,0);
	wt(ans);
	//printf("\n%lf\n",double(clock()-beg)/CLOCKS_PER_SEC);
	return 0;
}