题解：CF2138C2 Maple and Tree Beauty (Hard Version)
Engulf
·
·
题解
记叶子中深度最小的为 d，答案不超过 d。
考虑一种特殊情况，所有的叶子深度相同，均为 d。这种情况下，所有字符串的长度相等，为了使 LCS 最大，我们希望深度相同的节点（相当于同位置的字符）取同种字符，下文把深度为 i 的节点称为“第 i 组”。
记 c_i 表示深度 i 的节点个数。如果存在一种选取组的方案 S 使得 \sum\limits_{i\in S} c_i = k，把 0 都放在这些组的节点上，1 放在剩下的节点上，可以使得答案为 d。可以 01 背包解决。
如果不存在这样的方案，答案为 d - 1。
:::info[证明]
现在证明这个东西。
有显然事实：c_i \le c_{i + 1}，于是 c_d 是最大的（注意这是在所有叶子深度相同的限制下）。考虑这样一种构造方案：我们不要 c_d 了，把它拆成 c_d 个体积为 1 的物品。这样，只要前 d-1 组存在一种选法使得 \sum\limits_{i\in S} c_i = s, k-s\le c_d，就可以做到答案 d-1，即 s \ge k - c_d。而 \sum\limits_{i=1}^{n-1}c_i = n - c_d \ge k - c_d，所以肯定存在。
:::
现在推广到叶子节点的深度不相同。我们猜测，原本按深度分组的方案仍然是最优的。深度 > d 的点，不会影响答案，可以随便选，把他们都看作体积为 1 的物品。
:::info[证明]
深度 <d 的组，这样分肯定最优。因为这是每个串的公共前缀。
深度 =d 的组，如果深度为 d 的节点 u 没有放入该组，那么我们会选择一个 u 子树内的若干点放入该组。本来可以任选的，现在被强制选则一个值，这是不优的。但如果把 u 选入，子树内的点就是自由的了，可以随便选了。
相当于做背包的时候，你把一个大体积的物品，拆出若干个 1，不会使答案变劣。
:::
发现我们在做 $01$ 背包，上 bitset 优化即可做到 $\mathcal{O}\left(\dfrac{n^2}{w}\right)$，可以通过。
:::success[实现]
```cpp line-numbers
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt;
while (tt--) {
int n, k; cin >> n >> k;
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
int p; cin >> p; p--;
g[p].emplace_back(i);
}
vector<int> dep(n);
vector<int> c(n);
int d = n;
auto dfs = [&](auto &&self, int u) -> void {
c[dep[u]]++;
if (g[u].empty()) d = min(d, dep[u]);
for (auto v: g[u]) {
dep[v] = dep[u] + 1;
self(self, v);
}
};
dfs(dfs, 0);
d++;
c.resize(d);
for (int i = 0; i < n; i++)
if (dep[i] >= d)
c.emplace_back(1);
bitset<200005> f;
f[0] = 1;
for (int i = 0; i < c.size(); i++)
f |= f << c[i];
cout << d - !f[k] << "\n";
}
return 0;
}
```
:::