Max sum distance on tree

Revision en3, by cuom1999, 2020-09-09 22:24:32


Given a tree of around $$$10^5$$$ nodes, $$$10^5$$$ queries, and 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 maximum value. Here $$$dist(u, v)$$$ is the number of edges on the simple path from $$$x$$$ to $$$y$$$.

I have been thinking about this problem for a while but 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.


  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)