#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll adder = 0, ans = 1e18;
int n, K, sz[500005], used[500005], dis[500005], pl[500005], o[500005], bel[500005];
vector<int> g[500005];
void Getsz(int x, int fa) {
    sz[x] = 1;
    for (int y : g[x]) {
        if (y == fa || used[y]) continue;
        Getsz(y, x), sz[x] += sz[y];
    }
}
void Findct(int x, int fa, int all, int &mn, int &ct) {
    int mx = 0;
    for (int y : g[x]) {
        if (y == fa || used[y]) continue;
        Findct(y, x, all, mn, ct), mx = max(mx, sz[y]);
    }
    mx = max(mx, all - sz[x]);
    if (mx < mn) mn = mx, ct = x;
}
/*void dfz(int z) {
    int mn = 1e9, x = 0;
    Getsz(z, 0), Findct(z, 0, sz[z], mn, x), used[x] = 1;
    for (int y : g[x])
        if (!used[y]) dfz(y);
}*/
void dfs(int x, int fa, int b) {
    bel[x] = b;
    for (int y : g[x]) {
        if (y == fa) continue;
        dis[y] = dis[x] + 1;
        dfs(y, x, (b == 0 ? y : b));
    }
}
vector<int> indis[500005];
int P[500005], V[500005];
vector<int> Calc(int x) {
    if (!x) return {};
    dis[x] = 0;
    dfs(x, 0, 0);
    for (int i = 1; i <= n; i++) indis[dis[i]].push_back(i);
    int m = 0;
    for (int i = n; i >= 0; i--) {
        for (int j : indis[i]) pl[++m] = j;
        o[i] = P[i] = V[i] = 0, indis[i].clear();
    }
    // for (int i = 1; i <= n; i++) cout << dis[i] << ' ';
    // puts("");
    int cho = 0;
    ll sum = 1ll * (n - 1) * K;
    vector<int> might;
    for (int i = 1; i <= n; i++) {
        int y = pl[i];
        // cout << "Taking:" << y << ' ' << bel[y] << '\n';
        if (o[bel[y]] == K / 2) {
            if (!P[bel[y]]) P[bel[y]] = y, V[bel[y]] = dis[y];
            might.push_back(bel[y]);
            // cout << "Might:" << y << ' ' << bel[y] << '\n';
            continue;
        }
        o[bel[y]]++, sum -= 2 * dis[y], cho++;
        if (cho == K) break;
    }
    if (cho == K) ans = min(ans, adder + sum);
    sort(might.begin(), might.end());
    might.resize(unique(might.begin(), might.end()) - might.begin());
    return might;
}
int p1 = 2000000;
char buf[2000005];
int gc() {
    if (p1 >= 2000000) fread(buf, 1, 2000000, stdin), p1 = 0;
    return buf[p1++];
}
int rd() {
    int x = 0;
    char ch = gc();
    while (ch < '0' || ch > '9') ch = gc();
    while (ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = gc();
    return x;
}
vector<int> mymight;
void DFS2(int x, int fa) {
    if (g[x].size() != 2) {
        mymight.push_back(x);
        return;
    }
    for (int y : g[x]) {
        if (y == fa) continue;
        DFS2(y, x);
    }
}
int CC = 0;
void Solve(int z) {
    assert(z && !used[z]);
    int mn = 1e9, x = 0;
    Getsz(z, 0), Findct(z, 0, sz[z], mn, x), used[x] = 1;
    vector<int> to = Calc(x);
    // cerr << "Calcing:" << x << '\n';
    if (to.size() == 2) {
        if (g[x].size() != 2) {
            CC++;
            if (CC > 1) {
                while (to.size() > 1) to.pop_back();
            }
            for (auto i : to)
                if (!used[i]) Solve(i);
            return;
        }
        assert(g[x].size() == 2);
        Calc(P[to[0]]);
        Calc(P[to[1]]);
        DFS2(x, 0);
        for (auto i : mymight) Calc(i);
        return;
    }
    for (auto i : to) {
        if (!used[i]) Solve(i);
    }
}
int main() {
    n = rd(), K = rd();
    if (K == 1) return cout << n - 1, 0;
    for (int i = 1, x, y; i < n; i++) {
        x = rd(), y = rd();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    if (n <= 200) {
        for (int i = 1; i <= n; i++) Calc(i);
    } else Solve(1);
    cout << ans;
}