题解 | 图论

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e5+5;

ll n,m;

// 邻接表存储无向图
vector<vector<ll>>adj(N);
// 存储需要连通的m个目标节点
unordered_set<ll>s;
// BFS队列，用于层序遍历图
queue<ll>q;
// 标记节点是否已访问，避免重复遍历
vector<bool>vis(N,false);
// 存储最终选中的边（生成树的边）
vector<pair<ll,ll>>ans;

void bfs(){
    // BFS核心循环：队列非空时持续遍历
    while(!q.empty()){
        // 取出队首节点作为当前遍历节点
        ll t=q.front();
        q.pop();

        // 遍历当前节点的所有邻接节点
        for(auto it:adj[t]){
            // 仅处理未访问过的节点（避免环和重复）
            if(vis[it]==false){
                // 若邻接节点是目标节点（属于s集合）
                if(s.find(it)!=s.end()){
                    // 记录这条边（当前节点 -> 目标节点）
                    ans.emplace_back(t,it);
                    // 收集到m-1条边时直接返回（生成树边数=节点数-1）
                    if(ans.size()==m-1){
                        return;
                    }
                }
                // 将邻接节点入队，继续BFS遍历
                q.push(it);
                // 标记为已访问，防止重复处理
                vis[it]=true;
            }
        }
    }
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
    // 输入节点总数n、需要连通的目标节点数m
    cin>>n>>m;
    // 读入n-1条边，构建无向图的邻接表
    for(ll i=1;i<=n-1;i++){
        ll u,v;
        cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
   }
   // 读入m个目标节点，存入集合s以便快速查询
   for(ll i=1;i<=m;i++){
        ll t;
        cin>>t;
        s.insert(t);
   }
    // BFS初始化：从任意一个目标节点开始（选s的第一个元素）
    q.push(*s.begin());
    // 标记起始节点为已访问
    vis[*s.begin()]=true;
   // 执行BFS，收集目标节点间的连通边
   bfs();
    // 输出选中的边数（理论上是m-1）
    cout<<ans.size()<<'\n';
    // 输出每条选中的边
    for(auto t:ans){
        cout<<t.first<<' '<<t.second<<'\n';
    }
	return 0;
}