제출 #1322521

#제출 시각아이디문제언어결과실행 시간메모리
1322521TsaganaCat in a tree (BOI17_catinatree)C++20
100 / 100
107 ms23580 KiB
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int n, d;
int a[200010];
vector<int> adj[200010];
int dis[200010], dp[200010];

void dfs(int s, int p) {
    dis[s] = INT_MAX;
    for (auto i: adj[s]) {
        if (i == p) continue;
        dfs(i, s);
        if (dis[s] + dis[i] + 1 >= d) {
            dp[s] += dp[i];
            dis[s] = min(dis[s], dis[i] + 1);
        }
        else {
            dp[s] += dp[i] - 1;
            dis[s] = max(dis[s], dis[i] + 1);
        }
    }
    if (dis[s] >= d) {
        dp[s]++;
        dis[s] = 0;
    }
}

void solve () {
    cin >> n >> d;
    for (int i = 1; i <= n - 1; i ++) {
        int p;
        cin >> p;
        adj[i].pb(p);
        adj[p].pb(i);
    }
    dfs(0, 0);
    cout << dp[0];
}
signed main() {IOS solve(); return 0;}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...