solve2 for E1; solve3 for E2

// Problem: E1. Maple and Tree Beauty (Easy Version)
// Contest: Codeforces - Codeforces Round 1048 (Div. 2)
// URL: https://codeforces.com/contest/2139/problem/E1
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

namespace rngs = std::ranges;
using ll = long long;
using a2l = array<ll, 2>;
using vl = vector<ll>;

void solve2()
{
    ll n, k;
    cin >> n >> k;
    vector<vl> g(n + 1);
    for (ll i = 2, p; i <= n; ++i) {
        cin >> p;
        g[p].push_back(i);
    }
    vl dcnt(n);
    ll min_leaf = LLONG_MAX / 2;
    auto dfs = [&](auto &&self, ll u, ll depth) -> void {
        dcnt[depth] += 1;
        bool is_leaf = true;
        for (auto v : g[u]) {
            self(self, v, depth + 1);
            is_leaf = false;
        }
        if (is_leaf)
            min_leaf = min(min_leaf, depth);
    };
    dfs(dfs, 1, 0);

    ll d1 = min(k, n - k), d2 = max(k, n - k);
    vl dp(d1 + 1);
    dp[0] = d2;

    ll ans = 0;
    for (ll i = 0; i <= min_leaf; ++i) {
        ll v = dcnt[i];
        vl ndp(dp);
        for (auto &x : ndp)
            x -= v;
        for (ll j = v; j <= d1; ++j)
            ndp[j] = max(ndp[j], dp[j - v]);

        swap(dp, ndp);
        for (auto &x : dp)
            if (x >= 0)
                ans = max(ans, i + 1);
    }
    cout << ans << '\n';
}

constexpr ll maxn = 2e5 + 3;
template <ll dlen = 1> ll calc(ll d1, ll d2, const vl &dcnt, ll min_leaf)
{
    if (dlen <= d1) {
        return calc<min(2 * dlen, maxn)>(d1, d2, dcnt, min_leaf);
    }

    bitset<dlen> bs;
    bs[0] = true;
    ll ans = 0;
    map<ll, ll> cnt;
    for (ll i = 0; i <= min_leaf; ++i)
        cnt[dcnt[i]] += 1;

    vl opt;
    for (auto [k, v] : cnt) {
        for (ll i = 1; i <= v; i <<= 1) {
            opt.push_back(k * i);
            v -= i;
        }
        if (v)
            opt.push_back(k * v);
    }

    ll sum = 0;
    for (auto v : opt) {
        sum += v;
        bs = bs | (bs << v);
    }

    if (sum <= d1 || sum <= d2)
        return min_leaf + 1;
    for (ll i = min(max(0ll, sum - d2), d1); i <= d1; ++i)
        if (bs[i])
            return min_leaf + 1;

    return min_leaf;
};
void solve3()
{
    ll n, k;
    cin >> n >> k;
    vector<vl> g(n + 1);
    for (ll i = 2, p; i <= n; ++i) {
        cin >> p;
        g[p].push_back(i);
    }
    vl dcnt(n);
    ll min_leaf = LLONG_MAX / 2;
    auto dfs = [&](auto &&self, ll u, ll depth) -> void {
        dcnt[depth] += 1;
        bool is_leaf = true;
        for (auto v : g[u]) {
            self(self, v, depth + 1);
            is_leaf = false;
        }
        if (is_leaf)
            min_leaf = min(min_leaf, depth);
    };
    dfs(dfs, 1, 0);

    ll ans = calc(min(k, n - k), max(k, n - k), dcnt, min_leaf);
    cout << ans << '\n';
}

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<vl> g(n + 1);
    for (ll i = 2, p; i <= n; ++i) {
        cin >> p;
        g[p].push_back(i);
    }
    vl dcnt(n);
    ll min_leaf = LLONG_MAX / 2;
    auto dfs = [&](auto &&self, ll u, ll depth) -> void {
        dcnt[depth] += 1;
        bool is_leaf = true;
        for (auto v : g[u]) {
            self(self, v, depth + 1);
            is_leaf = false;
        }
        if (is_leaf)
            min_leaf = min(min_leaf, depth);
    };
    dfs(dfs, 1, 0);
    ll ans = 0;

    vector<vl> dp(n - k + 1, vl(k + 1, LLONG_MIN / 2));
    dp[0][0] = 0;
    auto search = [&](auto &&self, ll sid, ll r1, ll r2) -> ll {
        if (sid > min_leaf || dcnt[sid] == 0)
            return 0;
        if (r1 < dcnt[sid] && r2 < dcnt[sid])
            return 0;
        if (dp[r1][r2] != LLONG_MIN / 2)
            return dp[r1][r2];
        ll res = 0;
        if (r1 >= dcnt[sid]) {
            ll branch = self(self, sid + 1, r1 - dcnt[sid], r2) + 1;
            res = max(res, branch);
        }
        if (r2 >= dcnt[sid]) {
            ll branch = self(self, sid + 1, r1, r2 - dcnt[sid]) + 1;
            res = max(res, branch);
        }
        ans = max(ans, res);
        return dp[r1][r2] = res;
    };

    search(search, 0, n - k, k);

    cout << ans << '\n';
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll t = 1;
    cin >> t;
    while (t--)
        solve3();

    return 0;
};