Random Entity Selection () Consider the task of selecting uniformly at random an entity in a tree rooted at s. Show how to perform this task, started by the root, with at most 2(n − 1) + dT (s, x) messages and 2r(s) + dT (s, x)

ideal time units. Prove both correctness and complexity.