Expert.
Put your skills to the test.

Problem summary

A connected network of N cities has exactly N−1 undirected flight connections. Find all cities minimizing their maximum distance, in number of flights, to any other city.

Constraints

2 ≤ N ≤ 100,000; endpoints are distinct labels from 1 through N.

Worked example

Official sample, transcribed with whitespace restored from the PDF.

7
4 3
2 3
6 2
2 5
1 5
1 7

2
2 5

Solution analysis

1. The flight network is a tree. Its centers are the middle one or two vertices of a longest path. Repeatedly removing all current leaves shortens every longest path from both ends and preserves its middle vertices.
2. Initialize a queue with all degree-one cities. Process one complete queue layer at a time, decrementing neighboring degrees and adding newly exposed leaves to the next layer. Stop when at most two cities remain. These are the centers; sort their labels for output.
3. In the sample, the first leaves are 4,6,7. Removing them exposes 3 and 1. Removing that next layer leaves cities 2 and 5, exactly the middle two vertices of the five-edge path 4−3−2−5−1−7.

Why it works

For any diameter path, a vertex outside its middle has larger maximum distance to one of its endpoints than a middle vertex; the middle vertices attain radius equal to half the diameter rounded up. Thus the tree centers are exactly those middle vertices. Removing every leaf removes one vertex from each end of every diameter and leaves the same middle vertices, until only those one or two vertices remain. Layered leaf pruning therefore returns precisely all optimal cities.

Watch out. Remove an entire leaf layer before checking the remaining count. A two-city tree already has both cities as centers.

An independently written complete program with standard headers.

// Key idea: For any diameter path, a vertex outside its middle has larger maximum distance to one of
// its endpoints than a middle vertex; the middle vertices attain radius equal to half the diameter
// rounded up. Thus the tree centers are exactly those middle vertices.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>graph(n+1);
    vector<int>degree(n+1);
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        ++degree[u];
        ++degree[v];
    }
    queue<int>leaves;
    for(int v=1;v<=n;++v){
        if(degree[v]==1){
            leaves.push(v);
        }
    }
    int remaining=n;
    while(remaining>2){
        int layer=int(leaves.size());
        remaining-=layer;
        while(layer--){
            int v=leaves.front();
            leaves.pop();
            for(int u:graph[v]){
                if(--degree[u]==1){
                    leaves.push(u);
                }
            }
        }
    }
    vector<int>centers;
    while(!leaves.empty()){
        centers.push_back(leaves.front());
        leaves.pop();
    }
    sort(centers.begin(),centers.end());
    cout<<centers.size()<<'\n';
    for(int i=0;i<int(centers.size());++i){
        cout<<(i?" ":"")<<centers[i];
    }
    cout<<'\n';
}