Find a pair of vertices with the minimum sum of distances

Revision en1, by zeropointone, 2022-01-02 15:37:51

Good afternoon! Recently I faced the following problem: given k trees on n vertices, let p[i](a, b) be the distance from vertex a to vertex b in the i-th tree. It is necessary to find two vertices x and y such that p[0](x, y) + ... + p[k-1](x, y) is minimal (i.e. choose a pair of points such that the sum of the distances from one to the other across all trees will be minimal). As I understood, it is necessary to use centroid decomposition for the solution, but I don't quite understand how to apply it here :( If you have any ideas, write them in the comments. Thank you in advance!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English zeropointone 2022-01-03 19:10:36 642
ru3 Russian zeropointone 2022-01-03 19:09:50 525
en2 English zeropointone 2022-01-02 18:05:11 105
en1 English zeropointone 2022-01-02 15:37:51 645 Initial revision for English translation
ru2 Russian zeropointone 2022-01-02 15:35:47 0 (опубликовано)
ru1 Russian zeropointone 2022-01-02 15:33:40 609 Первая редакция (сохранено в черновиках)