Для решения этой задачи, в первую очередь нам потребуется двоичное дерево. Естественно все его узлы хранить не удастся, соответственно прибегнем к помощи мапа/хешмапа или же пропишем свое дерево. Пускай мы для каждого поддерева храним текущее количество заряда в нем. Это несложно делается за O(H) проходом от заданной вершины к корню дерева. 

Как же найти теперь математическое ожидание?

Рассмотрим корень дерева. Пускай L - заряд левого поддерева + заряд корня, а R - заряд правого поддерева + заряд корня.  Если L == R то очевидно, что в любом случае потенциал дерева равен L (Вне зависимости от того куда путь распада пойдет). Не теряя общности допустим L < R. Тогда если путь распада пойдет в левое поддерево то потенциал дерева будет равен R. То есть с вероятностью 0.5 потенциал равен R. В другом же случае нам необходимо перейти в правое поддерево и помнить, что вероятность того что мы туда попадем уже сама по себе 0.5, а также что на предыдущем шагу мы уже оставили одну из компонент связности. Такое рассуждение необходимо применять рекурсивно, волоча за собой в рекурсии: максимальный заряд уже встретившейся компоненты связности и вероятность попадания в вершину.

В кратком псевдокоде это выглядит так:

f(curVertex, maxWas, curProbability)

{

if (curVertex is leaf) result += maxWas * curProbability;

if (L == R) result += curProbability * L;

if (L < R)

{

result += curProbability* 0.5 * R;

f(curVertex->right, max(maxWas, L), curProbability * 0.5);

}

if (L > R)

{

result += curProbability* 0.5 * L;

f(curVertex->left, max(maxWas, R), curProbability * 0.5);

}

}

Таким образом, вызовом функции

f(root, 0, 1.0) 

за время O(H) находится математическое ожидание потенциала. 

Итоговая сложность алгоритма O(HQ)