Codeforces Round 1048 (Div. 2)——E1. Maple and Tree Beauty (Easy Version)（背包问题）（子集枚举→能否凑出某个的和） · znzryb
## 思路讲解
[https://chatgpt.com/share/68c0ff99-20d0-8013-b16a-26d60768748a](https://chatgpt.com/share/68c0ff99-20d0-8013-b16a-26d60768748a)
```cpp
// 我们会发现，能否通过前K关（构造出K前缀），和这个顺序是没有关系的
// 我们直接看前 K 个物品是否可以凑出一个和
// vector<vii> dp(SZ(ls)+5,vii(N+5));
vii dp(N+5);
ll sum=0;
ll ans=0;
// 滚动数组优化，第i层哪些值是可以达到的
dp[0]=true;
FOR(i,1,desti){
ll w=ls[i];
sum+=w;
// 滚动数组反向遍历
ROF(j,N-w,0){
dp[w+j]|=dp[j];
}
FOR(a,0,N){
if(dp[a]){
ll b=sum-a;
if((a<=K && b<=N-K) || (b<=K && a<=N-K) ){
ans=i;
break;
}
}
}
if(ans!=i){
break;
}
}
```
## AC代码
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#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)1e3+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));
vii dp(N+5);
ll sum=0;
ll ans=0;
// 滚动数组优化，第i层哪些值是可以达到的
dp[0]=true;
#ifdef LOCAL
_print(ls);
#endif
FOR(i,1,desti){
ll w=ls[i];
sum+=w;
// 滚动数组反向遍历
ROF(j,N-w,0){
dp[w+j]|=dp[j];
}
FOR(a,0,N){
if(dp[a]){
ll b=sum-a;
#ifdef LOCAL
debug(a)
debug(b);
#endif
if((a<=K && b<=N-K) || (b<=K && a<=N-K) ){
ans=i;
break;
}
}
}
if(ans!=i){
break;
}
}
cout<<ans<<"\n";
}
/*
AC
https://codeforces.com/contest/2139/submission/337899174
*/
```
:::
## 心路历程（WA，TLE，MLE……）