题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6178

题意：给你一棵树，有$K$只猴子要爬到树上，每只猴子必须跟一个猴子紧密联系，即两个点要有一条边连接，现在我们希望砍掉尽可能多的边但仍使条件满足，输出最少剩下的边数。

思路：贪心的思想可以知道我们要尽可能多的连通块，所以我们希望把一棵树分成尽量多的两两相连的连通块，即最大二分匹配数，又因为最小点覆盖等于最大二分匹配数，所以我们用树形$DP$去求最小的点覆盖，然后与$K$进行比较，如果$K \leq ans*2$那么结果为$K/2$，否则为$K-ans*2+ans$，多出来的我们直接再把边加上去就好了，如果是奇数还要再加$1$，时间复杂度$O(n)$。

P.S：这题读入量太大，要用$fread$读入挂。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
#define FI(n) FastIO::read(n)
namespace FastIO{
    const int SIZE=1<<16;
    char buf[SIZE],obuf[SIZE],str[60];
    int bi=SIZE,bn=SIZE,opt;
    int read(char *s){
        while (bn){
            for (;bi<bn && buf[bi]<=' ';bi++);
            if (bi<bn) break;
            bn=fread(buf,1,SIZE,stdin);
            bi=0;
        }
        int sn=0;
        while (bn){
            for (;bi<bn && buf[bi]>' '; bi++) s[sn++]=buf[bi];
            if (bi<bn) break;
            bn=fread(buf,1,SIZE,stdin);
            bi=0;
        }
        s[sn]=0;
        return sn;
    }
    bool read(int& x){
        int n=read(str),bf;

        if (!n)return 0;
        int i=0;if(str[i]=='-') bf=-1,i++;else bf=1;
        for (x=0;i<n;i++) x=x*10+str[i]-'0';
        if (bf<0) x=-x;
        return 1;
    }
};
int T,n,k,dp[maxn][2];
vector<int>G[maxn];
void dfs(int u,int f){
    dp[u][0]=1;//选这个点
    dp[u][1]=0;//不选这个点
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
        dp[u][0]+=min(dp[v][0],dp[v][1]);//选了这个点就要与下面所有的连边，还要尽可能小
        dp[u][1]+=dp[v][0];
    }
}
int main(){
    for (FI(T);T--;){
        FI(n),FI(k);
        for (int i=1;i<=n;i++) G[i].clear();
        for (int i=2;i<=n;i++){
            int x;FI(x);
            G[i].push_back(x);
            G[x].push_back(i);
        }
        dfs(1,-1);
        int ans=min(dp[1][0],dp[1][1]);
        if (k&1){
            k--;
            if (k<=ans*2) printf("%d\n",k/2+1);
            else printf("%d\n",(k-ans*2)+ans+1);
        }
        else{
            if (k<=ans*2) printf("%d\n",k/2);
            else printf("%d\n",(k-ans*2)+ans);
        }
    }
    return 0;
}