Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Given a tree, if an edge is removed resulting in 2 subtrees, how to find the end nodes of a diameter for each subtree? (many such queries)

Правка en2, от pabloskimg, 2019-08-11 21:23:49

I have a tree, and if I remove an edge the tree would get disconnected into 2 subtrees. Now, for each of these 2 subtrees I would like to find (quickly) 2 end nodes of a diameter, that is, I would like to find the end nodes of a diameter of subtree 1 and the end nodes of a diameter of subtree 2 (4 nodes in total). I need to do this for many possible edges (edge removals don't accumulate). Is it possible to do that efficiently? I need this in order to solve this problem. Otherwise I will need to figure out another approach. Thank you in advance.

Теги #trees, #diameter, #graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский pabloskimg 2019-08-11 21:23:49 2 Tiny change: 'e, and if a remove an' -> 'e, and if I remove an'
en1 Английский pabloskimg 2019-08-11 07:56:48 739 Initial revision (published)