Consider a weighted tree $T = (V,E)$. The bottleneck weight for a pair of vertices $v_1,v_2 \in V$ is the highest weight of the edges on the unique path from $v_1$ to $v_2$ (if $v_1 = v_2$ it is 0). Clearly, using a simple graph traversal from a given node we can find the bottleneck weight from that node to all other nodes in $\mathcal O(|V|)$ time, so we can find all $V^2$ bottleneck weights in $\mathcal O(|V|^2)$ time.
I am interested in the situation where $V$ is large, and we are not interested in finding bottlenecks for all pairs $(v_1,v_2)$, but nonetheless for an (also large) number of pairs $Q$ (the letter $Q$ stands for queries).
I am wondering whether it is possible to do some preprocessing in less than $\mathcal O(|V|^2)$ time -- in particular, in $\mathcal O(|V|\log|V|)$ -- so that we produce some search mechanism, which will then produce a bottleneck weight for $(v_1,v_2)$ in $\mathcal O(\log |V|)$ time. Then we can produce the answer to all queries in $\mathcal O(|V|\log |V| + Q\log|V|)$.
Note that there are $\mathcal O(|V|)$ edges, and thus also that many possible answers to a query. Hence, a balanced decision tree whose leaves are the edge weights, which takes pairs of vertices and decides the highest weight edge between them -- if such a tree exists -- would do the job.
One attempt to build the tree was as follows: recursively split the original tree by removing the highest weight edge. Assign the nodes of the tree indices so that both resulting trees have indices in a contiguous range. Then make a node in the decision tree, which when given two vertices decides whether they lie in the same of the two ranges; if not, this search tree node represents the highest weight edge between the vertices; if so, continue in either of the children of the search tree node.
Unfortunately, this construction fails as the decision tree need not be balanced. Consider, for example, the tree which is just a simple path with ever decreasing weights along the path. Balancing the tree does not seem to be an option, as the decision procedures created by the balancing operations grow too fast (traversing the tree would take too long).
Any suggestions or insights are welcome.
