Estaba resolviendo este problema. En resumen, el problema es el siguiente:
Se le da un árbol rooteado. En cada paso eliges un nodo al azar y eliminas el subárbol rooteado por ese nodo y el propio nodo, hasta que se hayan eliminado todos (es decir, se haya elegido la raíz). Encuentre el número esperado de pasos en este proceso.
En el editorial está escrito que la eliminación directa del nodo $i$ (ese nodo $i$ ha sido elegido, no sus antecesores) es $\frac{1}{\text{Depth[i]}}$ . Intuitivamente me doy cuenta de que si algún nodo tiene más ancestros entonces la probabilidad de que su ancestro sea elegido (por lo tanto el nodo $i$ se eliminó) es más que el propio nodo. Por lo tanto, un mayor número de ancestros implica una menor probabilidad de eliminación directa. Pero cómo la probabilidad es exactamente igual a $\frac{1}{\text{Depth[i]}}$ que no podía entender.
Por favor, ayuda.
