诗意狗
题目描述
怒发冲冠凭栏处,有这样一群狗,它们以诗意为食。有一些诗馆,诗馆之间有道路相连,形成一棵树的结构。为了建一些新的诗馆,诗意狗们必须阻断其间的一些道路,以此保证新诗馆按时建成。
但诗意狗们喜欢一起吟阙歌舞,所以需要保证每一只诗意狗至少要能通过保留下来的道路和至少另外一只诗意狗相互来往。但因为它们都想独占一个诗馆,所以每个诗馆最多只能待一只诗意狗。现在想知道最少需要保留多少条道路,才能让诗意狗们满意?
格式
输入格式
第一行一个整数 \(T\),表示数据组数;
每组数据第一行两个整数 \(N,K\),表示总共的诗馆数目和诗意狗数目。
第二行 \(N-1\) 个整数,第 \(i\) 个整数 \(A_i\) 表示诗馆 \(i+1\) 和诗馆 \(A_i\) 有一条道路连接 \((1≤A_i≤i)\)。
输出格式
每组数据输出一个整数表示最少保留的道路数目。
样例1
样例输入1
2
4 4
1 2 3
4 3
1 1 1
样例输出1
2
2
限制
对于 \(30\%\) 的数据:\(N≤15\);
对于 \(50\%\) 的数据:\(N≤300\);
对于 \(70\%\) 的数据:\(N≤2000\);
对于 \(100\%\) 的数据:\(2≤K≤N≤100000,T≤10\)。