Ягнёнок на тропах Суусамыра
На пастбищах Суусамыра 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.
Комментарии