Hey, I've been trying to solve the following problem and I have no idea how to go further.
You are given 2 weighted undirected trees $$$T_1$$$ and $$$T_2$$$ such that both trees have $$$n$$$ vertices. You have to find the pair of vertices $$$(v, u)$$$ such that the value of $$$f_1(v, u)+f_2(v, u)$$$ is minimal where $$$f_i(v, u)$$$ is the maximum weight on edge on the path from $$$v$$$ to $$$u$$$ in $$$i$$$-th tree (only output the minimal value, no need to output vertices).
$$$n \leq 10^6$$$ and $$$w_i \leq 10^9$$$ (where $$$w_i$$$ is weight on $$$i$$$-th edge)
I thought about converting those trees to Line trees and then doing some D&C but it doesn't seem to work and I have no idea how to go further. I'm rather looking for some hints than a whole solution. Thanks in advance!
I hope it doesn't spoil the solution immediately, but if you have 2 neighbouring nodes $$$u$$$ and $$$v$$$ then let's say they have cost $$$f_1+f_2$$$. Then any pair of nodes whose path goes through $$$u$$$ and $$$v$$$ will have at least the same cost.
It doesn't have to be true. While vertices $$$(v, u)$$$ might be neighbouring in $$$T_1$$$ they don't have to be adjacent in $$$T_2$$$. (i.e. structures of both trees are Independent from each other).
Oh, yes, I missed that
Convert both to Line Trees. Problems are always easier to solve on chains than on trees.
Build cartesian tree on one of them, and use the "merge small into big" trick (I don't know what is it called, maybe DSU on tree?)
Reverse the whole process.
Consider that we already have built the "line tree" (or I prefer to call it chain).
We build the cartesian tree on the first chain, and when we try to merge 2 subtrees containing vertexes $$$S_1,S_2$$$ (let $$$|S_1| \lt |S_2|$$$):
Using some data structures to do this will yield a $$$O(n\log^2n)$$$ solution, which is not possible to pass $$$10^6$$$.
However, we can reverse this merging process and turn it into splitting $$$S_1\cup S_2$$$ into $$$S_1$$$ and $$$S_2$$$. This way, our data structure only need to support deletion and querying precessor/successor of an existing element, which can be done by a bidirectional list. Therefore, we get everything done in $$$O(n\log n)$$$.
upd. Sorry I made a mistake. We still need to concatenate the removed elements of the smaller set in the correct order. Doing this with radix sort will keep the complexity at $$$O(n\log n)$$$. Quick sort will result in $$$O(n\log^2n)$$$ but with a significantly better constant factor than using data structures to maintain merging sets.