Codeforces #408 Div2 D. Police Stations

今回E,Fが厳しくない？
http://codeforces.com/contest/796/problem/D

問題

木を成すグラフが与えられる。
N頂点中、K頂点は特殊な頂点である。
各頂点から、距離D以内に少なくとも1の頂点があるような状態を維持したまま、辺の数をできるだけ減らしたい。
減らす辺の候補を答えよ。

解法

以下を考える。
F(v) := 頂点vにおける、最寄りの特殊頂点からの距離

F(v)を最小に押さえるためには、vの隣接点v'のうちF(v')が最小となるv'から移動してくるのが良い。
よって、特殊な頂点から、BFSで未到達の隣接点を探索し、そこに至る辺を残していこう。
以下のコードは律儀にF(v)を記録してしまったが、辺の距離が一定な上探索順がBFSであり自動的にF(v)が小さい順に辿るので、F(v)を覚える必要はない。

int N,K,D;
int P[303030];
int dist[303030];
vector<pair<int,int>> E[303030];
int used[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>D;
	MINUS(dist);
	queue<int> Q;
	FOR(i,K) {
		cin>>x;
		dist[x]=D;
		Q.push(x);
	}
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back({y,i});
		E[y].push_back({x,i});
	}
	int unused=N-1;
	while(Q.size()) {
		int c = Q.front();
		Q.pop();
		if(dist[c]==0) continue;
		FORR(e,E[c]) if(dist[e.first]<0) {
			dist[e.first] = dist[c]-1;
			Q.push(e.first);
			used[e.second]=1;
			unused--;
		}
	}
	_P("%d\n",unused);
	FOR(i,N-1) if(used[i]==0) _P("%d ",i+1);
	_P("\n");
		
}

まとめ

これはすんなり思いついた。