mayoko’s diary

プロコンとかいろいろ。

AtCoder Grand Contest 001 C - Shorten Diameter(その2)

AtCoder
問題

agc001.contest.atcoder.jp

解法

想定解のほうで解きます。

木の直径周りではいろんな定理が成り立っていて, この辺りは知っておいた方が良いかもしれません。

定義

  • 頂点 v からの距離が最大の点との距離が最小であるような頂点を木の中心という。
  • 木の中心からの距離が最大のものを, 木の半径という。

定理

  • 木の中心は隣接する。
  • 木の中心は 1 つか 2 つである。
  • 木の直径をなす任意の頂点の組 (u, v) は, u から v に行くために木の中心を通る。

以上のことを使うと, この問題の解説(https://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf)に書いてあったことがいろいろとわかります。

木の中心が 1 つの時と 2 つの時で場合分けします。

木の中心が一つの時
木の中心を c とします。また, 木の半径を R とします。
c を根として木を作ると, c の子で深さが R-1 より大きい部分木が存在しないことがわかります。なぜなら, そうでないと木の半径が R を超えてしまうからです。
また, c の子で, 深さが R-1 であるような部分木が, 必ず 2 つ以上存在します。これは背理法で示します。

深さが R-1 のものが一つもない場合は, 明らかに半径が R 未満になるのでダメです。
深さが R-1 のものが 1 しかない場合, その部分木の頂点になっている c の子を ch とします。ch における各頂点との距離を考えると,

  • ch の子とは距離が R-2 以下
  • ch - c - (c の ch 以外の子) というルートをたどる頂点との距離は 2 + (R-2 以下) なので R 以下

よって, 木の中心は c でないか, 木の中心が c, ch の二つあることになります。これは矛盾です。

以上より, 深さが R-1 であるような部分木が 2 つ以上存在します。このことから, 木の直径は 2*R で偶数です。

木の中心が 2 つの時
木の中心は隣接しています。これらを c, d とします。また, 木の半径を R とします。

c の子, d の子それぞれで, 深さが R-1 以上であるような部分木は存在しません。例えば d の子に深さ R-1 の部分木があったとすると, c -> d -> (部分木) というルートで距離が R+1 になってしまうので, 半径が R でなくなります。
また, c, d の子で深さが R-2 以上であるような部分木が, 少なくとも一つずつ存在します。これはまぁ上と同じですね。こうしないと c から距離 R の頂点が存在しなかったりします。
これを考えると, 木の直径は 2*(R-1) + 1 = 2*R-1 で奇数です(+1 は c-d 間の距離)。

以上から, この問題の解法として,

  • K が偶数なら木の中心は 1 つ, その頂点からの距離がすべて K/2 以下になるようにすれば, 木の直径は K 以下になる
  • K が奇数なら木の中心は 2 つ, それらの頂点からの距離がすべて (K-1)/2 以下になるようにすれば, 木の直径は K 以下になる

ということがわかります。

struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}


const int MAXN = 2222;
int A[MAXN], B[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	vector<vector<edge> > G(N);
	for (int i = 0; i < N - 1; i++) {
		cin >> A[i] >> B[i];
		A[i]--; B[i]--;
		G[A[i]].emplace_back(B[i], 1);
		G[B[i]].emplace_back(A[i], 1);
	}
	int ans = N;
	if (K % 2 == 0) {
		for (int i = 0; i < N; i++) {
			auto d = dijkstra(N, G, i);
			int cnt = 0;
			for (int j = 0; j < N; j++) {
				if (d[j] > K / 2) cnt++;
			}
			ans = min(ans, cnt);
		}
	}
	else {
		for (int i = 0; i < N - 1; i++) {
			auto da = dijkstra(N, G, A[i]);
			auto db = dijkstra(N, G, B[i]);
			int cnt = 0;
			for (int j = 0; j < N; j++) {
				if (min(da[j], db[j]) > (K - 1) / 2) cnt++;
			}
			ans = min(ans, cnt);
		}
	}
	cout << ans << endl;
    return 0;
}