Блог пользователя Y25t

Автор Y25t, история, 3 года назад, По-английски

In a rooted tree $$$T$$$, let $$$dep_u$$$ be the distance from $$$u$$$ to the root, $$$dis_u$$$ be the distance from $$$u$$$ to the deepest leaf in $$$u$$$'s subtree.

Let $$$f(T)=\sum_{u\in T} dep_u\times dis_u$$$.

Someone says that the expected number of $$$f(T)$$$ is $$$O(n\sqrt{n})$$$ when $$$T$$$ is uniformly randomly chosen from all $$$n$$$ vertices rooted trees.

How to prove it?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится