和syq大兄弟吐槽题目不小心yy出了正解..

最优的选法就是选两个两个相互独立的，欸这不就是最大匹配吗？那多的企鹅就新加一条边呗？不够的就除以2上取整呗？

欸？AC了？

树也是一个二分图，最大匹配=最小点覆盖=N-最大独立集，树上的最大独立集就是没有上司的舞会，没了。

#include
     
      #include
      
       #include
       
        using namespace std;inline int rd(){    int ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}const int MAXN=100005;struct Edge{    int next,to;}e[MAXN<<1];int ecnt,head[MAXN];inline void add(int x,int y){    e[++ecnt].next = head[x];    e[ecnt].to = y;    head[x] = ecnt;}int n,m,T;int f[MAXN][2];void dfs(int x,int pre){    f[x][1]=1;    for(int i=head[x];i;i=e[i].next){        int v=e[i].to;        if(v==pre) continue;        dfs(v,x);        f[x][1]+=f[v][0];        f[x][0]+=max(f[v][0],f[v][1]);    }}void solve(){    memset(f,0,sizeof(f));    memset(head,0,sizeof(head));    ecnt=0;        n=rd();m=rd();    for(int i=2;i<=n;i++){        int x=rd();        add(i,x);add(x,i);    }    dfs(1,0);    int ans=n-max(f[1][1],f[1][0]);    if(ans*2>=m) cout<<(m+1)/2<