+\df{lowest common ancestor} of~$x$ and~$y$ in~$T$. It is therefore sufficient to
+consider only paths that connect a~vertex with one of its ancestors.
+
+When we combine the two transforms, we get:
+
+\lemman{Balancing of trees}\id{verbranch}%
+For each tree~$T$ on $n$~vertices and a~set~$Q$ of $q$~query paths on~$T$, it is possible
+to find a~complete branching tree~$T'$, together with a~set~$Q'$ of paths on~$T'$,
+such that the weights of the heaviest edges of the paths in~$Q$ can be deduced from
+the same of the paths in~$Q'$. The tree $T'$ has at most $2n$ vertices and $\O(\log n)$
+levels. The set~$Q'$ contains at most~$2q$ paths and each of them connects a~vertex of~$T'$
+with one of its ancestors. The construction of~$T'$ involves $\O(n)$ comparisons
+and the transformation of the answers takes $\O(q)$ comparisons.
+
+\proof
+The tree~$T'$ will be the Bor\o{u}vka tree for~$T$, obtained by running the
+contractive version of the Bor\o{u}vka's algorithm (Algorithm \ref{contbor})
+on~$T$. The algorithm runs in linear time, for example because trees are planar
+(Theorem \ref{planarbor}). We therefore spend $\O(n)$ comparisons in it.
+
+As~$T'$ has~$n$ leaves and it is a~complete branching tree, it has at most~$n$ internal vertices,
+so~$n(T')\le 2n$ as promised. Since the number of iterations of the Bor\o{u}vka's
+algorithm is $\O(\log n)$, the depth of the Bor\o{u}vka tree must be logarithmic as well.
+
+For each query path $T[x,y]$ we find the lowest common ancestor of~$x$ and~$y$
+and split the path by the two half-paths. This produces a~set~$Q'$ of at most~$2q$ half-paths.
+The peak of every original query path is then the heavier of the peaks of its halves.
+\qed
+
+\paran{Bounding comparisons}%
+We will now describe a~simple variant of the depth-first search which finds the
+peaks of all query paths of the balanced problem. As we promised,
+we will take care of the number of comparisons only, as long as all other operations
+are well-defined and they can be performed in polynomial time.
+
+\defn
+For every edge~$e=uv$, we consider the set $Q_e$ of all query paths containing~$e$.
+The vertex of a~path, that is closer to the root, will be called the \df{top} of the path,
+the other vertex its \df{bottom.}
+We define arrays $T_e$ and~$P_e$ as follows: $T_e$ contains
+the tops of the paths in~$Q_e$ in order of their increasing depth (we
+will call them \df{active tops} and each of them will be stored exactly once). For
+each active top~$t=T_e[i]$, we define $P_e[i]$ as the peak of the path $T[v,t]$.
+
+\obs
+As for every~$i$ the path $T[v,T_e[i+1]]$ is contained within $T[v,T_e[i]]$,
+the edges of~$P_e$ must have non-increasing weights, that is $w(P_e[i+1]) \le
+w(P_e[i])$.
+This leads to the following algorithm:
+
+\alg $\<FindPeaks>(u,p,T_p,P_p)$ --- process all queries located in the subtree rooted
+at~$u$ entered from its parent via an~edge~$p$.
+\id{findpeaks}
+
+\algo
+\:Process all query paths whose bottom is~$u$ and record their peaks.
+This is accomplished by finding the index~$i$ of each path's top in~$T_p$ and reading
+the desired edge from~$P_p[i]$.
+
+\:For every son~$v$ of~$u$, process the edge $e=uv$:
+
+\::Construct the array of tops~$T_e$ for the edge~$e$: Start with~$T_p$, remove
+ the tops of the paths that do not contain~$e$ and add the vertex~$u$ itself
+ if there is a~query path which has~$u$ as its top and whose bottom lies somewhere
+ in the subtree rooted at~$v$.
+
+\::Prepare the array of the peaks~$P_e$: Start with~$P_p$, remove the entries
+ corresponding to the tops that are no longer active. If $u$ became an~active
+ top, append~$e$ to the array.
+
+\::Finish~$P_e$:
+ Since the paths leading to all active tops have been extended by the
+ edge~$e$, compare $w(e)$ with weights of the edges recorded in~$P_e$ and replace
+ those edges which are lighter by~$e$.
+ Since $P_p$ was sorted, we can use binary search
+ to locate the boundary between the lighter and heavier edges in~$P_e$.
+
+\::Recurse on~$v$: call $\<FindPeaks>(v,e,T_e,P_e)$.
+\endalgo
+
+\>As we need a~parent edge to start the recursion, we add an~imaginary parent
+edge~$p_0$ of the root vertex~$r$, for which no queries are defined. We can
+therefore start with $\<FindPeaks>(r,p_0,\emptyset,\emptyset)$.
+
+Let us account for the comparisons:
+
+\lemma\id{vercompares}%
+When the procedure \<FindPeaks> is called on the balanced problem, it
+performs $\O(n+q)$ comparisons, where $n$ is the size of the tree and
+$q$ is the number of query paths.
+
+\proof
+We will calculate the number of comparisons~$c_i$ performed when processing the edges
+going from the $(i+1)$-th to the $i$-th level of the tree.
+The levels are numbered from the bottom, so leaves are at level~0 and the root
+is at level $\ell\le \lceil \log_2 n\rceil$. There are $n_i\le n/2^i$ vertices
+at the $i$-th level, so we consider exactly $n_i$ edges. To avoid taking a~logarithm
+of zero, we define $\vert T_e\vert=1$ for $T_e=\emptyset$.
+\def\eqalign#1{\null\,\vcenter{\openup\jot
+ \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
+ \crcr#1\crcr}}\,}
+$$\vcenter{\openup\jot\halign{\strut\hfil $\displaystyle{#}$&$\displaystyle{{}#}$\hfil&\quad#\hfil\cr
+c_i &\le \sum_e \left( 1 + \log \vert T_e\vert \right)&(Total cost of the binary searches.)\cr
+ &\le n_i + \sum_e \log\vert T_e\vert&(We sum over $n_i$ edges.)\cr
+ &\le n_i + n_i \cdot {\sum_e \log\vert T_e\vert \over n_i}&(Consider the average of logarithms.) \cr
+ &\le n_i + n_i \cdot \log{\sum_e \vert T_e\vert \over n_i}&(Logarithm is concave.) \cr
+ &\le n_i + n_i \cdot \log{q+n\over n_i}&(Bound the number of tops by queries.) \cr
+ &= n_i \cdot \left( 1 + \log\left({q+n\over n}\cdot{n\over n_i}\right) \right)\cr
+ &= n_i + n_i\log{q+n\over n} + n_i\log{n\over n_i}.\cr
+}}$$
+Summing over all levels, we estimate the total number of comparisons as:
+$$
+c = \sum_i c_i = \left( \sum_i n_i \right) + \left( \sum_i n_i \log{q+n\over n}\right) + \left( \sum_i n_i \log{n\over n_i}\right).
+$$
+The first part is equal to~$n$, the second one to $n\log((q+n)/n)\le q+n$. For the third
+one, we would like to plug in the bound $n_i \le n/2^i$, but we unfortunately have one~$n_i$
+in the denominator. We save the situation by observing that the function $f(x)=x\log(n/x)$
+is decreasing\foot{We can easily check the derivative: $f(x)=(x\ln n-x\ln x)/\ln 2$, so $f'(x)\cdot \ln2 =
+\ln n - \ln x - 1$. We want $f'(x)<0$ and therefore $\ln x > \ln n - 1$, i.e., $x > n/e$.}
+for $x > n/e$, so for $i\ge 2$ it holds that:
+$$
+n_i\log{n\over n_i} \le {n\over 2^i}\cdot\log{n\over n/2^i} = {n\over 2^i} \cdot i.
+$$
+We can therefore rewrite the third part as:
+$$\eqalign{
+\sum_i n_i\log{n\over n_i} &\le n_0\log{n\over n_0} + n_1\log{n\over n_1} + n\cdot\sum_{i\ge 2}{i\over 2^i} \le\cr
+&\le n\log1 + n_1\cdot {n\over n_1} + n\cdot\O(1) = \O(n).\cr
+}$$
+Putting all three parts together, we conclude that:
+$$
+c \le n + (q+n) + \O(n) = \O(n+q). \qedmath
+$$
+
+\para
+When we combine this lemma with the above reduction from general trees to balanced trees, we get the following theorem:
+
+\thmn{Verification of the MST, Koml\'os \cite{komlos:verify}}\id{verify}%
+For every weighted graph~$G$ and its spanning tree~$T$, it is sufficient to
+perform $\O(m)$ comparisons of edge weights to determine whether~$T$ is minimum
+and to find all $T$-light edges in~$G$.
+
+\proof
+We first transform the problem to finding all peaks of a~set
+of query paths in~$T$ (these are exactly the paths covered by the edges
+of $G\setminus T$). We use the reduction from Lemma \ref{verbranch} to get
+an~equivalent problem with a~full branching tree and a~set of parent-descendant
+paths. The reduction costs $\O(m+n)$ comparisons.
+Then we run the \<FindPeaks> procedure (Algorithm \ref{findpeaks}) to find
+the tops of all query paths. According to Lemma \ref{vercompares}, this spends another $\O(m+n)$
+comparisons. Since we (as always) assume that~$G$ is connected, $\O(m+n)=\O(m)$.
+\qed
+
+\paran{Applications}%
+The problem of computing path maxima or minima in a~weighted tree has several other interesting
+applications. One of them is computing minimum cuts separating given pairs of vertices in a~given
+weighted undirected graph~$G$. We construct a~Gomory-Hu tree~$T$ for the graph as described in \cite{gomoryhu}
+(see also \cite{bhalgat:ght} for a~more efficient algorithm running in time
+$\widetilde\O(mn)$ for unit-cost graphs). The crucial property of this tree is that for every two
+vertices $u$, $v$ of the graph~$G$, the minimum-cost edge on $T[u,v]$ has the same cost
+as the minimum cut separating $u$ and~$v$ in~$G$. Since the construction of~$T$ generally
+takes $\Omega(n^2)$ time, we could of course invest this time in precomputing the minima for
+all pairs of vertices. This would however require quadratic space, so we can better use
+the method of this section which fits in $\O(n+q)$ space for $q$~queries.
+
+\paran{Dynamic verification}%
+A~dynamic version of the problem is also often considered. It calls for a~data structure
+representing a~weighted forest with operations for modifying the structure of the forest
+and querying minima or maxima on paths. Sleator and Tarjan have shown in \cite{sleator:trees}
+how to do this in $\O(\log n)$ time amortized per operation, which leads to
+an~implementation of the Dinic's maximum flow algorithm \cite{dinic:flow}
+in time $\O(mn\log n)$.
+
+%--------------------------------------------------------------------------------
+
+\section{Verification in linear time}\id{verifysect}%
+
+We have proven that $\O(m)$ edge weight comparisons suffice to verify minimality
+of a~given spanning tree. Now we will show an~algorithm for the RAM
+which finds the required comparisons in linear time. We will follow the idea
+of King from \cite{king:verifytwo}, but as we have the power of the RAM data structures
+from Section~\ref{bitsect} at our command, the low-level details will be easier,
+especially the construction of vertex and edge labels.
+
+\para
+First of all, let us make sure that the reduction to fully branching trees
+in the Balancing lemma (\ref{verbranch}) can be made run in linear time. As already noticed
+in the proof, the Bor\o{u}vka's algorithm runs in linear time. Constructing
+the Bor\o{u}vka tree in the process adds at most a~constant overhead to every
+step of the algorithm.