#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, dep[300010], f[300010], t[20][300010];
int dfn[300010], out[300010], dcnt;
vector<int> a[300010];
void init(int now, int fa) {
	dep[now] = dep[fa] + 1, f[now] = fa;
	t[0][dfn[now] = ++dcnt] = now;
	for (int v : a[now])
		if (v != fa) init(v, now);
	out[now] = dcnt;
}
int LCA(int x, int y) {
	if (x == y) return x;
	x = dfn[x], y = dfn[y];
	if (x > y) swap(x, y);
	int len = 31 ^ __builtin_clz(y - (x++));
	if (dep[t[len][x]] < dep[t[len][y - (1 << len) + 1]])
		return f[t[len][x]];
	return f[t[len][y - (1 << len) + 1]];
}
vector<pair<int, int>> e[300010];
int st[300010], top, sz[300010], vis[300010];
void getrt(int now, int fa, int nowsz, int rt) {
	sz[now] = 1;
	int mx = 0;
	for (auto t : e[now]) {
		if (t.first == fa || vis[t.first]) continue;
		getrt(t.first, now, nowsz, rt);
		sz[now] += sz[t.first], mx = max(mx, sz[t.first]);
	}
	if (mx * 2 <= nowsz && sz[now] * 2 > nowsz)
		rt = now;
}
vector<int> d;
int cnt[300010], mod;
void dfs(int now, int fa, int nowd) {
	if (now % mod == 0) d.push_back(nowd % mod);
	for (auto t : e[now]) {
		if (t.first == fa || vis[t.first]) continue;
		dfs(t.first, now, nowd + t.second);
	}
}
ll calc() {
	for (int x : d) cnt[x] = cnt[mod - x] = 0;
	for (int x : d) cnt[x]++;
	ll res = 0;
	for (int x : d) res += cnt[x ? mod - x : 0];
	return res;
}
ll solve(int rt, int nowsz) {
	getrt(rt, 0, nowsz, rt);
	vis[rt] = 1;
	vector<int> all;
	if (rt % mod == 0) all.push_back(0);
	ll res = 0;
	for (auto t : e[rt]) {
		if (vis[t.first]) continue;
		d.clear(), dfs(t.first, rt, t.second);
		res -= calc();
		for (int x : d) all.push_back(x);
	}
	d = all, res += calc();
	for (auto t : e[rt]) {
		int v = t.first;
		if (vis[v]) continue;
		res += solve(v, sz[v] < sz[rt] ? sz[v] : nowsz - sz[rt]);
	}
	return res;
}
ll g[300010];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y), a[y].push_back(x);
	}
	init(1, 0);
	for (int i = 1; i <= 19; i++) {
		int x = 1 << i;
		for (int j = 1; j + x - 1 <= n; j++) {
			if (dep[t[i - 1][j]] < dep[t[i - 1][j + x / 2]])
				t[i][j] = t[i - 1][j];
			else t[i][j] = t[i - 1][j + x / 2];
		}
	}
	for (int d = 1; d <= n; d++) {
		vector<int> p;
		for (int i = d; i <= n; i += d)
			p.push_back(i);
		sort(p.begin(), p.end(), [&](int x, int y) {
			return dfn[x] < dfn[y];
		});
		for (int i = 0; i < n / d - 1; i++)
			p.push_back(LCA(p[i], p[i + 1]));
		sort(p.begin(), p.end(), [&](int x, int y) {
			return dfn[x] < dfn[y];
		});
		p.resize(unique(p.begin(), p.end()) - p.begin());
		for (int x : p) e[x].clear(), vis[x] = 0;
		top = 0;
		for (int x : p) {
			while (top && (dfn[x] < dfn[st[top]] || dfn[x] > out[st[top]]))
				top--;
			if (top) {
				e[st[top]].push_back({x, dep[x] - dep[st[top]]});
				e[x].push_back({st[top], dep[x] - dep[st[top]]});
			}
			st[++top] = x;
		}
		mod = d, g[d] = solve(p[0], p.size());
	}
	ll ans = 0;
	for (int i = n; i >= 1; i--) {
		for (int j = i + i; j <= n; j += i)
			g[i] -= g[j];
		ans += g[i] * i;
	}
	cout << ans << endl;
	return 0;
}