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

本题的本质是一个典型的无向树上最短路径极值问题。

拓扑结构映射：

• 给定结构为 个节点、 条边的连通图，保证了其无根树（Unrooted Tree）的严格数学性质。
• Sekai 点的定义“只延伸出一条道路的地点”，在图论中等价于树的叶子节点（度数为 1 的节点）。
• Miku 点的定义为：在非叶子节点中，到最近叶子节点的距离最大的节点网络集合。这可以理解为寻找树中“最深”或“被包裹最厚实”的核心节点集。

多源广度优先搜索 (Multi-source BFS)

求解“所有非叶子节点到最近叶子节点的距离”，若从非叶子节点出发寻找叶子，属于多对多求解，存在大量的路径重叠计算。

通过逆向思维，可将目标转化为：“从所有叶子节点同时出发，向网络内部扩散，求到达各节点的最短距离”。这正是多源广度优先搜索（Multi-source BFS）的标准应用场景。

1. 并行扩散模拟：将所有 Sekai 点（叶子）视为初始波源，水波每经过一条边耗时为 1。任意内部节点首次被波及的时间，即为它到最近波源的最短距离。
2. 单阶段线性收敛：BFS的队列机制天然保证了按距离递增的顺序访问图，每个节点仅需被访问（松弛）一次，即可确定其全局最短距离。

为什么不选择树形 DP？

虽然换根 DP （两次 DFS 扫描）也能在 时间内解决树上距离问题，但本题仅关注“到最近叶子”的距离，多源 BFS 的状态机远比树形 DP 简单。且 BFS 的迭代模型规避了深层递归带来的栈溢出（Stack Overflow）风险，内存访问也具备更好的局部性（Cache Locality）。

复杂度分析

• 时间复杂度：

  • 构建邻接表与统计节点度数：遍历 条边，为 。
  • 多源 BFS 遍历：每个节点最多入队出队一次，每条边最多被访问两次，时间复杂度严格为 。
  • 极值筛选：线性扫描非叶子节点得出最大距离，为 。
  • 结果排序：Miku 点的数量设为 （），排序时间为 。
  • 整体时间复杂度：。

• 空间复杂度：

  • 邻接表存储树结构：需要 空间。
  • 状态数组（度数数组、距离数组）：均为长为 的一维结构，各耗费 空间。
  • BFS 队列容器：极端情况下（星型拓扑），队列大小为 。
  • 整体空间复杂度：。

代码实现

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

static constexpr int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<vector<int>> adj(n + 1);
        vector<int> deg(n + 1, 0);

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

        queue<int> Q;
        vector<int> dist(n + 1, INF);
        for (int i = 1; i <= n; i++) {
            if (deg[i] == 1) {
                Q.push(i);
                dist[i] = 0;
            }
        }

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int v : adj[u]) {
                if (dist[v] == INF) {
                    Q.push(v);
                    dist[v] = dist[u] + 1;
                }
            }
        }

        vector<int> ans;
        int maxDist = -1;
        for (int i = 1; i <= n; i++) {
            if (dist[i] > maxDist) {
                ans.clear();
                maxDist = dist[i];
                ans.push_back(i);
            } else if (dist[i] == maxDist) {
                ans.push_back(i);
            }
        }

        cout << ans.size() << endl;
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i];
            if (i == ans.size() - 1)
                cout << "\n";
            else
                cout << " ";
        }
    }
}