AtCoder ARC #116 : E - Spread of Information

なんかCodeforcesっぽさを感じる問題。
https://atcoder.jp/contests/arc116/tasks/arc116_e

問題

N頂点からなる木を成す無向グラフと、整数Kが与えられる。
N個中K個の点を選んだ時、どの頂点も選んだ頂点のうちいずれかとの距離がR以下となる最小のRを求めよ。

解法

Rを仮置きして二分探索する。
二分探索では、DFSで頂点が以下のいずれの状態かを管理しよう。

• 近くに選んだ点がなく、あと距離r以内に選んだ点がないといけない
• すでに近くに選んだ点がなく、その影響があと距離rまで及ぶ

選んだ点の影響が及ばず、かつ「あと距離r以内に選んだ点がないといけない」の条件を満たせそうにないタイミングで初めてその点を選択するようにする。

int N,K,V;
vector<int> E[202020];

int need[202020],aff[202020];
int num;

void dfs(int cur,int pre) {
	need[cur]=0;
	aff[cur]=-1;
	
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		if(aff[e]>=0) aff[cur]=max(aff[cur],aff[e]-1);
		if(need[e]>=0) need[cur]=max(need[cur],need[e]+1);
	}
	
	if(aff[cur]>=need[cur]) {
		need[cur]=-1;
	}
	else {
		if(need[cur]>=V) {
			need[cur]=-1;
			aff[cur]=V;
			num++;
		}
		else {
			aff[cur]=-1;
		}
	}
}


int ok(int v) {
	if(v<=0) return 0;
	
	V=v;
	num=0;
	dfs(0,0);
	if(need[0]>=0) num++;
	return num<=K;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	int ret=N;
	for(j=20;j>=0;j--) if(ok(ret-(1<<j))) ret-=1<<j;
	cout<<ret<<endl;
	
}

まとめ

まぁこちらは割とすんなり。