Description
企鹅国的网吧们之间由网线互相连接，形成一棵树的结构。现在由于冬天到了，供暖部门缺少燃料，于是他们决定去拆一些网线来做燃料。但是现在有K只企鹅要上网和别人联机游戏，所以他们需要把这K只企鹅安排到不同的机房（两只企鹅在同一个机房会吵架），然后拆掉一些网线，但是需要保证每只企鹅至少还能通过留下来的网线和至少另一只企鹅联机游戏。
所以他们想知道，最少需要保留多少根网线？
Input
第一行一个整数T，表示数据组数；
每组数据第一行两个整数N，K，表示总共的机房数目和企鹅数目。
第二行N-1个整数，第i个整数Ai表示机房i+1和机房Ai有一根网线连接(1≤Ai≤i)。
Output
每组数据输出一个整数表示最少保留的网线数目。
Solutions
最优的情况一定是一条边匹配两个点，在多一个点对答案的贡献只有一。
贪心的想，就是一条边两个点的尽量多。
这图显然是一颗树，从下往上匹配即可，因为子节点只有唯一的父节点，而父节点却有多个子节点。
代码
1 var 2 TT,n,k,nm,ans:longint; 3 fa,next,ls:array [0..100001] of longint; 4 bo:array [0..100001] of boolean; 5 procedure add(x,y:longint); 6 begin 7 inc(nm); 8 fa[nm]:=y; next[nm]:=ls[x]; 9 ls[x]:=nm; 10 end; 11 12 procedure init; 13 var 14 i,x:longint; 15 begin 16 readln(n,k); 17 fillchar(ls,sizeof(ls),0); 18 fillchar(bo,sizeof(bo),true); 19 nm:=0; ans:=0; 20 for i:=2 to n do 21 begin 22 read(x); 23 add(x,i); 24 end; 25 end; 26 27 procedure dfs(x,y:longint); 28 var 29 i:longint; 30 begin 31 i:=ls[x]; 32 while i<>0 do 33 begin 34 if fa[i]<>y then 35 begin 36 dfs(fa[i],x); 37 if (bo[x]) and (bo[fa[i]]) then 38 begin 39 bo[x]:=false; 40 inc(ans); 41 end; 42 end; 43 i:=next[i]; 44 end; 45 end; 46 47 begin 48 assign(input,'tree.in'); 49 assign(output,'tree.out'); 50 reset(input); 51 rewrite(output); 52 readln(TT); 53 while TT>0 do 54 begin 55 init; 56 dfs(1,0); 57 if ans*2>k then writeln(k div 2+k mod 2) 58 else writeln(ans+(k-ans*2)); 59 dec(TT); 60 end; 61 close(input); 62 close(output); 63 end.