# Find a pair of nodes with maximum sum of distances in k given trees

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

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