Codeforces #318 Div1 C. Bear and Drawing

本番これだいぶ時間ぎりぎりにSubmitして、あまり自信なかったけど通ってよかった。
http://codeforces.com/contest/573/problem/C

問題

木を成す無向グラフが与えられる。

ここで、縦2列で横に無限個の点が並んだ点列がある。
与えられたグラフの頂点をそれぞれこの点列に対応づけ、グラフの辺は点の間を線分で結ぶことで、点列上にこのグラフを配置したい。
この時、辺同士が交差しないような頂点配置は可能か答えよ。

解法

条件を満たさないケースを考えてみる。
ある頂点に注目し、それをVとする。
Vを根としてみたとき、Vにつながる辺の先の頂点のサブツリーにおいて3辺以上がつながる頂点がある、というような辺が3つ以上あるとする。
そのようなサブツリーから3つを選び、それぞれ対応するVの隣接点をL,R,Xとする。

Vを上の段のある点に対応付け、L,Rを上の段においてVの左・右に配置したとする。(Vの隣ではなく離してもよい)
L,Rはそのサブツリー上で3辺がつながる頂点があるので、その先どこかで下の列の頂点とつながることになる。

とすると、X及びそのサブツリーは下の段だけで配置しなければならなくなる。

• Xが4辺以上とつながる
• Xの先に、3辺以上つながる点がある

のいずれかを満たす場合、Xのサブツリーを下の段に配置しきれない。

Vの隣接点において、Xに相当する頂点が2個までならそれをL,Rのように上段に置くことができるが、3個になると1つは下段に置く必要があり条件を満たせなくなる。

ここまでをまとめると、以下のような頂点Vがないならば条件を満たす頂点配置は可能である。

• Vを根とした木において、その隣接点のサブツリーに3辺以上つながる点が1個以上あるようなものが3個以上ある
• そのうち、上記下の段に配置しきれないXに該当する隣接点が3個以上ある

コードは意外と単純で、1回目のDFSで前者をチェックし、2回目で前者に当たる点Vに対し後者を判定している。

int N;
vector<int> E[101010];
int have3[101010];

int dfs(int cur,int pre) {
	FORR(tar,E[cur]) if(tar!=pre) have3[cur]+=dfs(tar,cur);
	return have3[cur] += (E[cur].size()>=3);
}

void dfs2(int cur,int pre,int n3) {
	
	int ng=(n3>=2 || (n3==1 && pre!=-1 && (E[pre].size()==2 || E[pre].size()==4)));
	FORR(tar,E[cur]) if(tar!=pre) if(have3[tar]>=2 || (have3[tar]==1 && (E[tar].size()==2||E[tar].size()==4))) ng++;
	if(ng>=3) _P("No\n"), exit(0);
	FORR(tar,E[cur]) if(tar!=pre) dfs2(tar,cur,have3[cur]+n3-have3[tar]);
}


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);
	_P("Yes\n");
}

まとめ

これテストケース作るのめんどくさそう。