Codeforces ECR #035 : F. Tree Destruction

ミスが多すぎてひどいですね。
http://codeforces.com/contest/911/problem/F

問題

木を成すグラフが与えられる。
この木に対し、以下の処理を頂点が１つになるまで繰り返す。

• 葉となる頂点を２つ選び、両者の最短経路長をスコアに加え、片方の頂点を削除する。

最適な選択・削除順を選んだ時、得られるスコアの最大値を求めよ。

解法

まず木の直径を求めよう。
そうすると、木の直径上にない頂点は、直径の両端のいずれかとペアにして削除すると、可能な最高スコアが得られる。
よって、直径上以外の頂点を葉から順に、最高スコアが得られる側の点とペアにしつつ消していこう。

直径が残ると、あとは選択肢がないので適当に端から削除すればよい。

int N;
vector<vector<int>> E;

pair<int,int> farthest(vector<vector<int>>& E, 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,e,cur,d+1,D));
	return r;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	E.resize(N);
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	vector<int> D[2];
	D[0].resize(N);
	D[1].resize(N);
	auto v1=farthest(E,0,0,0,D[0]);
	auto v2=farthest(E,v1.second,v1.second,0,D[0]);
	farthest(E,v2.second,v2.second,0,D[1]);
	x = v1.second;
	y = v2.second;
	int d=D[0][y];
	vector<int> dia(d+1);
	ll ret=1LL*d*(d+1)/2;
	
	vector<vector<int>> V;
	FOR(i,N) {
		if(D[0][i]+D[1][i]==d) {
			dia[D[0][i]]=i+1;
		}
		else if(D[0][i]>D[1][i]) {
			ret+=D[0][i];
			V.push_back({D[0][i],x+1,i+1});
		}
		else {
			ret+=D[1][i];
			V.push_back({D[1][i],y+1,i+1});
		}
	}
	cout<<ret<<endl;
	sort(ALL(V));
	reverse(ALL(V));
	FORR(v,V) {
		cout<<v[1]<<" "<<v[2]<<" "<<v[2]<<endl;
	}
	
	while(dia.size()>1) {
		cout<<dia[0]<<" "<<dia.back()<<" "<<dia.back()<<endl;
		dia.pop_back();
	}
}

まとめ

これはすんなり解けた。