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)?

  • $\begingroup$ Is there any relation between the trees other than that they contain the same nodes? $\endgroup$ Commented Feb 26, 2018 at 10:18
  • $\begingroup$ I assume there's nope. I forgot to mention n in the question :/ my fault. $\endgroup$
    – newbie
    Commented Feb 26, 2018 at 11:21
  • 1
    $\begingroup$ Is there a reference for the $k\leq 3$ algorithm? $\endgroup$
    – Chao Xu
    Commented Feb 26, 2018 at 20:20
  • $\begingroup$ @ChaoXu uoj.ac/problem/347 solution: drive.google.com/file/d/1J2vOg9UEHVpHquhMTkCu5iQh3bU0JZpO/… (in chinese) $\endgroup$
    – newbie
    Commented Feb 27, 2018 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
    Commented Mar 1, 2018 at 10:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.