题解 | #世界树上找米库#

题目描述

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

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

Miku 点的定义如下：

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

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

本题是考察多源 BFS（从所有叶子出发）与树的中心性质的题，难度中等

核心思路

核心观察

• Sekai 点 = 叶子节点（度为 1 的点）。
• 对每个非叶子节点，我们关心的是它到最近 Sekai 点的距离。
• 问题转化为：在所有非叶子节点中，找出“到最近叶子距离”最大的那些点。
• 这可以通过 多源 BFS 实现：将所有叶子（Sekai 点）作为初始源点（距离为 0），同时向外扩展，第一次到达某点时的距离即为该点到最近叶子的距离。

算法步骤

1. 建图，并统计每个点的度数（或直接用邻接表大小判断是否为叶子）。
2. 初始化距离数组 len 为无穷大，将所有 Sekai 点（deg[i] == 1）加入 BFS 队列，len[i] = 0。
3. 执行多源 BFS：
   • 每次从队列取出节点 ，
   • 遍历其邻居 ，若 未被访问（len[v] == INF），则更新 len[v] = len[u] + 1 并入队。
4. 在 BFS 过程中（或结束后），遍历所有非 Sekai 点，找出最大距离 maxd。
5. 收集所有满足 len[i] == maxd 且 deg[i] > 1 的点，排序后输出。

正确性分析

• 多源 BFS 保证每个点第一次被访问时，其距离即为到最近源点（Sekai 点） 的最短距离。
• 树是无环连通图，任意两点间路径唯一，因此 BFS 不会因环导致错误更新。
• 由于 BFS 按层扩展（距离非递减），在遍历过程中动态维护最大距离和结果集合是安全的（最后处理的非叶子节点具有最大距离）。
• 排除 Sekai 点（len[u] != 0 或 deg[u] > 1）确保 Miku 点定义被严格满足。

复杂度分析

• 时间复杂度：
  • 建图 ，BFS 遍历每条边一次 ，收集答案 （因使用 set 自动排序）。但题目保证所有测试数据的 总和 ，实际运行效率高。
• 空间复杂度：
  • 邻接表、距离数组、队列等均使用线性空间。

参考代码

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

void solve(){
    int n,ans=0;cin>>n;//答案的值
    vector<int>len(n+1,1e9);//最短距离
    vector<vector<int>>graph(n+1,vector<int>());//邻接矩阵
    set<int>res;//答案数组

    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    deque<int>bfs;
    for(int i=1;i<=n;i++) if(graph[i].size()==1) bfs.push_back(i),len[i]=0;//初始化bfs

    while(!bfs.empty()){
        int u=bfs.front();
        bfs.pop_front();

        for(auto &v:graph[u]){
            if(len[v]==1e9){//初次访问必为最小
                len[v]=len[u]+1;
                bfs.push_back(v);
            }
        }
        if(len[u]!=0&&len[u]>ans){
            res.clear();
            res.insert(u);
            ans=len[u];
        }
        if(len[u]==ans)res.insert(u);
    }

    cout<<res.size()<<endl;
    for(auto &i:res)cout<<i<<" ";
    cout<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--){
        solve();
    }
}