Shtrix's blog

By Shtrix, 8 years ago, In Russian,
Для решения этой задачи, в первую очередь нам потребуется двоичное дерево. Естественно все его узлы хранить не удастся, соответственно прибегнем к помощи мапа/хешмапа или же пропишем свое дерево. Пускай мы для каждого поддерева храним текущее количество заряда в нем. Это несложно делается за 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)
 
 
 
 
  • Vote: I like it  
  • +23
  • Vote: I do not like it