Problem Description

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.

Input Format

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.

Output Format

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

1
6
1 2
1 3
2 4
2 5
3 6
6 2 3 4 2 1

332748119

Hint

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