题目大意

给一棵 $n$ 个节点的树，有 $k$ 个牧羊人初始位置已知。需要选择最少的节点作为"关键节点"，使得每个牧羊人到其最近的关键节点的路径都经过该关键节点。

算法思路

预处理：

• 第一次 DFS 计算每个节点的深度和父亲

• 对牧羊人按深度降序排序

多源 BFS：

• 从所有牧羊人位置同时开始 BFS

• 计算每个节点到最近牧羊人的距离 $D[u]$

• 构建反图 $g3$：如果 $D[v] = D[u] + 1$，则在反图中添加边 $v \to u$

寻找祖先节点：

对每个牧羊人，沿着 $D$ 值递减的方向向上找，直到遇到 $D$ 值不连续的点，作为该牧羊人的"祖先节点"

贪心选择：

• 从深度大的牧羊人开始处理

• 如果牧羊人未被覆盖，选择其祖先节点作为关键节点

• 在反图中标记所有能被该关键节点覆盖的节点

时间复杂度

• DFS 和 BFS 都是 $O(n)$

• 总时间复杂度 $O(n + k \log k)$（排序开销）

空间复杂度

• 使用邻接表存储树和反图

• 总空间复杂度 $O(n)$

关键点

• 反图构建：通过 $g3$ 记录哪些节点可以被某个关键节点覆盖

• 贪心策略：从深到浅处理，确保每个牧羊人要么被覆盖，要么选择其祖先节点

• 祖先节点：确保选择的节点能够覆盖尽可能多的牧羊人

这个算法保证了选择的关键节点数量最少，并且能够覆盖所有牧羊人。

AC代码

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

const int N = 5e5 + 5;

int n, k, p[N], d[N], D[N], fa[N], anc[N];
bool vis[N], selected[N];
vector<int> g[N], g3[N];  // g: 原树；g3: 反图，用于记录覆盖关系

// 快读函数
int read() {
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = getchar(); }
    return x * f;
}

// 第一次DFS：计算深度和父节点
void dfs1(int u, int f) {
    d[u] = d[f] + 1;  // 节点深度
    fa[u] = f;        // 父节点
    for (int v : g[u]) if (v != f) dfs1(v, u);
}

// 多源BFS：计算每个节点到最近牧羊人的距离
void bfs() {
    memset(D, 0x3f, sizeof(D));  // 初始化为无穷大
    queue<int> q;
    
    // 所有牧羊人作为起点
    for (int i = 1; i <= k; i++) {
        D[p[i]] = 0;           // 牧羊人自身距离为0
        vis[p[i]] = 1;         // 标记为已访问
        q.push(p[i]);
    }
    
    // BFS过程
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (!vis[v]) {  // 未访问过的节点
                D[v] = D[u] + 1;
                vis[v] = 1;
                q.push(v);
            }
            // 构建反图：如果v是通过u到达的最近路径
            if (D[v] == D[u] + 1) {
                g3[v].push_back(u);  // 记录覆盖关系：v可以被u覆盖
            }
        }
    }
}

// 向上寻找祖先节点：找到D值不连续的点
int findAncestor(int u) {
    // 如果父节点的D值正好比当前节点小1，继续向上找
    if (D[u] + 1 == D[fa[u]]) return findAncestor(fa[u]);
    return u;  // 返回D值不连续的点
}

// 标记覆盖：从关键节点出发，标记所有能被覆盖的节点
void mark(int u) {
    if (vis[u]) return;
    vis[u] = 1;  // 标记为已覆盖
    // 在反图中递归标记
    for (int v : g3[u]) mark(v);
}

int main() {
    n = read(), k = read();
    
    // 读入树结构
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    // 读入牧羊人位置
    for (int i = 1; i <= k; i++) p[i] = read();
    
    // 步骤1：计算深度，按深度排序
    dfs1(1, 0);
    sort(p + 1, p + k + 1, [](int a, int b) { return d[a] > d[b]; });
    
    // 步骤2：多源BFS计算最近距离并构建反图
    bfs();
    
    // 步骤3：为每个牧羊人找到祖先节点
    for (int i = 1; i <= k; i++) anc[p[i]] = findAncestor(p[i]);
    
    // 步骤4：贪心选择关键节点
    memset(vis, 0, sizeof(vis));  // 重置访问标记
    int cnt = 0;  // 关键节点数量
    
    for (int i = 1; i <= k; i++) {
        if (vis[p[i]]) continue;  // 如果牧羊人已被覆盖，跳过
        
        // 选择该牧羊人的祖先节点作为关键节点
        mark(anc[p[i]]);            // 标记所有能被覆盖的节点
        selected[anc[p[i]]] = 1;    // 标记为关键节点
        cnt++;
    }
    
    // 输出结果
    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++) if (selected[i]) printf("%d ", i);
    
    return 0;
}