Max sum distance on tree

Revision en1, by cuom1999, 2020-09-09 22:21:49

Statement:

Given a tree of around $$$10^5$$$ nodes and around $$$10^5$$$ queries. We are also given an integer $$$k$$$. Each query has $$$k$$$ vertices $$$a_1, a_2, ..., a_k$$$. For each query, find a node $$$x$$$ such that $$$dist(x, a_1) + dist(x, a_2) + ... + dist(x, a_k)$$$ is maximum, then print that value. Here $$$dist(u, v)$$$ is the number of edge on the simple path from $$$x$$$ to $$$y$$$.

I have been thinking about this problem for a while, but have not been able to solve it, even for small $$$k$$$ like $$$2$$$ or $$$3$$$. Any idea on how to solve this problem? I appreciate all ideas and any sources of similar problems.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English cuom1999 2020-09-09 22:24:32 6 Tiny change: 'or a while, but have not been ' -> 'or a while but not been '
en2 English cuom1999 2020-09-09 22:23:23 39 (published)
en1 English cuom1999 2020-09-09 22:21:49 615 Initial revision (saved to drafts)