Ягнёнок на тропах Суусамыра


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На пастбищах Суусамыра n полян соединены n − 1 тропами так, что с любой поляны можно дойти до любой другой (поляны и тропы образуют дерево). Тропа i между полянами u[i] и v[i] имеет ширину w[i].

Отбившийся от отары ягнёнок бродит случайно: каждую минуту он уходит с текущей поляны по одной из выходящих из неё троп, причём по тропе ширины w он уходит с вероятностью, пропорциональной w (широкие тропы заметнее). Например, если с поляны выходят тропы ширины 1, 2 и 5, ягнёнок выберет их с вероятностями 1/8, 2/8 и 5/8.

Рисунок

Чабан Нурлан хочет знать, сколько ему ждать. Для каждого из q вопросов s t найдите математическое ожидание числа минут, за которое ягнёнок, начав на поляне s, впервые придёт на поляну t, где ждёт чабан.

Можно доказать, что ответ — рациональное число P / Q, где Q не делится на 998244353. Выведите P · Q⁻¹ по модулю 998244353.

Входные данные

В первой строке — два целых числа n и q (2 ≤ n ≤ 2 · 10⁵, 1 ≤ q ≤ 2 · 10⁵). В каждой из следующих n − 1 строк — три целых числа u v w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10⁹). В каждой из следующих q строк — два целых числа s t (1 ≤ s, t ≤ n).

Выходные данные

Для каждого вопроса выведите ожидаемое время по модулю 998244353.

Пример 1

Вход:

3 3
1 2 2
2 3 3
3 1
2 3
1 1

Выход:

5
332748120
0

Пояснение

Тропа 1 – 2 имеет ширину 2, тропа 2 – 3 — ширину 3. В первом вопросе ягнёнок за минуту доходит с поляны 3 до поляны 2, а оттуда уходит к поляне 1 с вероятностью 2/5 и обратно к поляне 3 с вероятностью 3/5; ожидание равно 5. Во втором вопросе ожидание равно 7/3, по модулю 998244353 это 332748120.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 8, ещё в 10 % тестов n, q ≤ 1000. В 10 % тестов все ширины равны 1.


Комментарии

Еще нет ни одного комментария.