P16222 [ECUSTPC 2025] Moonlight Over the Lotus Pond

Maddy encountered many blooming lotus flowers, but there was also something eerie among them... In this lotus pond, there is a tree with $n$ nodes, which is an undirected, acyclic, connected graph formed by $n-1$ edges. Each node $i$ ($1 \le i \le n$) has a weight $a_i$, and a $k$-pair $(x, y)$ on a tree is defined as follows: - $1 \le x < y \le n$, and $x$ and $y$ are integers representing nodes on the tree. - Let the weights of the nodes on the path from node $x$ to node $y$ form a multiset $S$. Note that $a_x$ and $a_y$ are also included on the path. - It is required that $\gcd S = \min S = k$, i.e. the greatest common divisor of the elements in $S$ equals the minimum value in $S$, and both are $k$. Maddy now randomly chooses two distinct nodes $(x, y)$ on the tree. If there exists a $k$ such that $(x, y)$ is a $k$-pair, then she will get $k$ lanterns. Please help Maddy compute the expected number of lanterns she gets. Output $ans$, which is the value of the expectation $q$ taken modulo $998244353$. See the Hint for the specific output requirement.

The first line contains an integer $T$ ($1 \le T \le 10^5$), denoting the number of test cases. For each test case, the first line contains an integer $n$ ($2 \le n \le 10^5$), denoting the number of vertices in the graph. Then follow $n-1$ lines, each containing two integers $u$ and $v$ ($1 \le u, v \le n, u \ne v$), indicating that there is an edge between $u$ and $v$ in the tree $T$. Then one line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), representing the weights of the nodes in the tree. It is guaranteed that $\sum n \le 3 \times 10^5$ over all testdata, and that the graph in each test case forms a tree.

For each test case, output one line with an integer $ans$, representing the expected number of lanterns Maddy gets modulo $998244353$.

### Explanation for Sample 1 The given tree has 6 nodes, with edges $1-2, 1-3, 2-4, 2-5, 3-6,$ The weights are $a_1 = 6, a_2 = 2, a_3 = 3, a_4 = 4, a_5 = 2, a_6 = 1.$ We enumerate all $\binom{6}{2} = 15$ pairs of nodes, and check whether $\gcd(S)$ equals $\min(S)$ for the multiset $S$ of weights on the path. For example: - Pair $(1,2)$: the path is $[6,2]$, $\min = 2$, $\gcd = 2$, so it belongs to $k = 2$. - Pair $(1,3)$: the path is $[6,3]$, $\min = 3$, $\gcd = 3$, so it belongs to $k = 3$. - Pair $(1,6)$: the path is $[6,3,1]$, $\min = 1$, $\gcd = 1$, so it belongs to $k = 1$. - Pair $(3,4)$: the path is $[3,6,2,4]$, $\min = 2$, $\gcd = 1$, which does not satisfy the condition. The final counts are: $k = 1$: 5 pairs $(1,6), (2,6), (3,6), (4,6), (5,6)$, $k = 2$: 6 pairs $(1,2), (1,4), (1,5), (2,4), (2,5), (4,5)$, $k = 3$: 1 pair $(1,3)$, $k = 4,5,6$: 0 pairs. Thus the expected number of lanterns is $$ \frac{5 \times 1 + 6 \times 2 + 1 \times 3 + 0 \times 4 + 0 \times 5 + 0 \times 6}{15} = \frac{4}{3}. $$ Taking it modulo gives the answer $332748119$. ### Hint It can be proven that the answer of this problem is a rational number. Let it be $\frac{p}{q}$ where $p$ and $q$ are coprime. The number you output, $ans$, must satisfy $0 \le ans < 998244353$ and $$ q \cdot ans \equiv p \pmod{998244353}. $$ It can be proven that such an $ans$ must exist under the meaning of this problem. Translated by ChatGPT 5