CODE FESTIVAL 2016 Relay : K - 木の問題 / Problem on Tree

これは結構考察が必要でチーム向きな問題だと思った。
http://cf16-relay-open.contest.atcoder.jp/tasks/relay_k

問題

木を成す無向グラフが与えられる。
このうちいくつかの異なる頂点からなる頂点列V[i]を作りたい。
この時、V[i]とV[i+1]を結ぶ最短経路上に、ほかにV上に含まれる頂点がないようにしたい。

Vは最長で何要素のものが構築可能か。

解法

Vにどういう頂点列を選べばいいか考える。
まず真っ先に思いつくのは2つの葉A,Bの経路にある頂点群をすべて選ぶことである。
ここから頂点を増やすことを考える。

経路中、３辺以上、すなわち経路外の頂点への脇道を持つ頂点cがあるとする。
この時、cをVに含まないようにすると、この脇道の頂点をVに取り入れることができるようになる。
また、脇道の途中にさらに分岐があるとき、vからその脇道までの間の頂点を選択しないようにするとそれぞれその分岐の先の頂点をVに取り入れることができるようになる。

そうして考えると、分岐の先の葉の頂点をVに入れるとVに入れる要素を最大化できそうである。
また、仮に脇道の先に分岐が１個もなくても葉は最低1個はあるので、cの代わりにその葉を入れれば少なくとも損はしない。

よって、Vは以下のように選択するとよい。

• 葉の頂点は全部Vに含める
• 次数が３以上の頂点はVに含めない
• ２つの葉を結ぶ経路上にある、次数２の頂点はVに含める

この際、経路の選び方が影響するのは最後のものだけである。
よって経路上に登場する次数２の頂点の数が最大化するような葉を２つ選ぼう。
これは各頂点を根とした場合、子頂点のうち登場する次数２の頂点の数が最大となるもの２つを選ぶ木DPを行っていけばよい。

int N;
vector<int> E[101010];
int C[101010];
int ma;

int dfs(int cur,int pre) {
	vector<int> V={0,0};
	FORR(e,E[cur]) if(e!=pre) V.push_back(dfs(e,cur));
	
	sort(ALL(V));
	reverse(ALL(V));
	ma=max(ma, C[cur]+V[0]+V[1]);
	C[cur]+=V[0];
	return C[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);
	}
	
	int leaf=0;
	int st=-1;
	FOR(i,N) {
		if(E[i].size()==1) leaf++;
		if(E[i].size()==2) {
			C[i]=1;
			st=i;
		}
	}
	
	if(st==-1) return _P("%d\n",leaf);
	dfs(st,-1);
	_P("%d\n",leaf+ma);
	
}

まとめ

シンプルな問題設定なのに、選ぶ頂点がかなり独特な形状になるのが面白い。