世界树上找米库

时间限制：3秒 空间限制：512M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

PJSK 的虚拟世界有若干个地点，这些地点通过一些道路形成了树形结构。你的目标，就是找到这个世界的“Miku”点。

​ 一共有 $n$ 个地点，它们由 $n-1$ 条长度为 $1$ 的双向道路连成了一棵无根树结构。其中，如果一个地点只延伸出了一条道路，那么这个地点将称为 $Sekai$ 点。

​ $Miku$ 点的定义如下：

• $Miku$ 点一定不是 $Sekai$ 点。
• $Miku$ 点是符合上一个条件的所有地点中，与相距最近的 $Sekai$ 点距离最大的点。

​ 根据以上信息，请你找出所有的 $Miku$ 点吧！

输入描述：

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1\le T\le 10^4)$ 代表数据组数，每组测试数据描述如下：

第一行，输入一个正整数 $n(3\le n\le 2\times 10^5)$ ，表示地点数。
接下来 $n-1$ 行，每行输入两个整数 $u,v(1\le u,v\le n,u\ne v)$ 代表一条双向道路。

对于同一个测试点，保证所有 $n$ 之和不超过 $2\times 10^5$ 。

输出描述：

对于每组数据，第一行输出 $Miku$ 点的个数，第二行按从小到大顺序所有 $Miku$ 点的编号。

示例1

输入：

2
4
1 2
2 3
3 4
10
2 1
3 2
4 3
5 4
6 3
7 5
8 7
9 5
10 2

输出：

2
2 3
1
4

说明：

对于第一组样例，可以得知这棵树为 $1\leftrightarrow 2\leftrightarrow 3\leftrightarrow 4$ ，其中 $1,4$ 号点只延伸出了一条道路，所以它们是 $Sekai$ 点。显然对于 $2,3$ 号点，都只需要经过一条边，就可以到达 其中一个 $Sekai$ 点，所以它们都是 $Miku$ 点。
对于第二组样例：

观察这个图，可以发现除了 $4$ 号点以外，其余要么是 $Sekai$ 点，要么距离最近的 $Sekai$ 点是 $1$ 。而距离 $4$ 号点最近的 $Sekai$ 点是 $6$ 或 $9$ 号点，距离为 $2$ ，所以输出 $4$ 号点。

解题思路

本题核心是通过多源BFS（广度优先搜索） 求解 $Miku$ 点：首先识别所有度数为 $1$ 的 $Sekai$ 点作为 $BFS$ 起点，初始化距离为 $0$ 并标记已访问；从这些起点开始逐层扩展 $BFS$ ，记录每个非 $Sekai$ 点到最近 $Sekai$ 点的距离；遍历过程中维护最大距离值ma，以及距离等于ma的节点集合；最终该集合即为满足“非 $Sekai$ 点且到最近 $Sekai$ 点距离最大”的 $Miku$ 点。多源 $BFS$ 保证每个节点仅被访问一次，时间复杂度为 $O(n)$ ，适配 $n\le 2\times 10^5$ 、总 $n\le 2\times 10^5$ 的规模，通过逐层扩散精准计算每个节点到最近 $Sekai$ 点的距离，筛选出符合定义的所有 $Miku$ 点并按要求输出。

总结

1. 核心逻辑：以所有 $Sekai$ 点为起点做多源 $BFS$ ，计算每个节点到最近 $Sekai$ 点的距离。
2. 关键筛选：保留非 $Sekai$ 点中距离最大的节点，即为 $Miku$ 点。
3. 输出要求：统计 $Miku$ 点数量，按升序输出节点编号。

代码内容

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll N=1e5+10;
const ll p=1e9+7;

void solve()
{
    ll n;
    cin>>n;
    vector<vector<ll>> g(n+1);
    vector<ll> deg(n+1,0);
    for(ll i=1;i<=n-1;i++)
    {
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    vector<ll>ans;
    ll ma=0;
    queue<pair<ll,ll>> q;
    vector<ll>vis(n+1,0);

    for(ll i=1;i<=n;i++)
    {
        if(deg[i]==1)
        {
            q.push({i,0});
            vis[i]=1;
        }
    }

    while(!q.empty())
    {
        ll u=q.front().first;
        ll cnt=q.front().second;
        q.pop();
        if(cnt>ma)
        {
            ans.clear();
            ans.push_back(u);
            ma=cnt;
        }
        else if(cnt==ma) ans.push_back(u);
    
        for(auto &v:g[u])
        {
            if(vis[v]) continue;
            vis[v]=1;
            q.push({v,cnt+1});
        }
    }

    cout<<ans.size()<<"\n";
    sort(ans.begin(),ans.end());

    for(auto c:ans) cout<<c<<' ';
    cout<<"\n";
}

int main()
{
    ll t=1;
    cin>>t;
    
    while(t--) solve();
    return 0;
}