1
$\begingroup$

Given a Tree (without a root) function w : v -> N and a number C - How can we count the number of verticies with distance between them equal to C.

I was thinking about some smart vertice numbering so we could use dynamic programing to do it but after some thinking it is no good.

I would be really thankful for any tips.

$\endgroup$
1
$\begingroup$

Hint: divide-and-conquer. How many paths are there of length C in the left subtree of the root? How many in the right subtree? How many others not covered by either of those two cases?

$\endgroup$
  • 1
    $\begingroup$ Well no one sad it is a binary tree but i get your idea. It will be a little more difficult with costs instead of lenghts and unrooted tree. I wilk need to remember all paths whose weigth is less then C for each vertex. It can get out of hand pretty quickly in terms of Memory... $\endgroup$ – user2184057 Apr 2 '15 at 6:35

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.