Codeforces #427 Div2 F. Roads in the Kingdom

こちらも勉強になった。
http://codeforces.com/contest/835/problem/F

問題

N頂点N辺の連結グラフが与えられる。
各辺には長さが設定されている。

辺のうち、消してもグラフの連結性が保てるものを１つ消したい。
消した後の木の直径の最小値を求めよ。

解法

N点N辺なので、このグラフはいわゆるなもりグラフである。
辺を消して連結性を保つには、消す辺は閉路中でなければならない。

言い換えれば閉路中の各頂点にぶら下がった木の辺は消さない。
よってまずこれらを処理しよう。

閉路中の各頂点から木の中の最遠点の距離を求めると同時に、個々の木の中における直径の最大値を求めよう。
（自分は後者をやり忘れてひどく手こずった）
そうすると、残りは閉路だけ(ただし閉路上の頂点にはそれぞれ閉路外の最遠点までの距離がわかってる)という状態になる。
ここで閉路中の１本の辺を消したときの直径を順次求めることを考える。

まず、閉路上の頂点を順に辿り、1～Cの計C頂点があったとする。
頂点C-1間の辺は残るものとし、i-(i+1)の辺が消えた状態を順次考えていく。

i-(i+1)の辺が消えた状態では、直径は以下のいずれかである。

• 1～i番の頂点およびそれらの最遠点で構成されるグラフの直径
• (i+1)～C番の頂点およびそれらの最遠点で構成されるグラフの直径
• (1～i番の最遠点のうち1番から最も遠い頂点の距離)+((i+1)～C番の最遠点のうちC番から最も遠い頂点の距離)+(C-iの距離)

各値はiを1からインクリメントしたり逆にC-1からデクリメントしていくことでそれぞれO(1)で求めることができる。
よって３つの最大値が最小となるものを求めればよい。
C-1間の辺が消えるケースは、i=Cとみなし先頭の値だけ求めればよい。

int N;
set<pair<int,int>> E[202020];
ll ntot[202020];
int vis[202020];
vector<pair<int,ll>> V;
map<pair<int,int>,int> M;
vector<ll> chi[202020];

void dfs(int cur,ll tot) {
	if(vis[cur]) return;
	vis[cur]=1;
	V.push_back({cur,tot});
	FORR(e,E[cur]) dfs(e.first,tot+e.second);
}

ll X[202020],L[202020];
ll Rdia[202020],Rma[202020];
ll Ldia[202020],Lma[202020];
ll tma;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y>>r;
		E[x-1].insert({y-1,r});
		E[y-1].insert({x-1,r});
		M[{x-1,y-1}]=M[{y-1,x-1}]=r;
	}
	queue<int> Q;
	FOR(i,N) if(E[i].size()==1) Q.push(i);
	
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		auto r=*E[cur].begin();
		E[cur].clear();
		int tar=r.first;
		int co=r.second;
		E[tar].erase({cur,co});
		
		chi[cur].push_back(0);
		chi[cur].push_back(0);
		sort(ALL(chi[cur]));
		reverse(ALL(chi[cur]));
		tma=max(tma,chi[cur][0]+chi[cur][1]);
		
		chi[tar].push_back(chi[cur][0]+co);
		ntot[cur]=-1;
		if(E[tar].size()==1) Q.push(tar);
	}
	
	FOR(i,N) if(ntot[i]>=0) {
		chi[i].push_back(0);
		chi[i].push_back(0);
		sort(ALL(chi[i]));
		reverse(ALL(chi[i]));
		tma=max(tma,chi[i][0]+chi[i][1]);
		ntot[i]=chi[i][0];
	}
	FOR(i,N) if(ntot[i]>=0) {
		dfs(i,0);
		break;
	}
	
	int C=V.size();
	FOR(i,C) {
		X[i]=V[i].second;
		L[i]=ntot[V[i].first];
	}
	ll tot=V.back().second + M[{V[0].first,V.back().first}];
	
	ll mi=1LL<<60;
	ll RR=0,LL=1LL<<60;
	for(i=C-1;i>=0;i--) {
		Rma[i]=max(Rma[i+1],tot-X[i]+L[i]);
		Rdia[i]=max({Rdia[i+1],RR-X[i]+L[i],L[i]});
		RR=max(RR,X[i]+L[i]);
	}
	
	FOR(i,C) {
		Lma[i]=max(i?Lma[i-1]:0,X[i]+L[i]);
		Ldia[i]=max({i?Ldia[i-1]:0,X[i]+L[i]-LL,L[i]});
		LL=min(LL,X[i]-L[i]);
		
		if(i==C-1) {
			mi=min(mi,Ldia[i]);
		}
		else {
			mi=min(mi,max({Ldia[i],Rdia[i+1],Lma[i]+Rma[i+1]}));
		}
	}
	cout<<max(tma,mi)<<endl;
	
	
}

まとめ

このテクは覚えておこう。