← 返回题目列表

Codeforces · 1654/D

D. 药水酿造课程

中文机器翻译题面 查看原题

爱丽丝的药水制作教授给他的学生布置了以下作业:使用$$$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$$$ 为模。

示例

输入 #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

注意

在第一个测试用例中,成分的最小总量为 $$$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$$$。