Codeforces Round 1048 (Div. 2)——E2. Maple and Tree Beauty (Hard Version)（bitset的使用，变长bitset）

思路讲解

Codeforces Round 1048 (Div. 2)——E1. Maple and Tree Beauty (Easy Version)（背包问题）（子集枚举→能否凑出某个的和）

不难发现，用背包会TLE。

说实话，这个就真没招了，看题解吧。

其实用bitset 优化一下就能过去。

最后发现，我这样分一个if else 的反而更快

还有一种曲线救国方法。使用模板参数。

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

$O(N^2/w)$ 的时间复杂度，能够过去。

源代码

// 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……）