【NOIP2017提高A组冲刺11.6】拆网线

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

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

欸？AC了？

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

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

inline int rd(){

    int ret=,f=;char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-:;

    while(isdigit(c))ret=ret*+c-'',c=getchar();

    return ret*f;

}

const int MAXN=;

struct Edge{

    int next,to;

}e[MAXN<<];

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][];

void dfs(int x,int pre){

    f[x][]=;

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].to;

        if(v==pre) continue;

        dfs(v,x);

        f[x][]+=f[v][];

        f[x][]+=max(f[v][],f[v][]);

    }

}

void solve(){

    memset(f,,sizeof(f));

    memset(head,,sizeof(head));

    ecnt=;

    n=rd();m=rd();

    for(int i=;i<=n;i++){

        int x=rd();

        add(i,x);add(x,i);

    }

    dfs(,);

    int ans=n-max(f[][],f[][]);

    if(ans*>=m) cout<<(m+)/<<endl;

    else cout<<ans+(m-ans*)<<endl;

}

int main(){

    freopen("tree.in","r",stdin);

    freopen("tree.out","w",stdout);

    T=rd();

    while(T--) solve();

    return ;

}