For each vertex of a tree count vertices closer than a specified value

Question

We have a weighted tree of $n\leq 10^5$ nodes, and for every node $v$, value $L(v)$. The goal is to calculate, for every vertex $v$, number of vertices $u$ such that $\mathrm{dist}(v,u)\leq L(v)$. This is a task from a programming contest. Judging by the limit on $n$, and also specifics of time limits on this contest, the desired complexity should be close to linear, i.e. $O(n \log n)$.

If the tree was rooted, and we were asked to count vertices $u$ that are also in a subtree of $v$, then the task could be solved by in-order traversal and a segment tree. However, this doesn't seem to help with this more general problem.

Answer 1

As it is a contest problem, I will give you some tips which may be a good start point.

1. Consider an easier problem: the graph has a vertex $v$ and multiple paths going out of it (they are straight). Of course, the result for vertex $v$ is easy to compute (one DFS). Now try to use the binary search to find the result for remaining vertices (tip: make a sorted list of distances from $v$ to all the other vertices in whole graph and in each separate branch).

2. Now the real problem. Choose any vertex $v$. We can compute the result for it using usual DFS. What if we remove this vertex? Let's say we computed recursively the result in each of the generated subtrees. Then for each vertex $w$ other than $v$ we need to add the number of vertices $s$ outside the $v$-subtree containing $w$ (formally, vertices $s$ such that $d(s,w)\le L(w)$ and $s\to w$ path contains vertex $v$). Try to do it in total $O(n \log n)$ time using the experience from point (1.).

3. Can you choose such vertex $v$ in the graph such that the size of the subtrees after removing $v$ doesn't exceed half of the initial size? Assuming you can, prove that the total running time is $O(n \log^2 n)$.

Answer 2

Since this is a contest problem, I'll just give a hint at one possible approach.

It sounds like you know how to efficiently answer queries of the form "how many vertices are of distance $\le d$ from $v$ and are within the subtree under $w$?".

So, try using that as a subroutine. Assume this is a rooted binary tree. Look at the path from $v$ to the root. In particular, consider $v$'s sibling, $v$'s father's sibling, $v$'$ grandfather's sibling, and try issuing an appropriate query for each. What will the running time be? Does this give you any tips on how to choose the root to make the resulting algorithm efficient?

Update: This doesn't suffice for $O(n \lg n)$ running time, because there may be no way to choose the root so that the average depth of a random leaf is $o(n)$.