4
$\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)?

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

0

Reset to default

Your Answer

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