本文共 1394 字，大约阅读时间需要 4 分钟。

有一棵n个节点的树，树上有k只猴子，这k只猴子所在位置可任意指定，但是每个点上最多只能有一只猴子，现在你要切掉尽可能多的边，但必须保证没有任何一只猴子被完全孤立，求最少得保留多少条边

题目还好，只不过偏要卡个常数，普通的快读都不行，还要更快的。。

从所有的叶子开始两个点两个点的取，相当于每两只猴子连一条边，取到根结束

之后剩下还没安放的猴子就只能每一只连一条边

PS：这个快读只能用文件读入

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;vector
       
         G[100005];int k, ans, vis[100005];struct FastIO{    static const int S = 2*100;    int wpos;    char wbuf[S];    FastIO() : wpos(0) {}    inline int xchar()    {        static char buf[S];        static int len = 0, pos = 0;        if (pos==len)            pos = 0, len = fread(buf, 1, S, stdin);        if (pos==len) exit(0);        return buf[pos ++];    }    inline int xint()    {        int s = 1, c = xchar(), x = 0;        while(c<=32) c = xchar();        if(c=='-') s = -1, c = xchar();        for(;'0'<=c && c<='9';c=xchar()) x = x*10+c-'0';        return x * s;    }    ~FastIO()    {        if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;    }}io;void Sech(int u, int p){	int i, v;	for(i=0;i
        
         =2) k -= 2, ans++; return; } } return;}int main(void){ int T, n, i, u; //freopen("in.txt", "r", stdin); scanf("%d", &T); while(T--) { n = io.xint(); k = io.xint(); for(i=1;i<=n;i++) G[i].clear(); for(i=2;i<=n;i++) { u = io.xint(); G[u].push_back(i); G[i].push_back(u); } ans = 0; memset(vis, 0, sizeof(vis)); Sech(1, 0); printf("%d\n", ans+k); } return 0;}