Codeforces ECR #098 : G. Game On Tree

ありそうという意味ではEducationalだ。
https://codeforces.com/contest/1452/problem/G

問題

木を成す無向グラフを用いて、AliceとBobの2人でターン制のゲームを行う。
初期状態でAliceは1頂点、Bobは入力で与えられる複数頂点にトークンを置いている。
各自の手番では、自身の全トークンを同時に隣接頂点に移動できる(移動しなくてもよい)。

AliceのトークンがBobのいずれかのトークンと同じ位置に来たらゲーム終了である。
終了までのターン数について、Aliceは最大化、Bobは最小化を図る場合、Aliceが各点を初期位置としたときの終了ターン数を求めよ。

解法

まずBFSで、以下を求めよう。
D(v)=頂点vから最寄りのBobのトークンまでの距離

Aliceのトークンの初期位置をuとしたとき、dist(u,v)≦D(v)であるようなvにおけるD(v)の最大値が求める値となる。
そこで、逆に、D(v)の大きい順にBFSでdist(u,v)≦D(v)を満たせるuを求めて行くとよい。

int N,K;
vector<int> E[202020];
int D[202020];
int hi[202020];
int ret[202020];
vector<int> cand[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) D[i]=303030;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	queue<int> Q;
	cin>>K;
	FOR(i,K) {
		cin>>x;
		D[x-1]=0;
		Q.push(x-1);
	}
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		cand[D[x]].push_back(x);
		FORR(e,E[x]) if(D[e]>D[x]+1) {
			D[e]=D[x]+1;
			Q.push(e);
		}
	}
	
	for(i=N;i>=0;i--) if(cand[i].size()) {
		queue<pair<int,int>> Q;
		FORR(c,cand[i]) if(hi[c]<D[c]) {
			ret[c]=max(ret[c],i);
			hi[c]=D[c];
			Q.push({D[c],c});
		}
		while(Q.size()) {
			int h=Q.front().first;
			int cur=Q.front().second;
			Q.pop();
			h--;
			if(h==0) continue;
			FORR(e,E[cur]) if(hi[e]<min(D[e],h)) {
				hi[e]=min(D[e],h);
				ret[e]=max(ret[e],i);
				Q.push({hi[e],e});
			}
		}
	}
	FOR(i,N) cout<<ret[i]<<" ";
	cout<<endl;
	
}

まとめ

Fの方がややこしい？