题解 | 世界树上找米库

这下不能再偷懒不打卡了（

/* 以下，是我的胡扯（bushi）时间，可以略过

很简单，这道题我们只需套一个背景：

Miku想用歌声统治全世界，于是在前几年举行了全球巡演。现在想要回顾一下，前几年选取的巡演场地，是不是真的已经覆盖了全世界呢？Miku想用一个数值来表示（未覆盖度），即世界上所有点距离最近的巡演场地的最大值。Miku想要找到所有“未覆盖度”最高的点，为进一步统治世界做准备。

*/

那么，咱们可以以每个巡演场地（即叶子节点）为起点，跑一个多源BFS，此处可以下面的参考代码，dis[i]即表示该点距离最近的巡演场地（即叶子节点）的最大值。我们跑完多源bfs之后扫一遍dis数组即可。

// 我平时头文件就长这样（
#include <bits/stdc++.h>
#define ll long long
#define PII pair<ll, ll>
#define PLL pair<ll, ll>
#define pb push_back
#define all(a) a.begin(), a.end()
#define all1(a) a.begin()+1, a.end()
#define endl '\n'
using namespace std;
const ll inf = (ll)2e18+9;
const ll MOD = 998244353;

inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}

template<typename Array> void printvec(Array vec) { for (auto it = vec.begin(); it != vec.end(); ++it) { cout << *it << " ";} cout << endl;}
template<typename Array> void printvec1(Array vec) { for (auto it = vec.begin()+1; it != vec.end(); ++it) { cout << *it << " ";} cout << endl;}
template<typename Array> void print2dvec(const Array& vec) { for (const auto& row : vec) { for (const auto& element : row) { cout << element << " ";}cout << endl;}}
void printPII(vector<PII> vec) { for (auto it = vec.begin(); it != vec.end(); ++it) { cout << (*it).first << "->" << (*it).second << " ";} cout << endl;}
void printPIII(vector<pair<ll, PII>> vec) { for (auto it = vec.begin(); it != vec.end(); ++it) { cout << (*it).second.first << "/" << (*it).second.second << "\n";}}
void printvecmap(const map<ll, vector<ll>>& g) {for (const auto& [key, value] : g) { cout << "key: " << key << " -> ";for (const auto& v : value) {cout << v << " ";}cout << endl;}}
void printmap(const map<ll, ll>& g) { for (const auto& [key, value] : g) { cout << "key: " << key << " -> " << value << " ";}cout << endl;}
ll ksm(ll a, ll b) {ll res = 1; while (b) {if (b & 1) {res = (res * a) % MOD;} a = (a * a) % MOD; b >>= 1;} return res;}
ll fpw(ll a, ll b) {ll res = 1; while (b) {if (b & 1) {res = (res * a) % MOD;} a = (a * a) % MOD; b >>= 1;} return res;}

void MIKUUUUUU() {
    ll n;
    cin >> n;
    vector<vector<ll>> g(n+1); // 邻接表

    for (int i = 1; i <= n-1; i++) {
        ll u, v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
    }

    queue<ll> que; 
    vector<ll> dis(n+1, inf), vis(n+1, 0); // 距离数组初始化为 inf，访问数组初始化为 0
    ll mx = 0; // 记录距离最大值
    for (int i = 1; i <= n; i++) {
        if (g[i].size() == 1) { // 是叶子节点，即Sekai点，放入多源bfs起始队列
            que.push(i); 
            vis[i] = 1;
            dis[i] = 0;
        }
    }
    
    while (!que.empty()) {
        ll u = que.front(); que.pop();
        mx = max(mx, dis[u]);
        for (auto v: g[u]) { // 访问所有邻接节点
            if (!vis[v]) { // 如果节点未被访问
                dis[v] = dis[u]+1;
                que.push(v); 
                vis[v] = 1;
            }
        }
    }  
    vector<ll> miku; // 存储所有的miku点
    for (int i = 1; i <= n; i++) {
        if (dis[i] == mx) miku.pb(i);
    }
    cout<<miku.size()<<endl;
    printvec(miku);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    ll tt; cin >> tt; while (tt--)
        MIKUUUUUU();
    return 0;
}