B

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<int> solve(vector<int> &arr, int n, int k) {
    vector<int> dp(n + 1);
    for (int i = 1; i <= n; ++i) {
        int left = max(1, i - k), right = min(n, i + k);
        int pright = arr[i] ? min(n, arr[i] + k) + 1 : 0;
        if (pright > left) left = pright;
        dp[i] = dp[arr[i]] + right - left + 1;
    }
    return dp;
}

vector<int> stupid_solve(vector<int> arr, int n, int k) {
    vector<bool> used(n+1);
    vector<int> ans(n+1);
    for (int i = 1; i <= n; ++i) {
        int v = i;
        used.assign(n+1, 0);
        while (1) {
            if (v == 0) break;
            for (int j = max(1, v-k); j <= min(n, v+k); ++j){
                used[j] = 1;
            }
            v = arr[v];
        }
        for (int j = 1; j <= n; ++j) {
            ans[i] += used[j];
        }
    }
    return ans;
}

void stress(int n, int k) {
    vector<int> v(n+1);
    for (int i = 1; i <= n; ++i) {
        v[i] = rand() % i;
    }
    vector<int> v1 = stupid_solve(v, n, k),
                v2 = solve(v, n, k);
    for (int i = 1; i <= n; ++i) {
        if (v1[i] != v2[i]) {
            printf("ALERTALERT: n=%d, k=%d, the array is: ", n, k);
            for (int i = 1; i <= n; ++i) {
                printf("%d ", v[i]);
            }
        }
    }
}

int main() {
    srand(time(NULL));
    for (int i = 0; i < 10000; ++i) {
        int n = rand() % 100 + 1;
        int k = rand() % (n+1);
        stress(n, k);
    }
    return 0;
}