CF1916G.Optimizations From Chelsu

You are given a tree with $n$ vertices, whose vertices are numbered from $1$ to $n$. Each edge is labeled with some integer $w_i$.

Define $len(u, v)$ as the number of edges in the simple path between vertices $u$ and $v$, and $gcd(u, v)$ as the Greatest Common Divisor of all numbers written on the edges of the simple path between vertices $u$ and $v$. For example, $len(u, u) = 0$ and $gcd(u, u) = 0$ for any $1 \leq u \leq n$.

You need to find the maximum value of $len(u, v) \cdot gcd(u, v)$ over all pairs of vertices in the tree.

给你一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。每条边都标有一个整数 $w_i$。

定义 $len(u, v)$ 为顶点 $u$ 与 $v$ 之间简单路径上的边数，$gcd(u, v)$ 为顶点 $u$ 与 $v$ 之间简单路径上所有边所标数字的最大公约数。例如，对任意 $1 \leq u \leq n$，均有 $len(u, u) = 0$ 且 $gcd(u, u) = 0$。

你需要在树中所有顶点对中，找出 $len(u, v) \cdot gcd(u, v)$ 的最大值。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. This is followed by their description.

The first line of each test case contains the number $n$ ($2 \leq n \leq 10^5$) — the number of vertices in the tree.

The next $n-1$ lines specify the edges in the format $u$, $v$, $w$ ($1 \leq u, v \leq n$, $1 \leq w \leq 10^{12}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示树中顶点的数量。

接下来的 $n-1$ 行以格式 $u$, $v$, $w$（$1 \leq u, v \leq n$，$1 \leq w \leq 10^{12}$）指定边。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, output a single number equal to the maximum value of $len(u, v) \cdot gcd(u, v)$ over all pairs of vertices in the tree.

对于每个测试用例，输出一个单一数字，该数字等于树中所有顶点对 $(u, v)$ 的 $len(u, v) \cdot gcd(u, v)$ 的最大值。