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; }