← 返回题目列表

Codeforces · 1916/G

G. 来自 Chelsu 的优化

中文机器翻译题面 查看原题

给你一棵有 $$$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)$$$ 的最大值。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$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$$$。

输出

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

示例

输入 #1

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

输出 #1

1000000000000
12
18
24