Случайное дерево

Подвесим дерево за любую вершину.

Тогда количество подмножеств, в которых эта вершина не присутствует, это $$$\sum{(2^{sz_{to}} - 1)}$$$ (по всем детям $$$to$$$ вершины $$$v$$$) + $$$2^{n-sz_{v}}$$$, где $$$sz_v$$$ — размер поддерева $$$v$$$.

Таким образом, ответ на задачу это $$$2^n \cdot n - \sum{(2^{sz_{v}} - 1)} + \sum{2^{n-sz_{v}}} - 2^n + 1$$$.

Также можно показать, что математическое ожидание глубины вершины в случайном дереве это $$$\log{n}$$$.

Тогда можно подняться за $$$O(depth)$$$ и пересчитать размеры поддеревьев, и вместе с ними обновить ответ.

Итоговое время работы: $$$\mathcal{O}(n \log{n})$$$.