A14902. Potion Brewing Class
编程题
普及/提高-
知识点
题目描述
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$ .
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$ .
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$ .
输入输出样例
输入 #1
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
输出 #1
69 359 573672453
说明/提示
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$ .
- 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$ .