CF1654D Potion Brewing Class

Alice 的魔药学教授给学生们布置了如下作业：用 $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 \ne j$，$1 \le x, y \le n$），表示原料 $i$ 和 $j$ 的比例应为 $x : y$。保证这些信息足以唯一确定原始的 $r_i$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出通过作业所需的最小原料总量，对 $998\,244\,353$ 取模后的结果。

在第一个测试用例中，最小的原料总量为 $69$。实际上，一种可行的魔药中各原料 $1, 2, 3, 4$ 的用量分别为 $16, 12, 9, 32$。该魔药是合法的，因为： - 原料 $3$ 和 $2$ 的比例为 $9 : 12 = 3 : 4$； - 原料 $1$ 和 $2$ 的比例为 $16 : 12 = 4 : 3$； - 原料 $1$ 和 $4$ 的比例为 $16 : 32 = 2 : 4$。 在第二个测试用例中，最小原料总量对应的各原料 $1, 2, 3, 4, 5, 6, 7, 8$ 的用量分别为 $60, 60, 24, 48, 32, 60, 45, 30$。 由 ChatGPT 4.1 翻译