链接：https://ac.nowcoder.com/acm/contest/112543/D 来源：牛客网 一共有 𝑛 n 个地点，它们由 𝑛 − 1 n−1 条长度为 1 1 的双向道路连成了一棵无根树结构。其中，如果一个地点只延伸出了一条道路，那么这个地点将称为 Sekai 点。 Miku 点的定义如下： Miku 点一定不是 Sekai 点。 Miku 点是符合上一个条件的所有地点中，与相距最近的 Sekai 点距离最大的点。 根据以上信息，请你找出所有的 Miku 点吧！ 输入描述: 每个测试文件均包含多组测试数据。第一行输入一个整数 𝑇 ( 1 ≤ 𝑇 ≤ 1 0 4 ) T(1≤T≤10 4 ) 代表数据组数，每组测试数据描述如下： 第一行，输入一个正整数 𝑛 ( 3 ≤ 𝑛 ≤ 2 × 1 0 5 ) n(3≤n≤2×10 5 )，表示地点数。 接下来 𝑛 − 1 n−1 行，每行输入两个整数 𝑢 , 𝑣 ( 1 ≤ 𝑢 , 𝑣 ≤ 𝑛 , 𝑢 ≠ 𝑣 ) u,v (1≤u,v≤n,u  ​ =v) 代表一条双向道路。 对于同一个测试点，保证所有 𝑛 n 之和不超过 2 × 1 0 5 2×10 5 。

<think>首先，用户要求使用中文回答问题。问题来自一个编程竞赛题目，我需要理解并解决它。 题目描述：有一棵树，有 n 个节点和 n-1 条边。Sekai 点定义为度数为 1 的节点（即叶子节点，因为只延伸出一条道路）。Miku 点定义为：不是 Sekai 点（即不是叶子节点），并且在所有非叶子节点中，与最近的 Sekai 点的距离最大。 输入是多组测试数据，每组给一棵树，输出所有的 Miku 点。 关键点： - Sekai 点：度数为 1 的节点（叶子）。 - Miku 点：非叶子节点，且与最近的 Sekai 点的距离最大。 我需要找到所有这样的节点，它们不是叶子，并且 min_distance_to_sekai 是最大的。 由于树是无根树，我需要一种高效的方法来计算每个节点到最近的 Sekai 点的距离。 Sekai 点是叶子节点，所以问题转化为：对于每个非叶子节点，计算它到最近叶子的距离，然后找出那些这个距离最大的节点。 在树中，计算每个节点到最近叶子的距离是一个经典问题。 一种方法是使用 BFS 或多源 BFS。既然所有叶子都是源点，我可以从所有叶子开始做 BFS，计算每个节点到最近叶子的距离。 具体步骤： 1. 识别所有叶子节点（度数为 1 的节点）。 2. 从所有叶子节点开始进行多源 BFS（类似 Dijkstra，但所有边权为 1）。 3. 在 BFS 过程中，记录每个节点的最小距离（即到最近叶子的距离）。 4. 然后，对于所有非叶子节点，找到这个距离的最大值，记作 max_dist。 5. 所有非叶子节点中，距离等于 max_dist 的节点就是 Miku 点。 注意：题目说“Miku 点一定不是 Sekai 点”，所以只考虑非叶子节点。 输入约束：总节点数不超过 200,000，但 T 组数据，所有 n 之和不超过 200,000，所以每组数据平均节点数可能很小，但最坏情况 T 最大 10,000，但 n 之和 <= 200,000，所以每组数据节点数可能很小，比如平均 20 个节点，但 n 从 3 到 200,000，但总和有限，所以算法需要高效。 由于所有 n 之和不超过 200,000，我可以在 O(n) 或 O(n log n) 时间内解决每组数据。 多源 BFS 是 O(n) 的，因为每个边只访问一次。 步骤： 对于每组数据： 1. 读取 n。 2. 读取 n-1 条边，构建图（邻接表），并记录每个节点的度数。 3. 找出所有叶子节点：度数为 1 的节点。 4. 初始化一个队列，将所有叶子节点入队，距离为 0。 5. 初始化一个距离数组，初始为无穷大，叶子节点为 0。 6. 进行 BFS：从队列中取出节点，遍历其邻居，如果邻居的当前距离大于当前节点距离 + 1，则更新邻居的距离，并将邻居入队。 7. BFS 结束后，距离数组存储了每个节点到最近叶子的距离。 8. 然后，找出所有非叶子节点（即度数 > 1 的节点），并计算 max_dist = 这些节点距离的最大值。 9. 最后，输出所有非叶子节点中距离等于 max_dist 的节点。注意可能有多个，需要按顺序输出？题目没说输出顺序，但通常按节点编号升序输出。 输出描述没指定，但应该输出所有 Miku 点的编号。 在输入输出示例中，题目没有给，但我需要输出节点列表。 现在，关于实现：由于是编程问题，用户可能期望代码，但用户的问题是描述性的，要求我回答问题，然后提出相关问题。 用户说：“请使用中文回答问题”，但问题是什么？用户贴了题目链接，但实际问题是“请你找出所有的 Miku 点吧！”，所以我需要解释如何解决这个问题。 用户指令："请使用中文回答问题"，然后贴了题目，所以我应该描述解决方案。 但最后，我必须根据问题和回答提出3-5个相关问题。 格式：回答完问题后，必须输出"§§相关问题§§"，然后列出1. 2. 3. 等。 所以，首先我需要回答问题。 回答：要解决这个问题，我们需要找到树中所有非叶子节点，这些节点到最近叶子节点的距离最大。以下是步骤： 1. 构建树的邻接表并计算每个节点的度数。 2. 识别所有叶子节点（度数为1的节点）。 3. 使用多源BFS从所有叶子节点开始，计算每个节点到最近叶子节点的距离。 4. 在非叶子节点中找到最大距离值。 5. 输出所有距离等于该最大值的非叶子节点。 由于输入包含多组测试数据，且总节点数有限，该算法是高效的。 现在，我需要提出3-5个相关问题。 相关问题应该基于用户的问题和我的回答。 用户的问题是：如何找出所有的Miku点。 所以，相关问题可以涉及： - 算法的复杂度？ - 特殊情况处理？ - 证明为什么这个方法正确？ - 扩展问题，如输出距离值等。 - 树的性质，如直径等。 列出3-5个： 1. 如果树是一条链（即所有节点线性排列），Miku点会是什么？ 2. 在多源BFS中，如何处理多个源点？代码实现细节？ 3. Miku点是否总是存在？在什么情况下只有一个Miku点？ 4. 是否可以不用BFS，而用树形DP解决？ 5. 时间复杂度是多少？如何优化？ 确保问题相关。 现在，写回答。 首先，回答问题。</think>### 问题解答 要解决这个问题，即找出树中所有的 Miku 点，需要遵循以下步骤。Miku 点的定义基于两个关键条件： 1. **不是 Sekai 点**：Sekai 点是度数为 1 的节点（即叶子节点），因此 Miku 点必须是度数为 2 或更高的节点（非叶子节点）。 2. **与最近 Sekai 点的距离最大**：在所有非叶子节点中，Miku 点是那些到最近 Sekai 点（叶子节点）的距离最大的节点。 #### 解决思路 1. **构建树结构**： - 读取输入，包括节点数 \(n\) 和边信息。 - 使用邻接表表示树，并计算每个节点的度数。 2. **识别 Sekai 点**： - Sekai 点即叶子节点，度数为 1 的所有节点。 3. **计算每个节点到最近 Sekai 点的距离**： - 使用**多源 BFS**（广度优先搜索）从所有 Sekai 点（叶子节点）开始，初始化队列，距离为 0。 - 遍历树，更新每个节点的最小距离（到最近叶子的距离）。 - 算法伪代码： ```python # 初始化距离数组 dist，所有节点初始为无穷大 dist = [float('inf')] * (n+1) queue = deque() # 将所有叶子节点（Sekai 点）入队，距离设为 0 for i in range(1, n+1): if degree[i] == 1: dist[i] = 0 queue.append(i) # 多源 BFS while queue: u = queue.popleft() for v in graph[u]: if dist[v] > dist[u] + 1: dist[v] = dist[u] + 1 queue.append(v) ``` 4. **找出 Miku 点**： - 遍历所有非叶子节点（度数 > 1），找到距离的最大值 `max_dist`。 - 输出所有距离等于 `max_dist` 的非叶子节点（按节点编号升序排序，以符合常规输出要求）。 #### 复杂度分析 - **时间复杂度**：每组数据 \(O(n)\)，其中 \(n\) 是节点数。多源 BFS 每个节点和边只访问一次。 - **空间复杂度**：\(O(n)\)，用于存储图、距离数组和队列。 - 总约束：所有测试数据的 \(n\) 之和不超过 \(2 \times 10^5\)，因此算法高效可行。 #### 示例说明 对于一棵树（例如链状结构），Sekai 点是端点叶子，Miku 点通常是中心节点。例如，节点数为 5 的链：1-2-3-4-5，Sekai 点为 1 和 5，Miku 点为 3（距离最近 Sekai 点为 2）。 在实际代码实现中，需处理多组测试数据，并确保输出所有 Miku 点（可能多个）。