Codeforces ECR #003 : E. Minimum spanning tree for each edge

これは凡ミスしたもののまぁすんなり。
http://codeforces.com/contest/609/problem/E

問題

重み付無向辺で構成される連結グラフが与えられる。

各辺に対し、その辺を含む最小全域木の総重量を求めよ。

解法

まず最小全域木を求めよう。

次に、頂点対(u,v)に対しu→vに至る経路中の最大コスト辺を求められるようにしておこう。
これには、u→LCA(u,v)とv→LCA(u,v)の最大コスト辺が求められれば良い。
よってu→LCA(u,v)の最大コスト辺を高速に求められるよう、ダブリングで各頂点から2の累乗個分親の頂点までの最大コスト辺を計算しておく。

ここまで事前に準備しておいて、各辺に対し題意の値を求めよう。
対象の辺がすでに最小全域木に含まれるなら、最小全域木の重さを答えればよい。
そうでない場合、uとvをつなぐ辺を加えることになるので、閉路ができる。
そのためu→LCA(u,v)→vのうち最大コストの辺を除こう。これは先の事前計算結果により高速に計算できる。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

int N,M;
map<pair<int,int>,int > MP;
int U[202020],V[202020], W[202020];
vector<pair<int,int> > VV;
int inc[202020];
vector<int> E[202020];
ll sum;

int P[21][200005],MA[21][200005],D[200005];

void dfs(int cur) {
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
}
int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

int hoge(int a,int b) {
	int ret=0;
	for(int i=19;i>=0;i--) if(D[a]-D[b]>=(1<<i)) {
		ret = max(ret,MA[i][a]);
		a=P[i][a];
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		U[i]--, V[i]--;
		if(U[i]>V[i]) swap(U[i],V[i]);
		MP[{U[i],V[i]}]=i;
		VV.push_back({W[i],i});
	}
	sort(ALL(VV));
	FORR(r,VV) {
		x = r.second;
		if(uf[U[x]] != uf[V[x]]) {
			inc[x]=1;
			sum += W[x];
			uf(U[x],V[x]);
			E[U[x]].push_back(V[x]);
			E[V[x]].push_back(U[x]);
		}
	}
	
	dfs(0);
	FOR(x,N) {
		y=P[0][x];
		if(x!=y) MA[0][x]=W[MP[{min(x,y),max(x,y)}]];
	}
	FOR(i,19) FOR(x,N) {
		P[i+1][x]=P[i][P[i][x]];
		MA[i+1][x] = max(MA[i][x],MA[i][P[i][x]]);
	}
	FOR(i,M) {
		int lc=lca(U[i],V[i]);
		int mae=max(hoge(U[i],lc),hoge(V[i],lc));
		cout<<(sum-mae+W[i])<<endl;
	}
}

まとめ

思いつけて良かった。