Профессор зельеварения дал следующее задание студентам: сварить зелье, используя $$$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$$$.
343 2 3 41 2 4 31 4 2 485 4 2 36 4 5 41 3 5 26 8 2 13 5 3 43 2 2 56 7 4 3178 7 4 169 17 4 55 14 13 1211 1 17 146 13 8 92 11 3 114 17 7 217 16 8 615 5 1 1416 7 1 1012 17 13 1011 16 7 210 11 6 413 17 14 63 11 15 815 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$$$.
Название |
---|