If you want to make money online : Register now

Number of path with given length within an unrooted Tree

, , No Comments
Problem Detail: 

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.

Asked By : user2184057

Answered By : D.W.

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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40963

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback