Дано дерево с \(n\) вершинами.
В некоторую вершину \(v \ne 1\) посадят робота. Пусть у вас изначально есть \(p\) монет. Рассмотрим следующий процесс, где в \(i\)-й шаг (начиная с \(i = 1\)):
- Если \(i\) нечётное, робот передвинется в соседнюю вершину в сторону вершины \(1\);
- Иначе, \(i\) чётное. Можно либо заплатить одну монету (если остались), после чего робот передвинется в соседнюю вершину в сторону вершины \(1\), либо ничего не платить, после чего робот передвинется в равновероятно выбранную соседнюю вершину.
Процесс останавливается, как только робот попадает в вершину \(1\). Определим \(f(v, p)\) как минимально возможное математическое ожидание количества шагов процесса выше (количество использованных монет минимизировать не надо).
Необходимо ответить на \(q\) запросов, в \(i\)-м из которых надо найти значение \(f(v_i, p_i)\) по модулю\(^{\text{∗}}\) \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел: значения \(f(v_i, p_i)\) по модулю \(998\,244\,353\).
Формально, пусть \(M = 998\,244\,353\). Можно показать, что ответ может быть представлен в виде несократимой дроби \(\frac{p}{q}\), где \(p\) и \(q\) — целые числа, и \(q \not \equiv 0 \pmod{M}\). Выведите целое число, равное \(p \cdot q^{-1} \bmod M\). Другими словами, выведите такое целое число \(x\), что \(0 \le x < M\) и \(x \cdot q \equiv p \pmod{M}\).
Примечание
Дерево из первого набора показано ниже:
Для первого запроса значение математического ожидания равно \(1\), так как робот начинает движение с вершины \(2\) и первым ходом попадает в вершину \(1\) и завершает перемещение.
Посчитаем значение математического ожидания для второго запроса (\(x\) это количество шагов в процессе):
- \(P(x < 2) = 0\), расстояние до вершины \(1\) равно \(2\) и робот не может дойти до него за меньшее количество шагов.
- \(P(x = 2) = \frac{1}{3}\), так как есть только одна последовательность шагов, приводящая к \(x = 2\). Это \(3 \rightarrow_{1} 2 \rightarrow_{0.33} 1\) с вероятностью \(1 \cdot \frac{1}{3}\).
- \(P(x \bmod 2 = 1) = 0\), так как робот может достичь вершину \(1\) сделав только чётное количество шагов.
- \(P(x = 4) = \frac{2}{9}\): возможные пути \(3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1\).
- \(P(x = 6) = \frac{4}{27}\): возможные пути \(3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1\).
- \(P(x = i \cdot 2) = \frac{2^{i - 1}}{3^i}\) в общем случае.
В результате \(f(v, p) = \sum\limits_{i=1}^{\infty}{i \cdot 2 \cdot \frac{2^{i - 1}}{3^i}} = 6\).
Дерево из второго набора показано ниже:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 4
1 2
2 3
2 4
2 0
3 0
4 0
3 1
12 10
1 2
2 3
2 4
1 5
5 6
6 7
6 8
6 9
8 10
10 11
10 12
6 0
9 0
10 0
11 0
3 1
7 1
10 1
12 1
12 2
11 12
|
1
6
6
2
4
9
8
15
2
3
6
9
5
5
|