제출 #1267604

#제출 시각아이디문제언어결과실행 시간메모리
1267604vneduCat in a tree (BOI17_catinatree)C++17
0 / 100
3 ms4928 KiB
#include<bits/stdc++.h>
using namespace std;
#define TASK ""

const int N = 2e5 + 5;
int n,d;
vector<int> adj[N];
namespace sub12
{
    bool check()
    {
        return n<=1500;
    }
    const int N = 1500 + 5;
    int dp[N][N];
    void dfs(int u, int pa)
    {
        dp[u][0]=1;
        for(int v : adj[u])
        {
            if(v!=pa)
            {
                dfs(v,u);
                dp[u][0]+=dp[v][d-1];
                for(int j=1;j<=d;++j)
                {
                    for(int k=j;k<=d;++k)
                    {
                        dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][max(j-1,d-1-k)]);
                    }
                }
            }
        }
    }
    void solve()
    {
        dfs(1,-1);
        int ans=0;
        for(int j=0;j<=d;++j)
        {
            ans=max(ans,dp[1][j]);
        }
        cout<<ans;
    }
}
void solve()
{
    cin>>n>>d;
    for(int i=2;i<=n;++i)
    {
        int u;
        cin>>u;
        ++u;
        adj[i].push_back(u);
        adj[u].push_back(i);
    }
    if(sub12::check())
    {
        return void(sub12::solve());
    }
}
int main(void)
{
//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int testcase=1;
//    cin>>testcase;
    while(testcase--)
        solve();
//    cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...