TOURIST - LCA (rmq O(1))

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxN = 110;
const int INF = 1e9 + 7;

int n, lg;
vector<int> graph[maxN];

namespace LCA {
#define MASK(i) (1LL << (i))
#define MIN_HIGH(x, y) (high[x] < high[y] ? (x) : (y))

int high[maxN], pos[maxN];
int nodes[maxN], cnt;

int rmq[maxN][25];

void DFS(int u, int p) {
    nodes[++cnt] = u;
    pos[u] = cnt;
    for (int v : graph[u]) {
        if (v == p) continue;

        high[v] = high[u] + 1;
        DFS(v, u);
        nodes[++cnt] = u;
    }
}

void build_LCA() {
    DFS(1, 1);
    for (int i = 1; i <= cnt; i++)
        rmq[i][0] = nodes[i];

    for (int j = 1; j <= 25; j++)
        for (int i = 1; i <= cnt - MASK(j) + 1; i++)
            rmq[i][j] = MIN_HIGH(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]);
}

int find_LCA(int u, int v) {
    int l = pos[u];
    int r = pos[v];
    if (l > r) swap(l, r);

    int k = 31 - __builtin_clz(r - l + 1);
    return MIN_HIGH(rmq[l][k], rmq[r - MASK(k) + 1][k]);
}
} // namespace LCA

int main() {
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#else
    freopen("TOURIST - LCA.inp", "r", stdin);
    freopen("TOURIST - LCA.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n-1; ++i) {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    LCA::build_LCA();

    ll ans = 0;
    for (int u = 1; u <= n; ++u) {
        for (int i = 2; i <= n/u; ++i) {
            int v = u * i;
            int t = LCA::find_LCA(u, v);

            int x1 = (LCA::high[u] - LCA::high[t]);
            int x2 = (LCA::high[v] - LCA::high[t]);

            ans += x1 + x2 + 1;
        }
    }
    cout << ans << '\n';

    return 0;
}