Submission #1186704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186704		hikari1234	Cat in a tree (BOI17_catinatree)	C++20	51 / 100	1105 ms	251436 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
int n,d;
vector<int> adj[200005];
deque<int> dp[200005];
void dfs(int node, int pre){
    dp[node].push_front(1);
    for(int &i: adj[node]){
        if(i==pre) continue;
        dfs(i,node);
        dp[i].push_front(dp[i][0]);
        if(dp[node].size()<dp[i].size()){
            swap(dp[node],dp[i]);
        }
        for(int j=0; j<dp[i].size(); j++){
            int x=dp[node][j], y=dp[node][j];
            int p=max(d-j, j);
            if(p<dp[i].size()){
                x=max(x,dp[i][p]+dp[node][j]);   
            }
            if(p<dp[node].size()){
                y=max(y,dp[node][p]+dp[i][j]);
            }
            dp[node][j]=max({dp[node][j],x,y});
        }
        for(int j=dp[node].size()-1; j>=0; j--){
            if(j+1<dp[node].size()){
                dp[node][j]=max(dp[node][j],dp[node][j+1]);
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    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);
    }
    dfs(1,0);
    cout<<dp[1][0]<<endl;
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 0 / 49