Discussion @ 1471. Distance in the Tree @ Timus Online Judge

Why wa at test 3?

Posted by SPIRiT 29 Sep 2006 17:10

I see many people had problems with test 3. Anything special about it?

Re: Why wa at test 3?

Posted by Andrey Veselovskiy 29 Sep 2006 18:16

I think it's not special.

it's only LCA algo.
http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestor_algorithm

Re: Why wa at test 3?

Posted by Kaliningrad SU -J_A_MES-HeadLiner 29 Sep 2006 21:17

Binary search rules!

I've solved it, but not with Tarjan algo, but with binary heap help(-)

Posted by SPIRiT 23 Oct 2006 13:01

The idea was to store branches and their parents. I.e. we select the longest branch and make it root. After that we select second longest branch and so on. This is done with binary heap. After that we know for each vertex index of branch it belongs to, and it's parent. This all is done in O(NlogN) time. As far as I understand Tarjan algo uses Union disjoint structure. Did anyone use my approach?

Discussion of Problem 1471. Distance in the Tree