可以贪心，固定最大距离为 $dis_{i,j}$，数有多少个 $k$ 满足 $dis_{i,k}\leq dis_{i,j}$ 且 $dis_{j,k}\leq dis{i,j}$，这些 $k$ 互相之间的距离也会 $\leq dis_{i,j}$。

证明：

设满足条件的 $k$ 构成集合 $K$

$\forall k_1,k_2\in K$ 都有：

• $dis_{i,k_1}\leq dis_{i,j}$
• $dis_{j,k_2}\leq dis_{i,j}$

当 $dis_{i,k}\leq dis_{i,j}$ 且 $dis_{j,k}\leq dis{i,j}$ 时，$k$ 不可能是 $i$ 或 $j$ 的儿子（以 $lca_{i,j}$ 为根）。

所以上述不等式可以转化为：

• $dis_{i,lca_{i,j}}+dis_{k_1,lca_{i,j}}\leq dis_{i,lca_{i,j}}+dis_{j,lca_{i,j}}$
• $dis_{j,lca_{i,j}}+dis_{k_2,lca_{i,j}}\leq dis_{i,lca_{i,j}}+dis_{j,lca_{i,j}}$

$\therefore dis_{k_1,k_2}=dis_{k_1,lca_{i,j}}+dis_{k_2,lca_{i,j}}\leq dis_{i,lca_{i,j}}+dis_{j,lca_{i,j}}=dis_{i,j}$

代码：

注意特判 $m=1$，此时答案为 $0$。

// Sam的素描作品
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, s, ans;
vector<int> tr[105], a, dis[105];

void dfs(int u, int fa) {
    for (int v : tr[u]) {
        if (v == fa) continue;
        dis[s][v] = dis[s][u] + 1;
        dfs(v, u);
    }
}

int main() {
    cin >> n >> m;
    a.resize(n + 5);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        s = i;
        dis[s].resize(n + 5);
        dfs(i, 0);
    }
    ans = n - 1;
    for (int i = 1; i <= n; i++) {
        if (!a[i]) continue;
        for (int j = i + 1; j <= n; j++) {
            if (!a[j]) continue;
            int cnt = 0;
            for (int k = 1; k <= n; k++)
                if (a[k] && (cnt += (dis[i][k] <= dis[i][j] && dis[j][k] <= dis[i][j])) >= m)
                    break;
            if (cnt >= m) ans = min(ans, dis[i][j]);
        }
    }
    if (m == 1) ans = 0;
    cout << ans << '\n';
    return 0;
}

首先，题目中的 ”最大值最小“ 这句话就非常符合二分答案的条件了。

因此我们考虑对答案（两个黑点的最远的距离）进行二分答案。

现在就要考虑如何进行 $check$。

$check$ 的方式肯定是看某个最远距离不超过 $mid$ 的集合中是否存在超过 $m$ 个黑点，但是关键在于如何枚举最远距离不超过 $mid$ 的集合。

这里会碰到一个误区，从某个点出发用 $dfs$ 计算离这个点距离小于 $mid$ 的所有集合，那么其实这个集合中最远的两个点的距离有可能达到 $2 * mid$，是错误的。

所以这里需要用到一个小技巧，先用 $bfs$ 的形式遍历这棵树，每次 $bfs$ 遍历到 $now$ 这个节点时，我们用 $dfs$ 从 $now$ 出发遍历现在已经访问过的点，也就是不把 $now$ 当做中间节点计算集合。而是把 $now$ 当做边缘或者根节点来计算集合，这样在 $bfs$ 已访问过的点中求出离 $now$ 距离小于 $mid$ 的所有点集，那么就能保证这些节点之间的距离不超过 $mid$。

然后判断黑色节点数量即可。

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

#define N 105

int n, m;
int a[N], vis[N]; // 用vis数组去区分点的不同的集合
vector<int> g[N];
queue<int> q;
int ans;

int dfs(int u, int fa, int all, int dis) {
    int res = a[u];
    if (dis == all) return res;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!vis[v] || v == fa) continue;
        res += dfs(v, u, all, dis + 1);
    }
    return res;
}

bool check(int mid) { // 二分的check，本质上为一个bfs
    memset(vis, 0, sizeof vis);
    while (q.size()) q.pop();
    q.push(1);
    while (q.size()) {
        int u = q.front();
        q.pop();
        vis[u] = 1;
        int tmp = dfs(u, 0, mid, 0); // 通过dfs获取这个集合的黑点的个数
        if (tmp >= m) return 1;
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (vis[v]) continue;
            q.push(v);
        }
    }
    return 0;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int l = 0, r = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}