Max sum distance on tree
Разница между en1 и en2, 39 символ(ов) изменены
Statement:↵

Given a tree of around $10^5$ nodes
 and around, $10^5$ queries. We are also given, 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 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский cuom1999 2020-09-09 22:24:32 6 Tiny change: 'or a while, but have not been ' -> 'or a while but not been '
en2 Английский cuom1999 2020-09-09 22:23:23 39 (published)
en1 Английский cuom1999 2020-09-09 22:21:49 615 Initial revision (saved to drafts)