/* [Author : Hoang Duy Vu] */
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define fi first
#define se second
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) {
if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) {
if (res > val) { res = val; return true; } return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int LOG = 20;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 200010;
vector <int> a[N];
int dp[N][450] = {0};
int t[N] = {0};
int f[1100] = {0};
int high[N] = {0};
int n , k;
int sz[N] = {0};
int ans = 0;
void input()
{
cin >> n >> k;
for (int i = 1 ; i < n ; i++)
{
int x;
cin >> x;
a[x].push_back(i);
a[i].push_back(x);
}
}
void dfs(int u ,int par)
{
memset(dp[u],0,sizeof(dp[u]));
for (int v : a[u])
if (v != par)
{
dfs(v,u);
maximize(high[u],high[v] + 1);
for (int i = 0 ; i <= k ; i++) f[i] = dp[u][i];
for (int i = 0 ; i <= min(high[u],k) ; i++)
{
for (int j = max(i - 1,0) ; j <= min(high[v],k) ; j++)
{
int x = j + 1;
maximize(dp[u][i],f[max(i,k - x)] + dp[v][j]);
}
}
}
maximize(dp[u][0],dp[u][k] + 1);
}
void case1()
{
dfs(0,0);
int res = 0;
for (int i = 0 ; i <= high[0] ; i++) maximize(res,dp[0][i]);
cout << res;
}
void DFS(int u , int par)
{
memset(dp[u],-1,sizeof(dp[u]));
dp[u][0] = INF;
sz[u] = 1;
for (int v : a[u])
if (v != par)
{
DFS(v,u);
sz[u] = min(ans,sz[u] + sz[v]);
// cout << u << " " << v << " " << ans << " " << sz[u] << " " << sz[v] << "\n";
for (int i = 0 ; i <= ans ; i++) f[i] = dp[u][i];
for (int i = 1 ; i <= sz[u] ; i++)
{
for (int z = 0 ; z <= i ; z++)
if (f[z] != -1 && dp[v][i - z] != -1 && f[z] + dp[v][i - z] + 1 >= k)
maximize(dp[u][i],min(f[z],dp[v][i - z] + 1));
}
}
// for (int i = 0 ; i <= sz[u] ; i++) if (dp[u][i] >= k) maximize(dp[u][i + 1],0);
// cout << u << " " << sz[u] << " :";
// for (int i = 0 ; i <= sz[u] ; i++) cout << dp[u][i] << " ";
// cout << "\n";
}
void case2()
{
DFS(0,0);
int res = 0;
for (int i = 0 ; i <= sz[0] ; i++)
if (dp[0][i] != -1) res = i;
cout << res;
}
void solve()
{
ans = (n / k) + 1;
if (k < ans) case1();
else case2();
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
if(fopen(TASK".inp", "r")){
freopen(TASK".inp","r",stdin);
freopen(TASK".out","w",stdout);
}
int tk;
tk = 1;
//cin >> tk;
while (tk--)
{
input();
solve();
}
return 0;
}
Compilation message
catinatree.cpp: In function 'int main()':
catinatree.cpp:137:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | freopen(TASK".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:138:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | freopen(TASK".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
