D. Potion Brewing Class
dfs and similar; math; number theory; trees
Alice's potion making professor gave the following assignment to his students: brew a potion using \(n\) ingredients, such that the proportion of ingredient \(i\) in the final potion is \(r_i > 0\) (and \(r_1 + r_2 + \cdots + r_n = 1\)).He forgot the recipe, and now all he remembers is a set of \(n-1\) facts of the form, ""ingredients \(i\) and \(j\) should have a ratio of \(x\) to \(y\)"" (i.e., if \(a_i\) and \(a_j\) are the amounts of ingredient \(i\) and \(j\) in the potion respectively, then it must hold \(a_i/a_j = x/y\)), where \(x\) and \(y\) are positive integers. However, it is guaranteed that the set of facts he remembers is sufficient to uniquely determine the original values \(r_i\).He decided that he will allow the students to pass the class as long as they submit a potion which satisfies all of the \(n-1\) requirements (there may be many such satisfactory potions), and contains a positive integer amount of each ingredient.Find the minimum total amount of ingredients needed to make a potion which passes the class. As the result can be very large, you should print the answer modulo \(998\,244\,353\).
The first line contains a single integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases.The first line of each test case contains a single integer \(n\) (\(2 \le n \le 2 \cdot 10^5\)).Each of the next \(n-1\) lines contains four integers \(i, j, x, y\) (\(1 \le i, j \le n\), \(i\not=j\), \(1\le x, y \le n\)) — ingredients \(i\) and \(j\) should have a ratio of \(x\) to \(y\). It is guaranteed that the set of facts is sufficient to uniquely determine the original values \(r_i\).It is also guaranteed that the sum of \(n\) for all test cases does not exceed \(2 \cdot 10^5\).
For each test case, print the minimum total amount of ingredients needed to make a potion which passes the class, modulo \(998\,244\,353\).
In the first test case, the minimum total amount of ingredients is \(69\). In fact, the amounts of ingredients \(1, 2, 3, 4\) of a valid potion are \(16, 12, 9, 32\), respectively. The potion is valid because Ingredients \(3\) and \(2\) have a ratio of \(9 : 12 = 3 : 4\); Ingredients \(1\) and \(2\) have a ratio of \(16 : 12 = 4 : 3\); Ingredients \(1\) and \(4\) have a ratio of \(16 : 32 = 2 : 4\). In the second test case, the amounts of ingredients \(1, 2, 3, 4, 5, 6, 7, 8\) in the potion that minimizes the total amount of ingredients are \(60, 60, 24, 48, 32, 60, 45, 30\).