#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 640;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
int N, D, dis[MAXN], cat_cnt, mxdep[MAXN];
int dp[MAXN][ROOTN];
bool vis[MAXN];
vi g[MAXN];
void dfs(int a, int par)
{
for(int b : g[a])
if(b != par)
dfs(b, a), dp[a][0] += dp[b][D-1];
F0Rrev(i, D-1)
{
if(i == 0)
break;
int x = i;
int y = max(i, D-i), sm = 0, mx = 0;
for(int b : g[a])
if(b != par)
sm += dp[b][y-1], mx = max(dp[b][x-1] - dp[b][y-1], mx);
dp[a][i] = sm + mx;
if(i < D-1)
dp[a][i] = max(dp[a][i], dp[a][i+1]);
}
dp[a][0] = max(dp[a][0], dp[a][1]);
F0R(i, D)
{
// cout<<"dp["<<a-1<<"]["<<i<<"] = "<<dp[a][i]<<'\n';
cat_cnt = max(cat_cnt, dp[a][i]);
}
}
int dfs_find_end(int a, int p = -1){
int ans = a;
for(int b : g[a]){
if(b != p && !vis[b]){
dis[b] = 1 + dis[a];
int t = dfs_find_end(b, a);
if(dis[t] > dis[ans]){
ans = t;
}
}
}
return ans;
}
void dfs_from_end(int a, vector<int>& V, int p = -1){
for(int b : g[a]){
if(b != p && !vis[b]){
dis[b] = 1 + dis[a];
cerr << "dis[" << b << "] = " << dis[b] << '\n';
if(dis[b] < D){
vis[b] = true;
cerr << "blocking " << b << '\n';
}else if(dis[b] == D){
V.pb(b);
}
dfs_from_end(b, V, a);
}
}
}
int dfs_mxdep(int a, int p = -1){
int t = a;
for(int b : g[a]){
if(b != p){
dis[b] = dis[a] + 1;
int y = dfs_mxdep(b, a);
if(dis[t] < dis[y]){
t = y;
}
}
}
mxdep[a] = dis[t];
return t;
}
int cnt;
int dfs_cnt(int a, int p = -1, int dis = D + 1){
for(int b : g[a]){
if(b != p){
dis = min(dis, 1 + dfs_cnt(b, a, dis + 1));
}
}
if(dis >= D){
// cerr << "dis for " << a << " is " << dis << "\n";
++cnt;
dis = 0;
}
return dis;
}
int solve(int a){
dis[a] = 0;
dfs_mxdep(a);
a = 1;
F0Re(i, N){
if(dis[a] < dis[i]){
a = i;
}
}
dis[a] = 0;
dfs_mxdep(a);
F0Re(i, N){
sort(all(g[i]), [&](int a, int b){return mxdep[a] > mxdep[b];});
}
cnt = 0;
dfs_cnt(a);
return cnt;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>N>>D;
srand(time(NULL));
cat_cnt = 1;
F0Re(i, N)
dis[i] = inf, mxdep[i] = 0;
// F0Re(i, N)
// F0R(j, D)
// dp[i][j] = (j==0) ? 1 : 0;
F0Re(i, N-1)
{
int j;
cin>>j;
g[i+1].pb(j+1);
g[j+1].pb(i+1);
}
if(D >= N)
{
cout<<"1\n";
exit(0);
}
if(D == 1)
{
cout<<N<<'\n';
exit(0);
}
// dbgLine;
if(D >= ROOTN){
F0Re(i, N){
vis[i] = false;
}
int TTT = 1;//(N > 1500) ? 40 : 100;
int ans = 1;
while(TTT--){
ans = max(ans, solve(1 + rand() % N));
}
cout << ans << '\n';
exit(0);
}
F0Re(i, N)
sort(all(g[i]), cmp);
F0Re(i, N)
F0R(j, D)
dp[i][j] = (j==0) ? 1 : 0;
dfs(1, -1);
cerr << cat_cnt << '\n';
return 0;
}
Compilation message
catinatree.cpp: In function 'int main()':
catinatree.cpp:209:19: error: 'cmp' was not declared in this scope; did you mean 'bcmp'?
209 | sort(all(g[i]), cmp);
| ^~~
| bcmp
