Телеграмм чат группы proalgorithms страница 4019

вот сама задача

23:48пожаловаться #1

В разборе говорится что
Set l=lca(a,b). Note that, until reaching l, every possible process still has the same probability of reaching b before a as it did when the first node was chosen. Therefore, we can assume that the process has reached l and calculate the probability from there

23:50пожаловаться #2

Но почему до достижения l вероятность достижения b раньше чем a была такой же как и первой итерации (то есть при выборе корня) ?

23:52пожаловаться #3

Потому что от корня до lca общая часть маршрута?

23:58пожаловаться #4

2021 July 05

Это в случае если l может двигаться верх по предкам ?

00:08пожаловаться #5

Или только по поддереву ?

00:09пожаловаться #6

М?

00:09пожаловаться #7

мм не то хотел сказать

допустим в таком тесте разве вероятность того что до b доберемся быстрее из l = 3 равна вероятности из корня ?

00:12пожаловаться #10

Да

00:13пожаловаться #11

Я имел ввиду при рассмотрении вероятности того что до b доберемся быстрее из l = 3 мы учитываем что мы можем сначала выбирать предков 3 а потом только вероятность что b встретится раньше a
Или же мы рассматриваем только поддерево вершины l ?

00:22пожаловаться #12

Если только поддерево то вероятность очевидно равна 1/2 ой

00:22пожаловаться #13

Чтобы добраться до b, надо добраться до l, чтобы добраться до a надо добраться до l

00:23пожаловаться #14