首先答案具有可二分性，考虑二分出最长时间后如何验证。我们需要判断需要点燃引线数目的最小值与 mmm 的关系。
怎么才能求出最小值？考虑树中从下往上贪心，每次当树内部需要但没有覆盖的点的距离达到了 midmidmid，才选择点燃这个点，否则在它的祖先处点燃也能覆盖子树内的点，还可以覆盖子树外的点。于是需要统计 fu,guf_u,g_ufu?,gu? 分别表示 uuu 的子树内部最远没有覆盖的点，以及最近覆盖的的距离点。若 fu+gu<=midf_u + g_u <= midfu?+gu?<=mid 则子树内部可以覆盖完，将 fuf_ufu? 设为 ?inf-inf?inf，可以从儿子处更新 f,gf, gf,g 的值，若最后 frt>=0f_{rt} >= 0frt?>=0 ，则表明整个树内部还有没有覆盖的点，还需要覆盖 rtrtrt。
另外一个做法复杂度要多 logn2logn^2logn2，我们只考虑需要覆盖的点，每次选其中深度最深的点，若它没有被覆盖，点燃引线则来覆盖它，还可以覆盖所有距离与它不超过 mid?2mid*2mid?2 的结点，只需点燃它的 midmidmid 级祖先即可。但如何快速覆盖？可以把贡献记在所有可能的 lcalcalca 处，维护每个 lcalcalca 处 2?deplca?du2*dep_{lca} - d_{u}2?deplca??du? 的最大值，若大于等于 dv?2?midd_v - 2*middv??2?mid 则该点也被覆盖。
总之就是考虑从下往上贪心，尽可能在高处点燃引线，因为越高的点覆盖范围更广。树上问题中维护点对之间的信息可以考虑维护每个可能的 lcalcalca 作为决策点的最值，计算两个点分别与 lcalcalca 的贡献，有一点分治的思想在里面。
树剖：
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef long long LL;
typedef pair <int, int> P;
const int N = 3e5 + 5;int n, m, idx;
int d[N], siz[N], id[N], fa[N], top[N], son[N], num[N];
bool vis[N];
vector <int> g[N];
vector <P> q;inline int Read()
{
int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}struct Tree {
int v1[N<<2], tag[N<<2], v2[N<<2];void push_up_(int o) {
int ls = o<<1, rs = o<<1|1;v1[o] = max(v1[ls], v1[rs]);v2[o] = max(v2[ls], v2[rs]);}void build_(int o, int l, int r) {
tag[o] = inf, v2[o] = -inf;if (l == r) {
v1[o] = d[num[l]]<<1;return;} int mid = (l + r)>>1;build_(o<<1, l, mid), build_(o<<1|1, mid + 1, r);push_up_(o);}void push_down_(int o) {
int ls = o<<1, rs = o<<1|1;tag[ls] = min(tag[ls], tag[o]);tag[rs] = min(tag[rs], tag[o]);v2[ls] = v1[ls] - tag[ls];v2[rs] = v1[rs] - tag[rs];tag[o] = inf;}void update_(int o, int l, int r, int x, int y, int k) {
if (x <= l && r <= y) {
tag[o] = min(tag[o], k);v2[o] = v1[o] - tag[o];return;}if (tag[o] < inf) push_down_(o);int mid = (l + r)>>1;if (x <= mid) update_(o<<1, l, mid, x, y, k);if (mid < y) update_(o<<1|1, mid + 1, r, x, y, k);push_up_(o);}int query_(int o, int l, int r, int x, int y) {
if (x <= l && r <= y) return v2[o];int res = -inf, mid = (l + r)>>1;if (tag[o] < inf) push_down_(o);if (x <= mid) res = max(res, query_(o<<1, l, mid, x, y));if (mid < y) res = max(res, query_(o<<1|1, mid + 1, r, x, y));return res;}
} T;void dfs2_(int u, int topf) {
top[u] = topf, id[u] = ++idx, num[idx] = u;if (son[u]) dfs2_(son[u], topf);for (int v, i = 0; i < g[u].size(); i++) {
v = g[u][i];if (v == fa[u] || v == son[u]) continue;dfs2_(v, v);}
}void dfs1_(int u) {
siz[u] = 1, d[u] = d[fa[u]] + 1;for (int i = 0; i < (int) g[u].size(); i++) {
int v = g[u][i];if (v == fa[u]) continue;fa[v] = u, dfs1_(v);siz[u] += siz[v];if (siz[v] > siz[son[u]]) son[u] = v;}
}void change_(int u, int v, int k) {
while (top[u] != top[v]) {
if (d[top[u]] < d[top[v]]) swap(u, v);T.update_(1, 1, n, id[top[u]], id[u], k);u = fa[top[u]];}if (d[u] > d[v]) swap(u, v);T.update_(1, 1, n, id[u], id[v], k);
}int ask_(int u, int v) {
int res = -inf;while (top[u] != top[v]) {
if (d[top[u]] < d[top[v]]) swap(u, v);res = max(res, T.query_(1, 1, n, id[top[u]], id[u]));u = fa[top[u]];}if (d[u] > d[v]) swap(u, v);return max(res, T.query_(1, 1, n, id[u], id[v]));
}int cal_(int lim) {
int res = 0;T.build_(1, 1, n);rep (i, 0, (int) q.size() - 1) {
int u = q[i].second;// if (lim == 1) cout<<u<<endl;if (ask_(u, 1) >= d[u] - lim*2) continue;// if (lim == 1 && u == 6) cout<<ask_(u, 1)<<" "<<d[u] - lim*2<<endl;res++, change_(u, 1, d[u]);//if (lim == 1) cout<<u<<endl;}return res;
}int main() {
cin>>n>>m;rep (i, 1, n) vis[i] = Read();for (int u, v, i = 1; i < n; i++) {
u = Read(), v = Read();g[u].push_back(v), g[v].push_back(u);}dfs1_(1);dfs2_(1, 1);int l = 0, r = n/(m + 1);rep (i, 1, n)if (vis[i]) q.push_back(P(-d[i], i));sort(q.begin(), q.end());while (l < r) {
int mid = (l + r)>>1;if (cal_(mid) <= m) r = mid;else l = mid + 1;}printf("%d\n", l);return 0;
}
树内贪心：
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef long long LL;
typedef pair <int, int> P;
const int N = 3e5 + 5;int ans, n, m, l, r;
int f[N], g[N];
vector <int> e[N];
bool vis[N];void dfs_(int u, int fa, int lim) {
g[u] = inf, f[u] = vis[u] ? 0 : -inf;for (int v, i = 0; i < (int) e[u].size(); i++) {
v = e[u][i];if (v == fa) continue;dfs_(v, u, lim);g[u] = min(g[u], g[v] + 1);f[u] = max(f[u], f[v] + 1);}if (g[u] + f[u] <= lim) {
f[u] = -inf;return;}if (f[u] == lim) ans++, g[u] = 0, f[u] = -inf;
}int main() {
cin>>n>>m;rep (i, 1, n) cin>>vis[i];for (int u, v, i = 1; i < n; i++) {
scanf("%d%d", &u, &v);e[u].push_back(v), e[v].push_back(u);}l = 0, r = n/2;while (l < r) {
int mid = (l + r)>>1;ans = 0, dfs_(1, 0, mid);if (g[1] + f[1] > mid) ans++;if (ans <= m) r = mid;else l = mid + 1; }printf("%d\n", l);return 0;
}