Solution Notes (Travis Hance and Richard Peng):
The problem asks us to find, given a rooted tree T, for each node v, the number
of descendants within a certain distance L. If we assign to each node v its
depth (that is, the distance of that node from the root), then for a node v of
depth D, we just want to count the number of descendants of depth at most D+L.
The simplest and most concise way of doing this problem is to 'flip over' what we need to compute.
For each vertex, we find how far up the tree is within a distance of L from it.
This can be done either by doing a DFS traversal of the tree and binary
searching on the search stack, or by building 'jump' pointers of distance
2i upwards in the tree.
Once this information is found, all we need to do is convert it back into information about
descendants.
This could be done by marking the first position up the tree that's at a distance of more than L from it.
The answer at a vertex can then be computed by summing over the answers for its descendants, and
subtracting away the number of times the current vertex is marked.
A very concise and well written solution by Roman Rubanenko is below.
His code computed tables that move up the tree by a distance of 2i,
and made clever use of the fact that the parent of node i is at a smaller index
Var ans,d:array[0..200333]of int64;
i,n,j,v:longint;
len:int64;
p:array[0..200333,0..19]of longint;
begin
assign(input,'runaway.in');reset(input);
assign(output,'runaway.out');rewrite(output);
read(n,len);
ans[1]:=1;
for i:=2 to n do
begin
read(p[i,0]);
read(d[i]);
d[i]:=d[i]+d[p[i,0]];
for j:=1 to 18 do
p[i,j]:=p[p[i,j-1],j-1];
v:=i;
for j:=18 downto 0 do
if d[i]-d[p[v,j]]<=len then v:=p[v,j];
inc(ans[i]);
dec(ans[p[v,0]]);
end;
for i:=n downto 1 do
ans[p[i,0]]:=ans[p[i,0]]+ans[i];
for i:=1 to n do
Writeln(ans[i]);
end.
A more complicated solution would be to count the number of descendants
of each node directly.
For a node v, we will say the set of such descendants is S(v).#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
#define NMAX 200005
struct entry {
long long weight;
long long depth;
bool operator<(entry const& o) const {
return depth < o.depth;
}
};
struct node {
vector<node*> children;
int sizeInNodes;
long long answer;
priority_queue<entry>* q;
long long weight;
long long qweight;
long long dist;
};
node nodes[NMAX];
long long l;
void dfs(node* v, long long depth) {
v->sizeInNodes = 1;
node* largestChild = NULL;
for (int i = 0; i < v->children.size(); i++) {
node* c = v->children[i];
dfs(c, depth + c->dist);
v->sizeInNodes += c->sizeInNodes;
if (largestChild == NULL || c->sizeInNodes >
largestChild->sizeInNodes) {
largestChild = c;
}
}
if (largestChild == NULL) {
v->q = new priority_queue<entry>();
v->qweight = 0;
} else {
v->q = largestChild->q;
v->qweight = largestChild->qweight;
while (v->q->size() > 0 && v->q->top().depth > depth
+ l) {
v->qweight -= v->q->top().weight;
v->q->pop();
}
}
for (int i = 0; i < v->children.size(); i++) {
node* c = v->children[i];
if (c != largestChild) {
while (c->q->size() > 0) {
entry e = c->q->top();
c->q->pop();
if (e.depth <= depth + l) {
v->q->push(e);
v->qweight += e.weight;
}
}
}
}
entry e;
e.weight = v->weight;
e.depth = depth;
v->q->push(e);
v->qweight += e.weight;
v->answer = v->qweight;
}
int main() {
freopen("runaway.in","r",stdin);
freopen("runaway.out","w",stdout);
int n;
scanf("%d", &n);
scanf("%lld", &l);
nodes[0].weight = 1;
nodes[0].dist = 0;
for (int i = 1; i < n; i++) {
int parent;
scanf("%d", &parent);
parent--;
nodes[parent].children.push_back(&nodes[i]);
nodes[i].weight = 1;
scanf("%lld", &nodes[i].dist);
}
dfs(&nodes[0], 0);
for (int i = 0; i < n; i++) {
printf("%lld\n", nodes[i].answer);
}
}
Here is a solution by Bruce Merry using the second approach:
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
struct node
{
node *parent;
vector<node *> children;
ll depth;
int last;
int label;
node() : parent(NULL), depth(0), last(-1) {}
void make_labels(int &pool)
{
label = pool++;
for (size_t i = 0; i < children.size(); i++)
children[i]->make_labels(pool);
if (children.empty())
last = label;
else
last = children.back()->last;
}
};
struct event
{
int A, B;
ll l;
int idx;
bool operator <(const event &b) const
{
if (l != b.l)
return l < b.l;
else
return A < b.A;
}
};
static void bit_add(vector<int> &bit, int p, int v)
{
p++;
while (p < int(bit.size()))
{
bit[p] += v;
p += p & ~(p - 1);
}
}
static int bit_get(const vector<int> &bit, int p)
{
int ans = 0;
p++;
while (p > 0)
{
ans += bit[p];
p &= p - 1;
}
return ans;
}
int main()
{
ifstream in("runaway.in");
ofstream out("runaway.out");
int N;
ll L;
in >> N >> L;
node *nodes = new node[N];
nodes[0].last = 0;
for (int i = 1; i < N; i++)
{
int p;
ll l;
in >> p >> l;
p--;
node *pr = nodes + p;
nodes[i].parent = pr;
nodes[i].depth = pr->depth + l;
pr->children.push_back(nodes + i);
}
int label_pool = 0;
nodes[0].make_labels(label_pool);
vector<event> events;
events.reserve(2 * N);
for (int i = 0; i < N; i++)
{
event add;
add.A = -1;
add.B = -1;
add.l = nodes[i].depth;
add.idx = nodes[i].label;
events.push_back(add);
event q;
q.A = nodes[i].label;
q.B = nodes[i].last + 1;
q.l = nodes[i].depth + L;
q.idx = i;
events.push_back(q);
}
vector<int> ans(N);
vector<int> bit(N + 1);
sort(events.begin(), events.end());
for (int i = 0; i < int(events.size()); i++)
{
const event &e = events[i];
if (e.A == -1)
{
// add
bit_add(bit, e.idx, 1);
}
else
{
// query
ans[e.idx] = bit_get(bit, e.B - 1) - bit_get(bit, e.A - 1);
}
}
for (int i = 0; i < N; i++)
out << ans[i] << '\n';
delete[] nodes;
}