Codeforces #397 E. Tree Folding

これはシンプルで面白い問題だった。
http://codeforces.com/contest/765/problem/E

問題

木を成す無向グラフが与えられる。
このグラフに対し、畳み込みという操作を定義する。

ある頂点vにおいて、そこから始まる2つのパスを考える。それらのパスが以下を満たす場合、2つのパスを葉頂点までの距離が等しい1つのパスにまとめることができる。

• 同じ頂点を含まない。
• vから葉頂点までに分岐がない。
• 葉頂点までの距離が等しい。

与えられたグラフに上記処理を繰り返したとき、グラフを単一のパスにできるか。
できる場合、最短の長さを答えよ。

解法

DFSを2回行い、各頂点において、隣接する各辺の先にある最遠点までの距離を求めよう。
この距離が異なる3つ以上の値を持つ場合、この頂点につながる3つ以上の辺を畳み込んで2つ以下にすることはできないので、条件を満たさない。

すべての点において、距離が異なる2つ以下の値しか持たない場合、1つのパスにできる。
その際は、葉頂点からの最遠点の距離を求めると、畳み込んだあとのパスの長さに一致する。

なお、分岐のない単一のパスを構成した場合も、その長さが偶数の場合、中心の点を取ることで半分に長さのパスに畳み込むことができる。
この処理を長さが奇数になるまで繰り返すとそれが解。

int N;
vector<int> E[202020];
vector<int> D[202020];

int dfs(int cur,int pre) {
	D[cur].push_back(0);
	FORR(e,E[cur]) if(e!=pre) {
		D[cur].push_back(dfs(e,cur));
	}
	sort(ALL(D[cur]));
	reverse(ALL(D[cur]));
	return D[cur][0]+1;
}

void dfs2(int cur,int pre,int par) {
	if(cur) D[cur].push_back(par);
	sort(ALL(D[cur]));
	reverse(ALL(D[cur]));
	FORR(e,E[cur]) if(e!=pre) {
		if(D[cur][0]==D[e][0]+1) dfs2(e,cur,D[cur][1]+1);
		else dfs2(e,cur,D[cur][0]+1);
	}
	D[cur].pop_back();
}

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);
	}
	
	dfs(0,-1);
	dfs2(0,-1,0);
	
	int mi=201010;
	FOR(i,N) {
		set<int> S;
		FORR(e,D[i]) S.insert(e);
		if(S.size()>2) return _P("-1\n");
		if(S.size()==1) mi=min(mi,*S.begin());
	}
	while(mi%2==0) mi/=2;
	cout<<mi<<endl;
	
}

まとめ

最初、1つのパスにした後も長さが偶数の場合さらに畳めることに気が付かなかった。