Induced subgraph problem in trees
First, notice that, in trees, the path between any pair of vertices is unique. This means that the sub-forest you want is the union of these paths.

To find them, do the following:


Pick any vertex to be the root of the tree.  Orient all the edges towards the root and store the distance from the root at each vertex.
To process a pair $(u_i,v_i)$ start a walk towards the root from the element of the pair that is farther from it.  (Break ties arbitrarily.)  As you walk, mark edges.  If the walk reaches the other item of the pair, stop.  Otherwise do the same thing from the other item of the pair.
Once all the pairs are processed, output the marked edges.


This is correct, since either $u_i$ and $v_i$ are on a path towards the root or the path between them goes through the root.  It's also too slow, since we may end up walking over the same edge multiple times, so we end up with $O(n^2)$ running time.

To speed this up, we can just use a union-find data structure.  The edges are partitioned into classes labeled by the lowest vertex they can reach by a path of marked edges.  Now when we walk, we can skip upwards every time we encounter a marked edge, at the same time merging any classes that we need to.

With this scheme, marked edges are encountered at most twice, so get a total of $O(\alpha(n)n)$, where $\alpha$ is the inverse Ackermann function.