Codeforces #1045 : Div2. D. Sliding Tree

Dまではすんなり。
https://codeforces.com/contest/2134/problem/D

問題

木を成す無向グラフがあたえられる。
slidingとは以下の手順を意味する。

• 3頂点のパスa,b,cを選ぶ。
• bにつながるa,c以外の隣接点を、cにつなぎ変える。

入力された木をパスグラフにするため、slidingを最少回数で達成したい。
1手目の例を答えよ。

解法

N-1から、直径に相当する回数だけ、slidingを減らすことができる。
そこで直径に相当するパスを1つ求める。
このパス上で、直径以外の辺とつながっている場合、初手で直径を分割してそれら他の辺の先の点につながぎ換えよう。
そうすると直径が1伸びる。

int T,N;
vector<int> E[202020];
int path[202020];

pair<int,int> farthest(int cur,int pre,int d,vector<int>& D) {
	D[cur]=d;
	pair<int,int> r={d,cur};
	FORR(e,E[cur]) if(e!=pre) r=max(r, farthest(e,cur,d+1,D));
	return r;
}

//両端と間の頂点を返す
vector<pair<int,int>> diameter() { // diameter,center
	vector<int> D[2];
	D[0].resize(N);
	D[1].resize(N);
	auto v1=farthest(0,0,0,D[0]);
	auto v2=farthest(v1.second,v1.second,0,D[0]);
	farthest(v2.second,v2.second,0,D[1]);
	
	vector<pair<int,int>> R;
	//重心を取る場合
	for(int i=N-1;i>=0;i--) if(D[0][i]+D[1][i]==v2.first) R.push_back({D[0][i],i});
	sort(ALL(R));

	return R;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			E[i].clear();
			path[i]=0;
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		auto V=diameter();
		FORR2(d,v,V) path[v]=1;
		
		FOR(i,N) if(path[i]) {
			x=y=-1;
			FORR(e,E[i]) {
				if(path[e]==0) y=e;
				if(path[e]==1) x=e;
			}
			if(x>=0&&y>=0) {
				cout<<x+1<<" "<<i+1<<" "<<y+1<<endl;
				break;
			}
		}
		if(i==N) cout<<-1<<endl;
		
	}
}

まとめ

これはちょっとの考察でできそう。