Submission #1322290

#TimeUsernameProblemLanguageResultExecution timeMemory
1322290lopkusCat in a tree (BOI17_catinatree)C++20
100 / 100
80 ms28392 KiB
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=2e5+5;
int n,D;
vector<int>g[MAX_N];
vector<int>dp[MAX_N];
int height[MAX_N];

void merge(int u,int v)
{
    vector<int>tmp;

    for(int curdepth=0;curdepth<dp[v].size();curdepth++)
    {
        int curbest=dp[v][dp[v].size()-1-curdepth];
        int curval=dp[v][dp[v].size()-1-curdepth];
        int otherdepth=max(curdepth+1,D-curdepth-1);
        if(otherdepth<dp[u].size())
        {
            curval+=dp[u][dp[u].size()-1-otherdepth];
            curbest=max(curbest,curval);
        }
        //case 1

        curval=0;
        if(dp[u].size()>(curdepth+1))curval=dp[u][dp[u].size()-1-(curdepth+1)];
        otherdepth=max(curdepth,D-(curdepth+1)-1);
        if(curval!=0 && otherdepth<dp[v].size())
        {
            curval+=dp[v][dp[v].size()-1-otherdepth];
            curbest=max(curbest,curval);
        }
        //case 2

        tmp.push_back(curbest);
    }

    for(int newdepth=dp[v].size();newdepth>=1;newdepth--)
    {
        int curval=tmp[newdepth-1];
        int pos=dp[u].size()-1-newdepth;
        dp[u][pos]=max(dp[u][pos],curval);
        if(pos)dp[u][pos]=max(dp[u][pos],dp[u][pos-1]);
    }

    vector<int>().swap(dp[v]);
}

void initdfs(int u,int par)
{
    height[u]=1;
    for(int v:g[u])
    {
        if(v==par)continue;
        initdfs(v,u);
        height[u]=max(height[u],height[v]+1);
    }
}

void dfs(int u,int par)
{
    int mx=-1,bigchild=-1;
    for(int v:g[u])
    {
        if(v==par)continue;

        if(height[v]>mx)
        {
            mx=height[v];
            bigchild=v;
        }
    }

    if(bigchild==-1)
    {
        dp[u].push_back(1);
        return;
    }

    dfs(bigchild,u);
    swap(dp[bigchild],dp[u]);
    vector<int>().swap(dp[bigchild]);

    int d1=0;
    if(dp[u].size()>D-1)d1=dp[u][dp[u].size()-1-(D-1)];
    dp[u].push_back(d1+1);

    int zerocase=0;
    for(int v:g[u])
    {
        if(v==par or v==bigchild)continue;
        dfs(v,u);
        if(dp[v].size()>D-1)
        {
            zerocase+=dp[v][dp[v].size()-1-(D-1)];
        }
        merge(u,v);
    }

    dp[u].back()+=zerocase;
    dp[u].back()=max(dp[u][dp[u].size()-2],dp[u].back());
}

int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>n>>D;
    for(int i=1;i<n;i++)
    {
        int x;
        cin>>x;
        g[x].push_back(i);
        g[i].push_back(x);
    }
    
    initdfs(0,-1);
    
    dfs(0,-1);

    cout<<dp[0].back()<<"\n";
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...