Optimizations From Chelsu
Contest: Good Bye 2023
Difficulty rating: 3500
Tags: divide and conquer, dp, number theory, trees

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
2
1 2 1000000000000
4
3 2 6
2 1 10
2 4 6
8
1 2 12
2 3 9
3 4 9
4 5 6
5 6 12
6 7 4
7 8 9
12
1 2 12
2 3 12
2 4 6
2 5 9
5 6 6
1 7 4
4 8 12
8 9 4
8 10 12
2 11 9
7 12 9

Example output:
1000000000000
12
18
24

Editorial:
Let's perform centroid decomposition and maintain the current found answer $$$ans$$$.
• On vertical paths, simply find the value of the function, and we will immediately update the answer,
• We need to learn how to update the answer for a pair of vertical paths, combining pairs $$$(g_1, len_1)$$$ and $$$(g_2, len_2)$$$. Let's make several observations.
• First. If $$$len_1 \ge len_2$$$, then $$$gcd(g_1, g_2) = g_1$$$. Because if $$$gcd(g_1, g_2)$$$ is not equal to $$$g_1$$$, then it is at least twice smaller than $$$g_1$$$.
• Second. From the first fact, we conclude that $$$g_2 = g_1 \cdot k$$$, so in order to make sense to update the answer, we need $$$g_1 \cdot (len_1 + len_2) > g_1 \cdot k \cdot len_2$$$ and from here we get that $$$len_1 > len_2 \cdot (k - 1)$$$. This means that $$$k \leq len_1$$$.
Let's do the following for a fixed centroid for each component:
• For each $$$g$$$, we will only keep the largest value of $$$len$$$,
• We will iterate over all such pairs and assume that we have fixed the pair $$$(g_1, len_1)$$$. For this, we will need to iterate over $$$1 \leq k \leq len_1$$$.
• Let's make the following optimization—if $$$g \cdot (len + d) \leq ans$$$, then there is no need to iterate over $$$k$$$, because we are guaranteed not to improve the answer. $$$d$$$—is the farthest distance from the centroid to any vertex.
We have an upper bound estimate for this solution $$$O(n \sqrt n \log n)$$$. Let's prove it.
For the pair $$$(len_i, gcd_i)$$$, we iterate over $$$k$$$ such that $$$1 \leq k \leq k_i$$$, where $$$k_i \leq len_i$$$ and we also cut off by the answer. Let's mark $$$k_i$$$ edges on the path from the centroid to the vertex from which this pair came. Let's look at some edge, suppose it is marked $$$c$$$ times, the distance from the centroid is $$$L$$$, and the $$$\gcd$$$ from the centroid, including this edge, is $$$g$$$. This means that we also marked it for some $$$gcd_i \leq \frac{g}{c}$$$. But we already knew that the answer was at least $$$g$$$, which means the size of the current graph is at least $$$L \cdot c$$$. It turns out that we could not have marked an edge at a distance $$$L$$$ from the centroid more than $$$\frac{n}{L}$$$ times.
We need to estimate in the tree the sum of $$$min(\frac{n}{depth[v]}, sz[v])$$$. It can be estimated as $$$n \sqrt n$$$. For $$$depth[v] \leq \sqrt n$$$, we have a total size of subtrees at the level of $$$n$$$, and then the value $$$\frac{n}{depth[v]} \leq \sqrt n$$$.