题意：要在一棵 n 个点的树上放 k 只猴子，然后删掉尽量多的边，使得删边后，每只猴子都至少和另外一只猴子相连，问最后剩下的边数。
思路：其实dfs遍历一次看有多少个点-边-点就好了，比赛的时候就觉得要从树尾开始分，其实不是，dfs遍历，vis标记就好了。这题的输入很大，要用多校给过的读入挂。
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#include <time.h>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = +;
const int N = ;
const ll maxm = 1e7;
const int INF = 0x3f;
const int mod=;
const ll inf = 1e15 + ;
const db eps = 1e-;
namespace fastIO {
#define BUF_SIZE 100000
// fread -> read
bool IOerror = ; char nc() {
static char buf[BUF_SIZE], *pl = buf + BUF_SIZE, *pr = buf + BUF_SIZE;
if(pl == pr) {
pl = buf;
pr = buf + fread(buf, , BUF_SIZE, stdin);
if(pr == pl) {
IOerror = ;
return -;
}
}
return *pl++;
} inline bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
} void read(int &x) {
char ch;
while(blank(ch = nc()));
if(IOerror)
return;
for(x = ch - ''; (ch = nc()) >= '' && ch <= ''; x = x * + ch - '');
}
#undef BUF_SIZE
};
using namespace fastIO;
struct Edge{
int u, v, next;
}e[maxn*];
int head[maxn*], cnt, vis[maxn*];
int dan; void init() {
cnt=, dan=;
memset(head, -, sizeof(head));
memset(vis, , sizeof(vis));
}
void add(int u, int v) {
e[cnt].v=v, e[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int u, int fa) {
for (int i=head[u]; ~i; i=e[i].next) {
int v=e[i].v;
if (v!=fa && v!=u) {
dfs(v, u);
if (!vis[v]) {
if (!vis[u]) {
vis[u]=vis[v]=;
}
else dan++;
}
}
}
}
void solve() {
init();
int n, k;
read(n); read(k);
for (int i=; i<=n-; i++) {
int u; read(u);
add(u, i+); add(i+, u);
}
dfs(, );
if (!vis[]) dan++;
int can=(n-dan)/;
int ans=;
if (*can<k) {
ans=k-can;
}
else ans=(k+)/;
printf("%d\n", ans);
}
int main() {
int t = ;
//freopen("in.txt", "r", stdin);
//scanf("%d", &t);
read(t);
while(t--)
solve();
return ;
}