CSAcademy Round #69 : D. Cover the Tree

今回B,Cが難しくないですか？
https://csacademy.com/contest/round-69/task/cover-the-tree/

問題

木が与えられる。
いくつかのパスを張り、全部の辺を最低１回ずつ覆うようにせよ。
パス同士は重なってもよい。

解法

葉の頂点数に関し重心を求めよう。
そうすると各SubTree内の葉頂点数は全体の半分以下なので、重心を通るように葉同士のペアを組めば全部の辺がカバーされる。

int N;
vector<int> E[101010];
int num[101010];
int L;
vector<int> C;

pair<int,int> dfs_center(int cur,int pre) {
	pair<int,int> res=make_pair(1<<30,-1);
	int ma=0;
	num[cur]=E[cur].size()==1;
	
	FORR(r,E[cur]) if(r!=pre) {
		res=min(res,dfs_center(r,cur));
		ma=max(ma,num[r]);
		num[cur]+=num[r];
	}
	if(E[cur].size()>=2) res=min(res,make_pair(max(ma,L-num[cur]),cur));
	return res;
}

void dfs2(int cur,int pre) {
	if(E[cur].size()==1) C.push_back(cur+1);
	FORR(e,E[cur]) if(e!=pre) dfs2(e,cur);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	if(N==2) {
		_P("1\n");
		_P("1 2\n");
		return;
	}
	
	int L=0;
	FOR(i,N) if(E[i].size()==1) L++;
	FOR(i,N) if(E[i].size()>=2) {
		auto p=dfs_center(i,-1);
		x=p.first;
		break;
	}
	
	dfs2(x,-1);
	if(C.size()%2) C.push_back(C.back());
	x=C.size()/2;
	cout<<x<<endl;
	FOR(i,x) cout<<C[i]<<" "<<C[i+x]<<endl;
}

まとめ

BもCもDiv2らしからぬ難易度。