题目描述

在树城（Tree City）中，有 $n$ 个旅游景点，分别用 $1$ 到 $n$ 的编号唯一标识。这些景点由 $n-1$ 条双向道路连接，使得游客可以通过某条道路路径从任意一个景点到达另一个景点。

你是树城规划委员会的一名成员。经过对旅游业的大量研究，你的委员会发现了一个关于游客的非常有趣的事实：他们热爱数论！如果一个游客访问了编号为 $x$ 的景点，那么他会接着访问编号为 $y$ 的景点，当且仅当 $y > x$ 且 $y$ 是 $x$ 的倍数。此外，如果这两个景点没有直接道路相连，游客一定会经过连接 $x$ 和 $y$ 的路径上的所有景点，即使它们不是 $x$ 的倍数。被访问的景点数量包括 $x$ 和 $y$ 本身。我们将这个数量称为一条路径的长度。

考虑以下城市地图：

:::align{center} :::

以下是游客可能走的所有路径及其长度：

$1 \to 2 = 4$， $1 \to 3 = 3$， $1 \to 4 = 2$， $1 \to 5 = 2$， $1 \to 6 = 3$， $1 \to 7 = 4$，

$1 \to 8 = 3$， $1 \to 9 = 3$， $1 \to 10 = 2$， $2 \to 4 = 5$， $2 \to 6 = 6$， $2 \to 8 = 2$，

$2 \to 10 = 3$， $3 \to 6 = 3$， $3 \to 9 = 3$， $4 \to 8 = 4$， $5 \to 10 = 3$

为了利用游客行为的这一现象，委员会希望计算从景点 $x$ 到景点 $y$（其中 $y > x$ 且 $y$ 是 $x$ 的倍数）的路径上的景点数量。你需要计算所有这些路径的 长度之和。对于上面的例子，总和为：$4 + 3 + 2 + 2 + 3 + 4 + 3 + 3 + 2 + 5 + 6 + 2 + 3 + 3 + 3 + 4 + 3 = 55$。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含一个整数 $n$（$2 \leq n \leq 200{,}000$），表示景点的数量。接下来的 $n-1$ 行，每行包含一对空格分隔的整数 $i$ 和 $j$（$1 \leq i < j \leq n$），表示景点 $i$ 和景点 $j$ 之间有一条直接相连的道路。保证景点集是连通的。

输出格式

输出一个整数，表示所有满足 $y > x$ 且 $y$ 是 $x$ 的倍数的路径 $x \to y$ 的长度之和。

10
3 4
3 7
1 4
4 6
1 10
8 10
2 8
1 5
4 9

55

提示

翻译由 DeepSeek V3.2 完成