Подвесим дерево за любую вершину.
Тогда количество подмножеств, в которых эта вершина не присутствует, это $$$\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})$$$.