Обсуждение @ 1471. Расстояние в дереве @ Timus Online Judge

Why wa at test 3?

Послано SPIRiT 29 сен 2006 17:10

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

Re: Why wa at test 3?

Послано Andrey Veselovskiy 29 сен 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?

Послано Kaliningrad SU -J_A_MES-HeadLiner 29 сен 2006 21:17

Binary search rules!

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

Послано SPIRiT 23 окт 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?

Обсуждение задачи 1471. Расстояние в дереве