机器选择(Machine Selection) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    auto bfs = [&](int start) {
        vector<int> dist(n + 1, -1), q;
        q.reserve(n);
        dist[start] = 0;
        q.push_back(start);
        int far = start;
        for (size_t head = 0; head < q.size(); ++head) {
            int u = q[head];
            if (dist[u] > dist[far]) far = u;
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push_back(v);
                }
            }
        }
        return make_pair(far, dist[far]);
    };
    int u = bfs(1).first;
    int diam = bfs(u).second;
    cout << (diam + 1) / 2 << "\n";
    return 0;
}