Codeforces Round 1048 (Div. 2)——E2. Maple and Tree Beauty (Hard Version)（bitset的使用，变长bitset） · znzryb
## 思路讲解
[Codeforces Round 1048 (Div. 2)——E1. Maple and Tree Beauty (Easy Version)（背包问题）（子集枚举→能否凑出某个的和）](/2025/09/10/20250910-53e3e1a3)
不难发现，用背包会TLE。
说实话，这个就真没招了，看题解吧。
其实用bitset 优化一下就能过去。
最后发现，我这样分一个if else 的反而更快
还有一种曲线救国方法。使用模板参数。
```cpp
template <int maxn>
inline void __() {
// cin >> N >> K;
if (maxn <= N) {
__< min(maxn * 2, (int)MAXN) >();
return;
}
```
## AC代码
[https://codeforces.com/contest/2139/submission/337943651](https://codeforces.com/contest/2139/submission/337943651)
$O(N^2/w)$ 的时间复杂度，能够过去。
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#include <bitset>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
cerr << "[ ";
for (T i : v) _print(i), cerr << " ";
cerr << "]";
}
template<typename T> void _print(set<T> s) {
cerr << "{ ";
for (T i : s) _print(i), cerr << " ";
cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
cerr << "{";
_print(p.first);
cerr << ", ";
_print(p.second);
cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
cerr << "{ ";
for (auto &p : m) _print(p), cerr << " ";
cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif
using ll = long long; using ull = unsigned long long;
using DB = double; using LD = long double;
// using i128 = __int128;
using pdd = pair<DB, DB>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<DB>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
inline void __();
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
while (lT--)
__();
return 0;
}
/*
双背包问题解法
https://chatgpt.com/share/68c0ff99-20d0-8013-b16a-26d60768748a
*/
inline void __() {
cin >> N >> K;
vll P(N + 5);
vector<vll> g(N + 5);
FOR(i, 2, N) {
cin >> P[i];
g[i].PB(P[i]);
g[P[i]].PB(i);
}
vll cnt(N + 5);
ll desti = INF;
auto dfs = [&](auto &&self, int u, int fa, int dep)->void {
cnt[dep]++;
bool isleaf = true;
for (auto &v : g[u]) {
if (v == fa) continue;
self(self, v, u, dep + 1);
isleaf = false;
}
if (isleaf) {
desti = min<ll>(desti, dep);
}
};
dfs(dfs, 1, 1, 1);
vll ls = {0};
FOR(i, 1, desti) {
ls.PB(cnt[i]);
}
// 我们会发现，能否通过前K关（构造出K前缀），和这个顺序是没有关系的
// 我们直接看前 K 个物品是否可以凑出一个和
// vector<vii> dp(SZ(ls)+5,vii(N+5));
if (K <= N - K) {
K = N - K;
}
ll ans = 0;
if (N <= 200) {
bitset<210> dp;
ll sum = 0;
// 滚动数组优化，第i层哪些值是可以达到的
dp[0] = true;
bitset<210> mask;
FOR(i, 0, K) {
mask[i] = true;
}
ll up = K - N;
FOR(i, 1, desti) {
ll w = ls[i];
sum += w;
dp |= (dp << w);
ll cur = sum - N + K - 1;
FOR(j, max(0ll, up), min(K, cur)) {
#ifdef LOCAL
debug(j);
#endif
mask[j] = 0;
}
up = cur;
// 这一大段代码
// sum-N+K<=val<=K
if ((mask & dp).any()) {
ans = i;
} else {
break;
}
}
} else {
bitset<MAXN> dp;
ll sum = 0;
// 滚动数组优化，第i层哪些值是可以达到的
dp[0] = true;
bitset<MAXN> mask;
FOR(i, 0, K) {
mask[i] = true;
}
ll up = K - N;
FOR(i, 1, desti) {
ll w = ls[i];
sum += w;
dp |= (dp << w);
ll cur = sum - N + K - 1;
FOR(j, max(0ll, up), min(K, cur)) {
#ifdef LOCAL
debug(j);
#endif
mask[j] = 0;
}
up = cur;
// 这一大段代码
// sum-N+K<=val<=K
if ((mask & dp).any()) {
ans = i;
} else {
break;
}
}
}
cout << ans << "\n";
}
/*
AC
https://codeforces.com/contest/2139/submission/337943651
1
5 2
1 1 1 1
*/
```
:::
## 心路历程（WA，TLE，MLE……）