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](http://codeforces.net/blog/entry/53060), 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;↵
}↵
~~~~~
↵
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](http://codeforces.net/blog/entry/53060), 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;↵
}↵
~~~~~
