Codeforces #866 : Div1 C. The Fox and the Complete Tree Traversal

よくいろいろ問題考えるよね。
https://codeforces.com/contest/1819/problem/C

問題

根付き木を成す無向グラフが与えられる。
距離1又は2の頂点へのジャンプを繰り返し、根頂点から初めて、他の全点を1回ずつジャンプで到達して、最後根頂点に戻る経路があるか。
あるならその一例を示せ。

解法

木DPで、各SubTreeに対し、根頂点の親側から、根頂点に2回着地せずSubTree内を全部訪問可能か見て行くと良い。

int N;
vector<int> E[202020];
int dp[202020];
int C[202020];
int D[202020];
int dfs(int cur,int pre) {
	C[cur]=1;
	if(cur!=pre) D[cur]=D[pre]+1;
	
	int nm=0;
	int x=1;
	FORR(e,E[cur]) if(e!=pre) {
		x=dfs(e,cur);
		C[cur]+=C[e];
		if(C[e]>1) nm++;
		if(x==0) return 0;
	}
	
	if(nm>1+(D[cur]==1)) return 0;
	return 1;
}

vector<int> V;

void dfs2(int cur,int pre,int order) {
	
	if(D[cur]==1) {
		
		FORR(e,E[cur]) if(e!=pre&&C[e]>1) {
			dfs2(e,cur,0);
			C[e]=0;
			break;
		}
		V.push_back(cur);
		FORR(e,E[cur]) if(e!=pre&&C[e]>1) {
			dfs2(e,cur,1);
		}
		FORR(e,E[cur]) if(e!=pre&&C[e]==1) {
			V.push_back(e);
		}
	}
	else {
		if(order==0) {
			V.push_back(cur);
			FORR(e,E[cur]) if(e!=pre&&C[e]>1) {
				dfs2(e,cur,1);
			}
			FORR(e,E[cur]) if(e!=pre&&C[e]==1) {
				V.push_back(e);
			}
		}
		else {
			FORR(e,E[cur]) if(e!=pre&&C[e]==1) {
				V.push_back(e);
			}
			FORR(e,E[cur]) if(e!=pre&&C[e]>1) {
				dfs2(e,cur,0);
			}
			V.push_back(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);
	}
	
	FOR(i,N) if(E[i].size()==1) break;
	x=dfs(i,i);
	if(x==0) {
		cout<<"No"<<endl;
		return;
	}
	
	dfs2(E[i][0],i,1);
	cout<<"Yes"<<endl;
	FORR(v,V) cout<<v+1<<" ";
	cout<<i+1<<endl;
	
	
}

まとめ

解法が思いついても、細かい条件判定とか地味に手間取る問題。