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

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

现在就要考虑如何进行 $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;
}