1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ An algorithm that runs in $n\log n$ isn't sublinear. Did you mean to write something else, there? Also, depending on context, a $\Theta(n^2)$ algorithm may well be fine on 100,000 vertices: $10^{10}$ steps is only a few seconds on a modern processor. $\endgroup$ – David Richerby Sep 2 '14 at 17:02
  • $\begingroup$ Sorry, what I meant was that it should be close to linear, and I'm pretty sure that the solution has to be significantly faster than O(n^2). $\endgroup$ – Cris Sep 2 '14 at 17:16
  • $\begingroup$ What have you tried? What approaches have you considered? What's the best algorithm you were able to come up with? Have you been able to find any special cases where you can solve it? $\endgroup$ – D.W. Sep 3 '14 at 6:39
2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Thanks a lot! That's a bit complicated to code, but I'm half way through doing it. $\endgroup$ – Cris Sep 3 '14 at 9:47
0
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ I thought of this approach, but the altogether number of queries is equal to the sum of distances of all vertices from the root. The tree can have a long diameter, i.e. be a path, and then no good choice for the root exists. Also, my tree doesn't have to be binary. $\endgroup$ – Cris Sep 3 '14 at 9:38
  • $\begingroup$ Quite right, @Cris, thank you for the correction. $\endgroup$ – D.W. Sep 3 '14 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.