This note resolves the part of the 2nd lecture on link
cut trees that was left unresolved during the lecture.
I think this is the cleanest way to finish this up.

First of all, we'll use the standard potential
function for splay trees.

            Phi(T) = Sum r(x)
                    x in T

Recall the Access Lemma:  The amortized number of
rotations done by a sequence of splays is at most
3(r(root) - r(x)) + 1

Remember that the +1 was for the last rotation, which
might happen if the splay ends in a zig step.  So let's
separate the rotations that occur in splaying into
two types "top rotations" and "non-top rotations".  The
top ones are those which occur in the zig step.

So a slightly refined version of the Access Lemma
says this:  In a sequence of splays, here are
amortized bounds:

  number of non-top rotations <= 3(r(root)-r(x))
  number of top rotations <= 1

So consider the cost of a splay(x) in the virtual tree.
We'll let this cost be the number of edges on the path
from x to the root of the virtual tree containing x.
This is also precisely equal to the number of rotations
done in the 3-part splay(x) operation.  Phase 2 (the
splices) does zero rotations so its cost is zero.
Let's consider the two types of rotations separately.
In phase 1, the telescoping argument explained in
lecture shows that the number of non-top rotations
is at most 3log(n).  In phase 3 the number of non-top
rotations is also at most 3log(n).

What about the top rotations?  In phase 1 we do at most
k+1 of these (k is the number of dashed edges on the
path).  In phase 3 we do at most 1 of these.  So we
need to bound Sum(k+2) where the sum is taken over all
splay operations in the virtual tree.

Note that in phase 3 we also do k-1 non-top rotations.
Therefore, the total number of non-top rotations done 
is an upper bound on Sum(k-1) over all the splays.
(where the sum is taken over all splays in the virtual
tree.) Therefore

     Sum(k-1) <= Sum(6log(n))
 ==>
     Sum(k+2) <= Sum(6log(n)+3)
 ==>
     amortized number of top rotations <= 6log(n)+3

So the amortized number of rotations total is at most
12 log(n) + 3.   Q.E.D.

---Danny Sleator     October 21, 2009