深刻。
考虑 \(k=1\) 的时候取直径中点最优，进一步不难发现连通块必然包含直径中点。
考虑二分 \(mid\)，求出令 \(\max d(i)\leq mid\) 的最少点数。枚举断边，对两个连通块分别求出在内部选一个连通块覆盖所有点的最少点数。对于一个连通块，以直径中点为根，对于每个深度为 \(d>mid\) 的点，其深度为 \(d-mid\) 的祖先必须被选中，自底向上求出必须被选中的点数即可。时间复杂度为 \(\mathcal{O}(n^2\log{n})\)，考场上的思考就到此为止了。
考虑优化 check 的复杂度。每个连通块都求出以直径中点为根的信息看上去不太好做，考虑抛开这个结构直接去 DP。比较容易求出的是：\(f_u\) 表示强制选择点 \(u\) 覆盖 \(sub_u\) 的最少点数。令 \(h_u\) 表示子树高度，那么容易得到转移：
再来考虑如果不强制选择点 \(u\) 怎么做。观察到如果有至少两个儿子 \(v\) 满足 \(h_v\geq mid\)，那么 \(u\) 是必选的，因此如果 \(u\) 可以不被选择，它至多只有一个儿子满足 \(h_v\geq mid\)。由此不难看出，不强制选择点 \(u\) 的方案，形如从 \(f_u\) 给出的方案中删去一条从 \(u\) 开始的链。
设计 \(g_u\) 表示这条链的最大长度。若 \(u\) 恰好有一个儿子 \(v\) 满足 \(h_v\geq mid\)，则设 \(d=\max\limits_{w\in son_u\land w\neq v}\{h_w+1\}\)，可以得到转移：
否则 \(g_u=0\)。
这个状态就很方便换根了。对于每个 \(u\)，我们求出 \(u\) 子树内/子树外的最大、次大的 \(h\) 和最大的 \(h\) 对应的节点，转移 \(g\) 的时候直接判断是否有 \(mx>mid\land smx\leq mid\) 就好了。
时间复杂度 \(\mathcal{O}(n\log{n})\)。
在洛谷上很卡常，需要精细实现。
代码#include using namespace std;using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair;
const int MAXN = 1e6 + 5;template T lowbit(T x) { return x & -x; }
template void chkMin(T &x, T y) { x = y < x ? y : x; }
template void chkMax(T &x, T y) { x = x < y ? y : x; }
constexpr int lg2(ll x) { return 63 ^ __builtin_clzll(x); }
constexpr ll bitCeil(ll x) { return x == 1 ? 1ll : 1ll << lg2(x - 1) + 1; }int tid, tc, n, k, fa[MAXN];
int deg[MAXN], st[MAXN], ed[MAXN], T[MAXN << 1];
int f[MAXN], g[MAXN], g2[MAXN];
pii edges[MAXN];
vector ord;struct Info {int mx, mxp, smx;
} a[MAXN], b[MAXN];bool check(int mid) {fill(f + 1, f + n + 1, 1);for (int u : ord | views::reverse) {g[u] = a[u].mx > mid && a[u].smx <= mid ? min(g[a[u].mxp] + 1, mid - a[u].smx) : 0;if (fa[u] && a[u].mx >= mid) f[fa[u]] += f[u];}if (f[1] - g[1] <= k) return true;for (int u : ord) {for (int _ = st[u]; _ < ed[u]; ++_) {int v = T[_];if (v == fa[u]) continue;int nf = f[u] - (a[v].mx >= mid ? f[v] : 0);g2[v] = b[v].mx > mid && b[v].smx <= mid ? min(b[v].mxp == fa[u] ? g2[u] + 1 : g[b[v].mxp] + 1, mid - b[v].smx) : 0;if (nf - g2[v] + f[v] - g[v] <= k) return true;if (b[v].mx >= mid) f[v] += nf;}}return false;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> tid >> tc;while (tc--) {cin >> n >> k;fill(deg + 1, deg + n + 1, 0);for (int i = 1; i < n; ++i) {int u, v;cin >> u >> v;edges[i] = {u, v};++deg[u];++deg[v];}st[1] = ed[1] = 0;for (int i = 1; i < n; ++i) st[i + 1] = ed[i + 1] = st[i] + deg[i];for (int i = 1; i < n; ++i) {auto [u, v] = edges[i];T[ed[u]++] = v;T[ed[v]++] = u;}ord.clear();ord.emplace_back(1);for (int i = 0; i < n; ++i) {int u = ord[i];for (int _ = st[u]; _ < ed[u]; ++_) {int v = T[_];if (v == fa[u]) continue;fa[v] = u;ord.emplace_back(v);}}int D = 0;fill(a + 1, a + n + 1, Info{0, 0, 0});for (int u : ord | views::reverse) {chkMax(D, a[u].mx + a[u].smx);if (u == 1) break;int p = fa[u];if (a[u].mx + 1 >= a[p].mx) {a[p].smx = a[p].mx;a[p].mx = a[u].mx + 1;a[p].mxp = u;} else {chkMax(a[p].smx, a[u].mx + 1);}}for (int u : ord) {array h;for (int _ = st[u]; _ < ed[u]; ++_) {int v = T[_];pii val = {v == fa[u] ? b[u].mx + 1 : a[v].mx + 1, v};for (auto &c : h) {if (val > c) swap(val, c);}}for (int _ = st[u]; _ < ed[u]; ++_) {int v = T[_];if (v == fa[u]) continue;pii x = h[0], y = h[1];if (x.second == v) {x = h[1];y = h[2];} else if (y.second == v) {y = h[2];}b[v] = {x.first, x.second, y.first};}}int l = 0, r = D + 1 >> 1;while (l < r) {int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}cout << l << '\n';}return 0;
}