#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr LL mod = 998244353;
constexpr int maxn = 200000 + 1;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    vector<vector<int>> G(N + 1);
    for(int i = 1, u, v; i < N; i += 1){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> size(N + 1), cut(N + 1), msize(N + 1);
    int center = 0;
    function<void(int, int, int)> fc = [&](int u, int par, int tot){
        size[u] = 1;
        msize[u] = 0;
        for(int v : G[u]) if(v != par and not cut[v]){
            fc(v, u, tot);
            size[u] += size[v];
            msize[u] = max(msize[u], size[v]);
        }
        msize[u] = max(msize[u], tot - size[u]);
        if(msize[u] < msize[center]) center = u;
    };
    msize[center] = INT_MAX;
    fc(1, 0, N);
    vector<vector<pair<int, int>>> vvn(N + 1);
    function<void(int, int, int, int)> DFS = [&](int u, int par, int dep, int root){
        vvn[u].push_back({root, dep});
        for(int v : G[u]) if(v != par and not cut[v]) DFS(v, u, dep + 1, root);
    };
    function <void(int, int)> solve = [&](int u, int tot){
        vvn[u].push_back({u, 0});
        for(int v : G[u]) if(not cut[v])
            DFS(v, u, 1, u);
        cut[u] = 1;
        for(int v : G[u]) if(not cut[v]){
            center = 0;
            if(size[v] > size[u]) size[v] = tot - size[u];
            fc(v, 0, size[v]);
            solve(center, size[v]);
        }
    };
    solve(center, N);
    vector<vector<int>> par(N + 1, vector<int>(19));
    vector<int> dep(N + 1), p(N + 1);
    function<void(int)> dfs = [&](int u){
        for(int i = 1; i < 20; i += 1)
            par[u][i] = par[par[u][i - 1]][i - 1];
        for(int v : G[u]) if(par[u][0] != v){
            par[v][0] = u;
            dep[v] = dep[u] + 1;
            dfs(v);
        }
    };
    auto ga = [&](int u, int k){
        for(int i = 19; i >= 0; i -= 1)
            if(k >= (1 << i)){
                k -= 1 << i;
                u = par[u][i];
            }
        return u;
    };
    dfs(1);
    for(int i = 1; i <= N; i += 1) p[i] = i;
    sort(p.begin() + 1, p.end(), [&](const int& x, const int& y){
        return dep[x] > dep[y];
    });
    int L = 1, R = N - 1;
    while(L < R){
        int M = (L + R) >> 1, k = 0;
        //cout << L << " " << R << " " << M << endl;
        vector<int> d(N + 1, -1E9);
        for(int i = 1; i <= N; i += 1){
            int u = p[i], vis = 0;
            for(auto [v, dr] : vvn[u])
                if(d[v] >= dr) vis = 1;
            if(vis) continue;
            k += 1;
            int x = ga(u, M);
            if(x == 0) break;
            for(auto [v, dr] : vvn[x]) if(M >= dr)
                d[v] = max(d[v], M - dr);
        }
        //cout << k << endl;
        if(k > K) L = M + 1;
        else R = M;
    }
    cout << L << "\n";
    return 0;
}
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
#define forn(a, e) for (i64 a = 0; a < (i64)(e); a++)
#define forr(a, s, e) for (i64 a = s; a < (i64)(e); a++)
#define fore(e, a) for (auto& e : a)

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; fore(e, a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; fore(e, a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; fore(r, a) { fore(e, r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; fore(e, a) { cerr << e.field << " ";} cerr << "\n"; }
#define logvff(a, f1, f2) {cerr << #a".{"#f1 << ", "#f2 << "} = \n"; fore(e, a) { cerr << "(" << e.f1 <<", " << e.f2 << ") ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logvff(a, f1, f2)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

using iip = pair<int, int>;
using llp = pair<i64, i64>;
using ivec = vector<int>;
using llvec = vector<i64>;
using svec = vector<string>;
template<typename T> using vec = vector<T>;

template<typename T, typename Dim>
auto make_vec(T value, Dim dim) { return vector<T>(dim, value); }
template<typename T, typename Dim1, typename... Dim>
auto make_vec(T value, Dim1 dim1, Dim... dims) { return make_vec(make_vec(value, dims...), dim1); }

template<typename T>
bool uax(T& v, const T& newv) { if (v < newv) { v = newv; return true; } else return false; }
template<typename T>
bool uin(T& v, const T& newv) { if (v > newv) { v = newv; return true; } else return false; }

template<typename T>
istream& operator>>(istream& is, vector<T>& c) { for (auto& e : c) is >> e; return is; }
template<typename T, size_t N>
istream& operator>>(istream& is, array<T, N>& c) { for (auto& e : c) is >> e; return is; }

template<typename ...T>
istream& read(T&... args) { return (cin >> ... >> args); }

static mt19937 rande(123123);
template<typename T>
T rand_int(T from, T to) { uniform_int_distribution<T> distr(from, to); return distr(rande); }

// const i64 INF = 2e18;
const int INF = 2e9;
const __int128_t M = 1000000;
const int MXB = 20;
using bin = bitset<MXB + 1>;
const double EPS = 1e-8;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    rande.seed(chrono::steady_clock::now().time_since_epoch().count());

    string s;
    while (read(s)) {
        int n = s.size();
        auto cc = make_vec(0, n + 1, 26);

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                cc[i][j] = cc[i + 1][j];
            }

            cc[i][s[i] - 'a']++;
        }

        i64 ans = 0;
        int lp = n;
        char lc = 0;
        for (int i = n - 3; i >= 0; i--) {
            if (s[i] == s[i + 1] && s[i + 1] != s[i + 2]) {

                int cl = cc[i + 2][s[i] - 'a'] - cc[lp][s[i] - 'a'];
                ans += max(0, lp - (i + 2) - cl);

                if (s[i] != lc) {
                    ans += n - lp;
                }

                lp = i;
                lc = s[i];
            }
        }

        cout << ans << endl;
    }
}