Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=213

For whatever reason, implementing any of the three official editorial solutions is not working out for me, so I am changing tact.

My idea is to store the depths relative to the root for each node, run a DFS and BIT similar to what I used in this problem, add/subtract values to/from the BIT according to a sliding window (e.g. when L = 3 and a node with depth 5 is at the bottom of the sliding window, nodes with depth of at most 8 are at the top), and query all nodes in the window that are ancestors of the node in question.

I would appreciate comments on my method.

Please help, and thanks in advance!

UPD: I coded my fourth attempted solution, only for it to fail the same cases (7, 8, and 9). I would appreciate it if someone could find out what is wrong with it, as I have wasted 8+ hours trying to upsolve this problem to get no variance/change in results.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

int N;
vector<int> children [200001];
pair<long long, int> pis [200001];
int tree [200001], id [200001], mx [200001], ret [200001], curr = 1, index = 1;
long long L, depth [200001];

void add(int pos, long long x){
    while(pos < 200001){
        tree[pos] += x;
        pos += (pos&-pos);
    }
}

int query(int pos){
    int sum = 0;
    while(pos > 0){
        sum += tree[pos];
        pos -= (pos&-pos);
    }
    return sum;
}

int dfs(int x){
    id[x] = curr++; mx[x] = id[x];
    for(int i = 0; i < children[x].size(); i++){
        int next = children[x][i];
        mx[x] = max(mx[x], dfs(next));
    }
    return mx[x];
}

int main(){
    //freopen("runaway.in", "r", stdin); freopen("runaway.out", "w", stdout);
    scanf("%d %d", &N, &L); depth[0] = 0ll;
    for(int i = 2; i <= N; i++){
        int x; long long y; scanf("%d %I64d", &x, &y);
        children[x].push_back(i); depth[i] = depth[x]+y;
    }
    dfs(1);
    for(int i = 1; i <= N; i++) pis[i] = make_pair(depth[i], i);
    sort(pis+1, pis+N+1);
    for(int i = 1; i <= N; i++){
        long long curDepth = pis[i].first; int now = pis[i].second; int from = id[now]; int to = mx[now];
        while(index <= N && curDepth+L >= depth[pis[index].second]){
            add(id[pis[index].second], 1);
            index++;
        }
        ret[now] = query(to)-query(from-1);
    }
    for(int i = 1; i <= N; i++) cout << ret[i] << '\n';
    return 0;
}