hdu--6178(多校

　　题意：要在一棵 n 个点的树上放 k 只猴子，然后删掉尽量多的边，使得删边后，每只猴子都至少和另外一只猴子相连，问最后剩下的边数。

　　思路：其实dfs遍历一次看有多少个点-边-点就好了，比赛的时候就觉得要从树尾开始分，其实不是，dfs遍历，vis标记就好了。这题的输入很大，要用多校给过的读入挂。

#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<cstring>

#include<queue>

#include<set>

#include<string>

#include<map>

#include <time.h>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = +;

const int N = ;

const ll maxm = 1e7;

const int INF = 0x3f;

const int mod=;

const ll inf = 1e15 + ;

const db eps = 1e-;

namespace fastIO {

    #define BUF_SIZE 100000

    // fread -> read

    bool IOerror = ;

    char nc() {

        static char buf[BUF_SIZE], *pl = buf + BUF_SIZE, *pr = buf + BUF_SIZE;

        if(pl == pr) {

            pl = buf;

            pr = buf + fread(buf, , BUF_SIZE, stdin);

            if(pr == pl) {

                IOerror = ;

                return -;

            }

        }

        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 - ''; (ch = nc()) >= '' && ch <= ''; x = x *  + ch - '');

    }

    #undef BUF_SIZE

};

using namespace fastIO;

struct Edge{

    int u, v, next;

}e[maxn*];

int head[maxn*], cnt, vis[maxn*];

int dan;

void init() {

    cnt=, dan=;

    memset(head, -, sizeof(head));

    memset(vis, , sizeof(vis));

}

void add(int u, int v) {

    e[cnt].v=v, e[cnt].next=head[u];

    head[u]=cnt++;

}

void dfs(int u, int fa) {

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

        int v=e[i].v;

        if (v!=fa && v!=u)  {

            dfs(v, u);

            if (!vis[v]) {

                if (!vis[u]) {

                    vis[u]=vis[v]=;

                }

                else  dan++;

            }

        }

    }

}

void solve() {

    init();

    int n, k;

    read(n);  read(k);

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

        int u;  read(u);

        add(u, i+);  add(i+, u);

    }

    dfs(, );

    if (!vis[])  dan++;

    int can=(n-dan)/;

    int ans=;

    if (*can<k)  {

        ans=k-can;

    }

    else  ans=(k+)/;

    printf("%d\n", ans);

}

int main() {

    int t = ;

    //freopen("in.txt", "r", stdin);

    //scanf("%d", &t);

    read(t);

    while(t--)

        solve();

    return ;

}