题解 | 世界树上找米库

根据题意，我们需要找到与相距最近的 Sekai 点距离最大的点且不是Sekai点的点

容易得出,我们要求出每个点距离Sekai点的最短距离，有点像最短路问题，我们将所有Sekai点当作源点进行bfs

创建一个dist数组初始化为INF，如果一个点的出度为1，那这个点就是Sekai点，我们就将这个点放入队列中，让后将这个点的dist=0

然后求出每个点到Sekai点的最短距离，并且用ans记录最大值

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << ": " << x << '\n';
const int INF = 0x3f3f3f3f3f3f3f3f;
void solve(){
    int n;cin>>n;
    vector<vector<int>> e(n+1);
    vector<int> dist(n+1,INF);
    int ans=-1;
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(e[i].size()==1){
            dist[i]=0;
            q.push(i);
        }
    }
    while(q.size()){
        auto cur=q.front();q.pop();
        for(auto x:e[cur]){
            if(e[x].size()==1) continue;
            if(dist[cur]+1>=dist[x]) continue;
            dist[x]=dist[cur]+1;
            ans=max(dist[x],ans);
            q.push(x);
        }
    }
    vector<int> res;
    for(int i=1;i<=n;i++){
        if(dist[i]==ans){
            res.push_back(i);
        }
    }
    sort(res.begin(),res.end());
    cout<<res.size()<<"\n";
    for(auto i:res) cout<<i<<' ';
    cout<<"\n";
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    cin>>t;
    while(t--){
        solve();
    }return 0;
}