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

题目链接

世界树上找米库

题目描述

给定一棵 $n$ 个点、 $n-1$ 条边的无根树。若某点度数为 $1$ ，称为 Sekai 点（叶子）。Miku 点需满足：

不是 Sekai 点；
在所有满足上一条件的点中，其到最近 Sekai 点的距离最大。

要求输出每组数据中所有的 Miku 点。

输入：

第一行一个整数 $T$ ，表示数据组数
对于每组数据：第一行一个整数 $n$ ；接下来 $n-1$ 行，每行两个整数 $u$ 、 $v$ 表示无向边

输出：

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

解题思路

设 $d(u)$ 为点 $u$ 到最近 Sekai 点（叶子）的最短距离。按边权均为 $1$ 计算。

用所有叶子作为多源 BFS 的起点，计算全图到最近叶子的距离 $d(u)$ 。
Miku 点即满足度数 $\ge 2$ 且 $d(u)$ 在这类点中取最大值的所有点。
复杂度：建图与 BFS 为 $\mathcal{O}(n)$ ；枚举统计为 $\mathcal{O}(n)$ 。

代码

c++
java
python

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

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

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; cin >> n;
        vector<vector<int>> g(n + 1);
        vector<int> deg(n + 1, 0);
        for (int i = 0; i < n - 1; ++i) {
            int u, v; cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
            deg[u]++; deg[v]++;
        }
        // multi-source BFS from all leaves
        const int INF = 1e9;
        vector<int> dist(n + 1, INF);
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (deg[i] == 1) {
                dist[i] = 0;
                q.push(i);
            }
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (dist[v] == INF) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        int maxd = -1;
        for (int i = 1; i <= n; ++i) if (deg[i] >= 2) maxd = max(maxd, dist[i]);
        vector<int> ans;
        for (int i = 1; i <= n; ++i) if (deg[i] >= 2 && dist[i] == maxd) ans.push_back(i);
        cout << ans.size() << "\n";
        for (int i = 0; i < (int)ans.size(); ++i) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << "\n";
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            List<Integer>[] g = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
            int[] deg = new int[n + 1];
            for (int i = 0; i < n - 1; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                g[u].add(v); g[v].add(u);
                deg[u]++; deg[v]++;
            }
            final int INF = (int)1e9;
            int[] dist = new int[n + 1];
            Arrays.fill(dist, INF);
            ArrayDeque<Integer> q = new ArrayDeque<>();
            for (int i = 1; i <= n; i++) if (deg[i] == 1) { dist[i] = 0; q.add(i); }
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : g[u]) {
                    if (dist[v] == INF) {
                        dist[v] = dist[u] + 1;
                        q.add(v);
                    }
                }
            }
            int maxd = -1;
            for (int i = 1; i <= n; i++) if (deg[i] >= 2) maxd = Math.max(maxd, dist[i]);
            List<Integer> ans = new ArrayList<>();
            for (int i = 1; i <= n; i++) if (deg[i] >= 2 && dist[i] == maxd) ans.add(i);
            System.out.println(ans.size());
            if (ans.isEmpty()) {
                System.out.println();
            } else {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < ans.size(); i++) { if (i > 0) sb.append(' '); sb.append(ans.get(i)); }
                System.out.println(sb.toString());
            }
        }
    }
}

from collections import deque

t = int(input().strip())
for _ in range(t):
    n = int(input().strip())
    g = [[] for _ in range(n + 1)]
    deg = [0] * (n + 1)
    for _e in range(n - 1):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)
        deg[u] += 1
        deg[v] += 1
    INF = 10 ** 9
    dist = [INF] * (n + 1)
    q = deque()
    for i in range(1, n + 1):
        if deg[i] == 1:
            dist[i] = 0
            q.append(i)
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] == INF:
                dist[v] = dist[u] + 1
                q.append(v)
    maxd = -1
    for i in range(1, n + 1):
        if deg[i] >= 2 and dist[i] > maxd:
            maxd = dist[i]
    ans = [i for i in range(1, n + 1) if deg[i] >= 2 and dist[i] == maxd]
    print(len(ans))
    if ans:
        print(' '.join(map(str, ans)))
    else:
        print()

算法及复杂度

算法：多源 BFS 计算到最近叶子的距离 $d(u)$ ，再在度数 $\ge 2$ 的点中取 $d(u)$ 最大者
时间复杂度： $\mathcal{O}(n)$ （每组）
空间复杂度： $\mathcal{O}(n)$