题解 | 世界树上找米库

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
	int t;
	cin >> t;
	vector<vector<int> > graph;
	vector<int> degree;
	vector<int> vis; 
	while(t--) {
		int n;
		cin >> n;
		graph.resize(n + 1);
		for(vector<vector<int> >::iterator it = graph.begin(); it != graph.end(); it++) {
			it -> clear();
		} 
		degree.assign(n + 1, 0);
		vis.assign(n + 1, 0);
		int v1, v2;
		for (int i = 0; i < n - 1; i++) {
			cin >> v1 >> v2;
			graph[v1].push_back(v2);
			graph[v2].push_back(v1);
			degree[v1]++;
			degree[v2]++;
		}
		queue<int> q;
		for (int i = 1; i <= n; i++) {
			if (degree[i] == 1) {
				q.push(i);
				vis[i] = 1;
			}
		}
		int round = 0, sz = 0;
		vector<int> ans;
		while (!q.empty()) {
			ans.clear();
			sz = q.size();
			for (int i = 0; i < sz; i++) {
				int v = q.front();
				ans.push_back(v);
				q.pop(); 
				for (vector<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++) {
					if (!vis[*it]) {
						q.push(*it);
						vis[*it] = 1;	
					} 
				}
			}
			round++;
		}
		sort(ans.begin(), ans.end());
		cout << ans.size() << endl;
		for (vector<int>::iterator it = ans.begin(); it != ans.end(); it++) {
			cout << *it << " ";
		}
		cout << endl; 
	}
}