UVa 1267 Network

問題

無向木で表されるネットワークがある。
木の内点はサーバで、葉はノードである。
サーバのうち番号sのサーバがオリジナルのサーバである。

オリジナル以外のサーバにいくつかソフトをインストールして、
全ての葉について、オリジナルもしくはソフトのインストールされた最も近いサーバへの距離がk以内となるようにしたい。


必要なソフトのインストールをすべきサーバの台数の最小値を求めよ。

制約条件

木の頂点≦1000

方針

sのサーバを根として考える。
最も深さの深いノードvに最も近いソフトの位置を考える。
これは、vからちょうどkだけ根のほうへ辿ったサーバである。
なぜなら、そのように置いてもより浅いノードはそのソフトから辿れるため、損がないから。


というわけで、まだカバーされていない最も深いノードから、kだけ根に向かったノードに貪欲にソフトをインストールしていけばいい。

ソフトをインストールしたら、そのノードから距離k以内にある葉は全てカバー済みにする。
木上の距離は最小共通先祖などを使ってO(log n)くらいで求める。


2^k親を覚えておくタイプの最小共通先祖の求め方を使えば、
kだけ根に向かったノードもO(log n)で求められる。

ソースコード

int n, s, k, p[10][1000];
int ls[1000], m, depth[1000];
bool ok[1000];
vector<vi> e;

void rec(int c, int pa, int d){
	p[0][c] = pa;
	depth[c] = d;
	int cnt = 0;
	rep(i, e[c].size()) if(p[0][e[c][i]] == -1){
		rec(e[c][i], c, d + 1);
		cnt++;
	}
	if(cnt == 0) ls[m++] = c;
}
int dist(int a, int b){
	int res = 0;
	if(depth[a] > depth[b]) swap(a, b);
	while(depth[b] > depth[a]) b = p[0][b], res++;
	if(a == b) return res;
	int A = a;
	for(int i = 9; i >= 0; i--) if(p[i][a] != p[i][b]){
		a = p[i][a]; b = p[i][b];
	}
	a = p[0][a];
	res += (depth[A] - depth[a]) * 2;
	return res;
}

int main()
{
	int cs;
	cin >> cs;
	while(cs--){
		cin >> n >> s >> k;
		s--;
		e.clear(); e.resize(n);
		rep(i, n - 1){
			int a, b;
			cin >> a >> b;
			e[--a].pb(--b); e[b].pb(a);
		}
		memset(p, -1, sizeof(p));
		memset(ok, 0, sizeof(ok));
		m = 0;
		rec(s, -2, 0);
		p[0][s] = s;
		rep(i, 9) rep(j, n) p[i + 1][j] = p[i][p[i][j]];
		rep(i, m) if(dist(ls[i], s) <= k) ok[ls[i]] = 1;
		
		priority_queue<pi> q;
		rep(i, m) if(!ok[ls[i]]) q.push(mp(depth[ls[i]], ls[i]));
		int ans = 0;
		while(!q.empty()){
			int c = q.top().second;
			q.pop();
			if(ok[c]) continue;
			ans++;
			for(int i = 9; i >= 0; i--) if(k & 1 << i) c = p[i][c];
			rep(i, m) if(!ok[ls[i]] && dist(ls[i], c) <= k) ok[ls[i]] = 1;
		}
		cout << ans << endl;
	}
	return 0;
}