Codeforces #1060 : Div2. D. Catshock

こちらは割とすんなりかも。
https://codeforces.com/contest/2154/problem/D

問題

木を成す無向グラフが与えられる。
初期状態でネコが頂点1にいる。
以下の２種類の処理を計3N回まで用いて、ネコが頂点Nにいるようにせよ。

• ネコを隣接点のいずれかに移動させる。どの隣接点に移動するかはランダムである。
• １つ頂点を選択し、辺と共に削除する。その際、ネコがその頂点にいる場合、ネコが消滅してしまう。

解法

グラフを二部グラフをみなすと、ネコがどちらのグループにいるかが確定する。
ネコがいないグループの葉をどんどん消していけばよい。

int T,N;
set<int> E[202020];
int D[202020];

void dfs(int cur,int pre,int d) {
	D[cur]=d;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,d^1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].insert(y-1);
			E[y-1].insert(x-1);
		}
		dfs(0,0,0);
		set<int> C[2];
		FOR(i,N-1) if(E[i].size()==1) C[D[i]].insert(i);
		vector<int> ret;
		int cur=0;
		int del=0;
		while(del<N-1) {
			if(C[cur^1].empty()) {
				ret.push_back(-1);
				cur^=1;
			}
			else {
				x=*C[cur^1].begin();
				C[cur^1].erase(x);
				y=*E[x].begin();
				E[y].erase(x);
				ret.push_back(x);
				del++;
				if(y!=N-1&&E[y].size()==1) {
					C[cur].insert(y);
				}
				ret.push_back(-1);
				cur^=1;
			}
		}
		cout<<ret.size()<<endl;
		FORR(a,ret) {
			if(a==-1) cout<<1<<endl;
			else cout<<2<<" "<<a+1<<endl;
		}
	}
}

まとめ

こちらはすんなりだったね。