Codeforces ECR #143 : F. Blocking Chips

コードはそんなに長くないけどね。
https://codeforces.com/contest/1795/problem/F

問題

木を成すグラフが与えられる。
また、K個の駒を置く頂点が指定される。

今から駒を動かすが、iターン目には0-originで(i%K)個めの駒を隣接点に動かす。
ただし、途中で過去に駒が存在していたことのある点に駒を動かすことはできない。
最大何ターン駒を動かすことができるか。

解法

最大ターン数Mを二分探索しよう。
そうすると、片方の端点と長さの決められたK個のパスをグラフ内に構築できるか判定する問題になる。
これはDFSで最長どれだけの空き頂点が連続するか、もしくは親方向にどれだけの空き頂点を必要とするかを求めて行けばよい。

int T,N;
vector<int> E[202020];
int K;
int C[202020];
vector<int> A;
int ok;
int dfs(int cur,int pre) {
	int ma=0;
	int req=C[cur];
	FORR(e,E[cur]) if(e!=pre) {
		int ret=dfs(e,cur);
		if(ret<0) {
			if(req) {
				ok=0;
				return 0;
			}
			req=-ret;
		}
		else {
			ma=max(ma,ret);
		}
	}
	if(req==0) return ma+1;
	else if(req<=ma+1) return 0;
	else return -req+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();
			C[i]=0;
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		cin>>K;
		A.resize(K);
		FOR(i,K) {
			cin>>x;
			A[i]=x-1;
		}
		int L=0,R=N-K+1;
		while(L+1<R) {
			int M=(L+R)/2;
			FOR(i,K) C[A[i]]=1;
			FOR(i,M) C[A[i%K]]++;
			ok=1;
			if(dfs(0,0)>=0&&ok) L=M;
			else R=M;
		}
		cout<<L<<endl;
	}
}

まとめ

結果だけ先見るとそこまで難しくないな。