Профессор зельеварения дал следующее задание студентам: сварить зелье, используя $$$n$$$ ингредиентов, так, чтобы доля ингредиента $$$i$$$ в зелье равнялась бы $$$r_i > 0$$$ (при этом $$$r_1 + r_2 + \cdots + r_n = 1$$$).
К сожалению, он забыл рецепт зелья, и теперь только помнит набор из $$$n-1$$$ факта вида «ингредиенты $$$i$$$ и $$$j$$$ должны входить в отношении $$$x$$$ к $$$y$$$» (т. е. если за $$$a_i$$$ и $$$a_j$$$ обозначить объемы ингредиентов $$$i$$$ и $$$j$$$ в зелье соответственно, то должно выполняться $$$a_i/a_j = x/y$$$), где $$$x$$$ и $$$y$$$ — положительные целые числа. Гарантируется, что данный набор фактов достаточен, чтобы однозначно определить доли ингредиентов в рецепте $$$r_i$$$.
Профессор решил, что он зачтет задание студентам, если они приготовят зелье, удовлетворяющее всем $$$n-1$$$ ограничениям (таких зелий может быть много), и при этом объем каждого ингредиента строго положительный и выражается целым числом.
Найдите минимальный суммарный объем всех ингредиентов, необходимый, чтобы сварить подходящее зелье. Так как ответ может быть большим, выведите его остаток от деления на $$$998\,244\,353$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).
Каждая из следующих $$$n-1$$$ строк содержит четыре целых числа $$$i, j, x, y$$$ ($$$1 \le i, j \le n$$$, $$$i\not=j$$$, $$$1\le x, y \le n$$$), обозначающие, что ингредиенты $$$i$$$ и $$$j$$$ должны иметь отношение объемов $$$x$$$ к $$$y$$$. Гарантируется, что этот набор фактов достаточен, чтобы однозначно определить исходные доли $$$r_i$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите минимальный суммарный объем ингредиентов, необходимый, чтобы сделать зелье, подходящее под требования профессора, по модулю $$$998\,244\,353$$$.
3 4 3 2 3 4 1 2 4 3 1 4 2 4 8 5 4 2 3 6 4 5 4 1 3 5 2 6 8 2 1 3 5 3 4 3 2 2 5 6 7 4 3 17 8 7 4 16 9 17 4 5 5 14 13 12 11 1 17 14 6 13 8 9 2 11 3 11 4 17 7 2 17 16 8 6 15 5 1 14 16 7 1 10 12 17 13 10 11 16 7 2 10 11 6 4 13 17 14 6 3 11 15 8 15 6 12 8
69 359 573672453
В первом наборе входных данных минимальный объем ингредиентов равен $$$69$$$. Действительно, объемы ингредиентов $$$1, 2, 3, 4$$$ должны быть равны $$$16, 12, 9, 32$$$, соответственно. Это зелье подходит, потому что
Во втором наборе объемы ингредиентов $$$1, 2, 3, 4, 5, 6, 7, 8$$$ в зелье минимального суммарного объема равны $$$60, 60, 24, 48, 32, 60, 45, 30$$$.
Название |
---|