题解 | 世界树上找米库

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    T = int(sys.stdin.readline())
    
    for _ in range(T):
        n = int(sys.stdin.readline())
        graph = [[] for _ in range(n + 1)]
        degree = [0] * (n + 1)
        
        for _ in range(n - 1):
            u, v = map(int, sys.stdin.readline().split())
            graph[u].append(v)
            graph[v].append(u)
            degree[u] += 1
            degree[v] += 1
        
        # 找出所有叶子节点（Sekai 点）
        sekai = [i for i in range(1, n + 1) if degree[i] == 1]

        # 多源 BFS，记录每个节点到最近 Sekai 点的距离
        dist = [-1] * (n + 1)
        q = deque()
        for s in sekai:
            dist[s] = 0
            q.append(s)
        
        while q:
            u = q.popleft()
            for v in graph[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    q.append(v)
        
        # 在非叶子节点中，找出距离值最大的点
        max_dist = -1
        miku = []
        for i in range(1, n + 1):
            if degree[i] > 1:
                if dist[i] > max_dist:
                    max_dist = dist[i]
                    miku = [i]
                elif dist[i] == max_dist:
                    miku.append(i)
        
        # 输出结果
        print(len(miku))
        print(' '.join(map(str, sorted(miku))))

main()