A16408 | 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.

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

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.