problem_cezar

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

void Read(int &val) {
    val = 0; char c;
    do { c = getchar(); } while (!isdigit(c));
    while (isdigit(c)) { val = val * 10 + c - '0'; c = getchar(); }
}

const int N = 1e5 + 4;
int n, k;
vector<int> adj[N];

int numChild[N];

void DFS_CountChild(int dad, int u) {
    numChild[u] = 1;
    for (int v : adj[u]) if (v != dad) {
        DFS_CountChild(u, v);
        numChild[u] += numChild[v];
    }
}

struct Binary_Indexed_Tree {
    int node[N], cost[N];
    Binary_Indexed_Tree() {
        memset(node, 0, sizeof(node));
        memset(cost, 0, sizeof(cost));
    }

    void update(int pos, int val) {
        for (int i = pos; i < N; i += i & (-i)) node[i] += val;
        for (int i = pos; i < N; i += i & (-i)) cost[i] += val * pos;
    }
    int get(int pos) {
        int ans = 0;
        for (int i = pos; i > 0; i -= i & (-i)) ans += node[i];
        return ans;
    }
    int getCost(int pos) {
        int ans = 0;
        for (int i = pos; i > 0; i -= i & (-i)) ans += cost[i];
        return ans;
    }

} BIT;

int res = -1;

void process(int root) {
    int l = 1, r = n, pos = -1;
    while (l <= r) {
        int mid = (l + r) / 2, Count = BIT.get(n) - BIT.get(mid-1);
        if (Count >= k) { pos = mid; l = mid + 1; }
        else r = mid - 1;
    }

    assert(pos != -1);

    int tmp = BIT.get(n) - BIT.get(pos-1), remain = tmp - k;

    int tmpRes = pos * remain;
    tmpRes += BIT.getCost(pos-1);

    res = (res == -1) ? tmpRes : min(tmpRes, res);
}

void DFS_getRes(int dad, int u) {
    int prevDad = numChild[dad], prevU = numChild[u];
    if (u != 1) {
        numChild[dad] = n - numChild[u]; numChild[u] = n;
        BIT.update(prevDad, -1); BIT.update(prevU, -1);
        BIT.update(numChild[dad], 1); BIT.update(numChild[u], 1);
    }

    process(u);

    for (int v : adj[u]) if (v != dad) DFS_getRes(u, v);

    if (u != 1) {
        BIT.update(prevDad, 1); BIT.update(prevU, 1);
        BIT.update(numChild[dad], -1); BIT.update(numChild[u], -1);
        numChild[dad] = prevDad; numChild[u] = prevU;
    }
}

void sol() {
    DFS_CountChild(0, 1);
    for (int i = 1; i <= n; ++i) BIT.update(numChild[i], 1);

    DFS_getRes(0, 1);
    cout << res << '\n';
}

int main() {
    freopen("input.txt", "r", stdin);
    // freopen("cezar.inp", "r", stdin);
    // freopen("cezar.out", "w", stdout);

    Read(n); Read(k); ++k;
    int u, v;
    for (int i = 1; i < n; ++i) {
        Read(u); Read(v);
        adj[u].push_back(v); adj[v].push_back(u);
    }

    sol();

    return 0;
}