Wunder Fund Round 2016 : D. Hamiltonian Spanning Tree

これはコーナーケースを落とさなくてよかった。
http://codeforces.com/contest/618/problem/D

問題

N頂点の完全グラフがある。
各辺の長さはYである。
ここで、この完全グラフからあるMSTを作成し、その辺の長さをXにした。

N,X,Y及びMSTを成す辺が与えられる。
このグラフ上のハミルトンパスのうち、総距離の最小値を求めよ。

解法

XとYの大小で解法が異なる。

• X＜Yの場合
  • ハミルトンパスは(N-1)本の辺を辿るので、MSTを無視すると長さはどう辿ってもY(N-1)となる。
  • ここで、ハミルトンパスを作る際、できるだけMSTの構成辺を流用すると1本あたり(Y-X)長さが減る。
  • MSTを複数のパスに分解しよう。これはDPを使い子頂点のうちパスの端点になっているものの数を数えていき、2個以上の子が端点を持つならうち２つを連結する、という処理を繰り返すことで求められる。
  • 上記DPのパス数がp個なら、それらを結ぶため(p-1)本は長さYの辺を使う必要があり、それ以外はMST中の辺を使えばよいので、(p-1)*Y + (N-1-(p-1))*Xが解。
• X＞Yの場合
  • MST中のパスはできるだけ使いたくない。
  • 点が増えるとMST以外の辺が増えるので、MST以外の辺だけでハミルトンパスを形成できる。よって解は(N-1)*Y。
  • コーナーケースとして、MSTが完全にスター型になっている場合、その頂点だけはMST中のパスを１本使わないと他頂点と連結できないので解は(N-2)*Y+X。

int N;
ll X,Y;
vector<int> E[202020];
int part;

int dfs(int cur,int pre) {
	int ret=0;
	FORR(r,E[cur]) if(r!=pre) ret+=dfs(r,cur);
	
	if(ret<=1) return 1;
	part += ret-1;
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	ll ret=0;
	if(X<=Y) {
		part+=dfs(0,-1);
		ret=(N-1)*X+(part-1)*(Y-X);
	}
	else {
		FOR(i,N) if(E[i].size()==N-1) break;
		if(i==N) ret=(N-1)*Y;
		else ret=(N-2)*Y+X;
		
	}
	cout<<ret<<endl;
}

まとめ

スター型はコーナーケースで結構落とした人いたみたいだし、自分もHackを狙ったのだけど残念ながら自分の部屋にはそもそもDをPretest通した人が少なかった…。