题意：给出一棵 N 个节点树，上面有 K 个猴子，然后竟可能删边，但是每一只猴子必须有直接相邻的猴子与之相邻。求最少剩下几条边。

 

分析：一条边可以用两只猴子站，这样的一条点对，越多越好，如果是ans个，ans*2>=k，那么只需要 (k+1)/2 条边。

否则，需要  ans + (k-ans*2) 条边。

现在问题就转为求这样的点对有多少，哈哈，有漏洞的DP都AC了，哈哈~~~~。

我发现标程思路也是这样，哈哈，都是bug程序！！！

唯一的解释就是 d[u][1] >= d[u][0] 感性认识

#include 
     
      using namespace std;const int maxn = 100005;vector
      
        g[maxn];/*------- 开挂 -------*/namespace fastIO {    #define BUF_SIZE 100000    // fread -> read    bool IOerror = 0;    char nc() {        static char buf[BUF_SIZE], *pl = buf + BUF_SIZE, *pr = buf + BUF_SIZE;        if(pl == pr) {            pl = buf;            pr = buf + fread(buf, 1, BUF_SIZE, stdin);            if(pr == pl) {                IOerror = 1;                return -1;            }        }        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 - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');    }    #undef BUF_SIZE};using namespace fastIO;/*------- 完结 -------*/int d[maxn][2]; // 0 匹配bool vis[maxn];void dp(int u,int fa) {    if(vis[u]) return;    vis[u] = 1;    d[u][0] = d[u][1] = 0;    int sum = 0;    for(int i=0; i < (int)g[u].size(); i++) {        int v = g[u][i];        if(v==fa) continue;        dp(v,u);        d[u][1] += max(d[v][0],d[v][1]);        sum+=d[v][0];    }    for(int i=0; i < (int)g[u].size(); i++) {        int v = g[u][i];        if(v==fa) continue;        d[u][0] = max(d[u][0],sum-d[v][0]+d[v][1]+1);    }}int T;int N,K;int main(){    //freopen("in.txt","r",stdin);    read(T);    while(T--) {        read(N);        read(K);        for(int i=0; i <= N; i++)            g[i].clear();        memset(vis,0,sizeof(vis));        int u;        for(int i=1; i < N; i++) {            read(u);            g[u].push_back(i+1);            g[i+1].push_back(u);        }        dp(1,-1);        int ans = max(d[1][1],d[1][0]);        if(ans*2>=K)            printf("%d\n",(K+1)/2);        else            printf("%d\n",ans+K-(ans*2));    }    return 0;}