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.

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.