[Codeforces] 609E. Minimum spanning tree for each edge

題目連結:http://codeforces.com/problemset/problem/609/E

---

本題跟次小生成樹的做法大同小異，畢竟要做次小生成樹就要求MST for each edge，所以就按照次小生成樹的做法稍微改一改吧。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<int,lld> pil;

#define N 200000
#define logN 20
struct Edge{
	int s,e,id;
	lld w;
	Edge(){}
	Edge(int a,int b,lld c,int d){s=a;e=b;w=c;id=d;}
	bool operator<(const Edge& a){return w<a.w;}
};
int djs[N+1];
vector<Edge> Es;
int Query(int x){if(djs[x]!=x)djs[x]=Query(djs[x]);return djs[x];};
inline void Merge(int a,int b){djs[Query(a)]=Query(b);}
vector<pil> MST[N+5];

pil ff[N+1][logN+1];
int time_in[N+5],time_out[N+5],timer=0;
void dfs(int,int,lld);
inline int lca(int,int);
inline bool anc(int,int);
inline lld walk(int,int);

lld ans[N+5];

int main(){
	cin.tie(0);ios_base::sync_with_stdio(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<N;i++) djs[i]=i;
	for(int i=0;i<=N;i++)for(int j=0;j<=logN;j++) ff[i][j]={i,0};
	for(int i=0;i<m;i++){
		int a,b;lld c;
		cin>>a>>b>>c;
		Es.push_back(Edge(a,b,c,i));
	}
	sort(Es.begin(),Es.end());
	lld sumMst=0;
	vector<Edge> noMST;
	vector<int> inMST;
	for(auto i:Es){
		if(Query(i.s)!=Query(i.e)){
			sumMst+=i.w;
			Merge(i.s,i.e);
			inMST.push_back(i.id);
			MST[i.s].push_back({i.e,i.w});
			MST[i.e].push_back({i.s,i.w});
		}else noMST.push_back(i);	
	}
	for(auto i:inMST) ans[i]=sumMst;
	dfs(1,1,0);
	for(int j=1;j<=logN;j++){
		for(int i=1;i<=n;i++){
			ff[i][j].first = ff[ ff[i][j-1].first ][j-1].first;
			ff[i][j].second = max(ff[ff[i][j-1].first][j-1].second, ff[i][j-1].second);
		}
	}
	for(auto i:noMST){
		int LCA = lca(i.s,i.e);
		lld tt=walk(i.s, LCA);
		tt=max(tt, walk(i.e, LCA));
		ans[i.id]=sumMst-tt+i.w;
	}
	for(int i=0;i<m;i++)cout<<ans[i]<<'\n';
	return 0;
}

void dfs(int w,int f,lld v){
	time_in[w]=++timer;
	ff[w][0]={f,v};
	for(auto i:MST[w])
		if(i.first!=f) dfs(i.first,w,i.second);
	time_out[w]=++timer;
}
inline bool anc(int x,int y){
	return time_in[x]<=time_in[y]&&time_out[y]<=time_out[x];
}
inline int lca(int x,int y){
	if(anc(y,x))return y;
	for(int j=logN;j>=0;j--)
		if(!anc(ff[y][j].first, x)) y=ff[y][j].first;
	return ff[y][0].first;
}

inline lld walk(int x,int y){
	if(x==y)return 0;
	if(anc(y,x)) swap(x,y);
	lld rr=0;
	for(int i=logN;i>=0;i--){
		if(!anc(ff[y][i].first,x)){
			rr=max(rr, ff[y][i].second);
			y=ff[y][i].first;
		}
	}
	return max(rr, ff[y][0].second);
}