kmjp's blog

競技プログラミング参加記です

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の経路にある頂点群をすべて選ぶことである。
ここから頂点を増やすことを考える。

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

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

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

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

この際、経路の選び方が影響するのは最後のものだけである。
よって経路上に登場する次数2の頂点の数が最大化するような葉を2つ選ぼう。
これは各頂点を根とした場合、子頂点のうち登場する次数2の頂点の数が最大となるもの2つを選ぶ木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);
	
}

まとめ

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