mayoko’s diary

プロコンとかいろいろ。

AtCoder Grand Contest 001 C - Shorten Diameter

解法

よくわからない理論で通ってしまったので後で想定解も書きます。ここでは本番に自分が書いた解法を書きます。

頂点 v が, 木の直径をなす一つの頂点であるとします。

このとき, v は葉になっていないといけないので, v から伸びる辺の数が 1 になるように調整します。

で, このもとで v からの距離が K 以下のものだけを残します。また, 距離が K 以下の頂点のうち, 最も v から離れている頂点 u を選びます。この v, u からの距離がどちらも K 以下である頂点だけを残します。

というのを v について全探索して消す頂点数が最小のものを選びます。

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

void dfs(int v, int p, vi& vs, const vector<vector<edge> >& G) {
    vs.push_back(v);
    for (auto e : G[v]) if (e.v != p) {
        dfs(e.v, v, vs, G);
    }
}

ll dist[2222][2222];

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++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].emplace_back(v, 1);
        G[v].emplace_back(u, 1);
    }
    for (int i = 0; i < N; i++) {
        auto d = dijkstra(N, G, i);
        for (int j = 0; j < N; j++)
            dist[i][j] = d[j];
    }
    int ans = N;
    for (int i = 0; i < N; i++) {
        int leaf = -1, maxi = 0;
        for (auto e : G[i]) {
            int ch = e.v;
            vi vs;
            dfs(ch, i, vs, G);
            int sz = vs.size();
            int cnt = N-sz-1;
            vi exist;
            for (int v : vs) {
                if (dist[i][v] > K) cnt++;
                else {
                    exist.push_back(v);
                    if (maxi < dist[i][v]) {
                        maxi = dist[i][v];
                        leaf = v;
                    }
                }
            }
            for (int v : exist) {
                if (dist[leaf][v] > K) cnt++;
            }
            ans = min(ans, cnt);
        }
    }
    cout << ans << endl;
    return 0;
}