| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1155833 | Ludissey | Cat in a tree (BOI17_catinatree) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int n,d;
vector<vector<int>> neigh;
vector<int> index;
vector<int> memo;
vector<int> dist;
vector<int> childC;
int mxC=0;
int build_tree(int x, int p){
childC[x]=1;
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t];
if(u==p||index[u]>=0) continue;
childC[x]+=build_tree(u,x);
}
return childC[x];
}
int centroid(int x, int p, int _n){
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t];
if(u==p||index[u]>=0) continue;
if(childC[u]*2>=_n) return centroid(u,x,_n);
}
return x;
}
void decompo(int x, int compoINDEX){
build_tree(x,-1);
if(childC[x]==1) { index[x]=compoINDEX; mxC=max(compoINDEX,mxC); return;}
int c=centroid(x,-1,childC[x]);
index[c]=compoINDEX;
mxC=max(compoINDEX,mxC);
for (auto u : neigh[c])
{
if(index[u]>=0) continue;
decompo(u,compoINDEX+1);
}
}
int calc(int x, int p, int dst, int indx){
dist[min(d,dst)]=max(dist[min(d,dst)],memo[x]);
int mx=dst;
for (auto u : neigh[x])
{
if(u==p||index[u]<=indx) continue;
mx=max(mx,calc(u,x,dst+1,indx));
}
return mx;
}
int dp(int x){
if(memo[x]!=-1) return memo[x];
vector<vector<int>> clc(sz(neigh[x]));
int mxS=0;
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t];
if(index[u]<=index[x]) continue;
mxS=max(calc(u,x,1,index[x]),mxS);
clc[t].resize(1);
clc[t][0]=0;
for (int i = 1; i <= d; i++)
{
if(dist[i]==-1) break;
clc[t][i]=dist[i];
dist[i]=-1;
}
}
mxS++;
vector<pair<int,int>> mxdist(mxS,{-1,-1});
mxdist[0]={0,0};
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t];
if(index[u]<=index[x]) continue;
for (int i = 0; i < sz(clc); i++)
{
if(clc[t][i]>mxdist[i].first) { mxdist[i].second=mxdist[i].first; mxdist[i].first=clc[t][i]; }
else if(clc[t][i]>mxdist[i].second) mxdist[i].second=clc[t][i];
}
}
memo[x]=1;
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t];
if(index[u]<=index[x]) continue;
for (int i = 0; i < sz(clc); i++)
{
if(d-i>=sz(mxdist)) continue;
int v=mxdist[d-i].first;
if(d-i<=sz(clc)&&v==clc[t][d-i]) v=mxdist[d-i].second;
memo[x]=max(memo[x],v+clc[t][i]+2);
}
}
return memo[x];
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> d;
index.resize(n,-1); childC.resize(n); dist.resize(d+1,-1); neigh.resize(n); memo.resize(n,-1);
for (int i = 1; i < n; i++)
{
int x; cin >> x;
neigh[x].push_back(i);
neigh[i].push_back(x);
}
decompo(0,0);
mxC++;
vector<vector<int>> grp(mxC);
for (int i = 0; i < n; i++)
{
grp[index[i]].push_back(i);
}
int ans=0;
for (int c = mxC-1; c >= 0; c--) {
for (auto u : grp[c])
{
ans=max(ans,dp(u));
}
}
cout << ans << "\n";
return 0;
}