Potion Brewing Class
Contest: Технокубок 2022 - Финал
Difficulty rating: 2100
Tags: implementation, 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$$$.

Input format:
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$$$.

Output format:
For each test case, print the minimum total amount of ingredients needed to make a potion which passes the class, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
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

Example output:
69
359
573672453

Editorial:
Hint 1
The n−1
facts make a tree. Hint 2
Assume that the amount of ingredient 1 is 1. For each i, the amount of ingredient i would be ci/di for some integer ci,di>0
. How to make an integer amount of each ingredient? Hint 3
The optimal amount of ingredient 1 is lcm(d1,d2,...,dn)
. Hint 4
Can you find the exponent of each prime p≤n in lcm(d1,d2,...,dn)
? Hint 5
If you visit the nodes in DFS order, each edge changes the exponent of O(logn) primes. At each moment, keep the factorization of ci/di of the current node, i.e., the exponents of each p≤n (they can be negative). For each p
, also keep the minimum exponent so far. Solution
Read the hints. The rest is just implementation.
Start a DFS from node 1 . Keep an array f such that fp is the exponent of p in the amount of ingredients of the current node. Keep also vi=ci/dimod998244353. At the beginning, the amount of ingredients (of node 1) is 1, so fp=0 for each p. Whenever you move from node i to node j, and ri/rj=x/y
,
for each pk
such that pk∣x and pk+1∤x, decrease fp by k ; for each pk such that pk∣y and pk+1∤y, increase fp by k
.
Notice that there exist O(logn) such values of pk for each edge, and you can find them by precalculating either the smallest prime factor (with the sieve of Eratosthenes) or the whole factorization of every integer in [2,n]
.
Let gp be the minimum value of fp during the DFS. Then, for every p, you have to multiply the amount of ingredients of node 1 by p−gp
.
The answer is the sum of vi , multiplied by the amount of ingredients of node 1
.
Complexity: O(nlogn)