5
$\begingroup$

For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ denotes the sum of weights of the edges in the path between x and y in $T_i$.

Recently I came across the $k \leq 3$ version of this problem, which can be solved in $O(n\log(n))$. But for general k, is there any way to get a complexity lower than $O(n^2)$ (assuming k is a constant)?

$\endgroup$
  • $\begingroup$ Is there any relation between the trees other than that they contain the same nodes? $\endgroup$ – John Dvorak Feb 26 '18 at 10:18
  • $\begingroup$ I assume there's nope. I forgot to mention n in the question :/ my fault. $\endgroup$ – newbie Feb 26 '18 at 11:21
  • 1
    $\begingroup$ Is there a reference for the $k\leq 3$ algorithm? $\endgroup$ – Chao Xu Feb 26 '18 at 20:20
  • $\begingroup$ @ChaoXu uoj.ac/problem/347 solution: drive.google.com/file/d/1J2vOg9UEHVpHquhMTkCu5iQh3bU0JZpO/… (in chinese) $\endgroup$ – newbie Feb 27 '18 at 0:04
  • 1
    $\begingroup$ @daniello in your example, take k1=k2=1, v1 is the point with maximum k1*x+k2*y, and u1 is the point with minimum. We're not taking extremal points along axis, but for every vector of length k consisted of {-1,1}, taking scalar products with these points and check the maximum and minimum. $\endgroup$ – newbie Mar 1 '18 at 10:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.