2017沈阳L，Tree，hdu6228

读题读半天，出题人的英语真是。。

分析是求连着k和k的子图的路径的长度，然后发现这样的路有岔路。。

然后想每条边要左边是k个右边是k个。

然后想写两发dfs有点难写

最后想到一遍dfs就行，另一边是n-cnt【i】

#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 200010;
typedef long long ll;
#define se second
#define fi first
#define rep(i, n, m) for(int i = (n); i <= (m); i++)

// struct Edge {
//     int u, v, id;
//     Edge(int a=0, int b=0, int c = 0):u(a), v(b), id(c){}
// }edge[N];

// vector<Edge> T[N];
// int n, k, ans, t;
// int a[N];

// int dfs(int u, int fa, int num, int eid)
// {//cout << u << ' ' << fa << ' ' << num << ' ' << eid << endl;
//     a[eid] = num;

//     b[eid] += 1;
//     for(int i = 0; i < T[u].size(); i++) {
//         if(T[u][i].v != fa) {
//             b[eid] += dfs(T[u][i].v, u, num + 1, T[u][i].id);
//         }
//     }
//     return b[eid];
// }

// int dfs(int v, int id)
// {//cout << u << ' ' << v << endl;
//     int num = 1;
//     for(int i = 0; i < T[v].size(); i++) {
//         if(T[v][i].id == id) continue;
//         num += dfs(T[v][i].v, T[v][i].id);
//     }
//     return num;
// }

vector<int> T[N];
int a[N], t, n, k, ans;

void dfs(int u, int v)
{
    a[v] = 1;
    for(int i = 0; i < T[v].size(); i++) {
        if(T[v][i] != u) {
            dfs(v, T[v][i]);
            a[v] += a[T[v][i]];
        }
    }
}

int main () {
    #ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif

    cin >> t;

    while(t--) {
        scanf("%d%d", &n, &k);
        rep(i, 0, n) T[i].clear();
        memset(a, 0, sizeof(int)*(n+1));
        // memset(b, 0, sizeof(int)*(n+1));
        // memset(deg, 0, sizeof(int)*(n+1));

        rep(i, 1, n - 1) {
            int u, v;
            scanf("%d%d", &u, &v);
            T[u].push_back(v);
            T[v].push_back(u);
            // T[u].push_back(Edge(u, v, i));
            // T[v].push_back(Edge(v, u, i));
        //    deg[u]++, deg[v]++;
        }

        // int le;
        // rep(i, 1, n) if(deg[i] == 1) {
        //     le = i;
        //     break;
        // } 

//         dfs(le, 0, 0, 0);
// rep(i, 1, n) {
//     cout << a[i] << ' ' << b[i] << endl;
// }
        // ans = 0;
        // rep(i, 1, n - 1) {
        //     if(a[i] >= k && b[i] >= k) {
        //         ans++;
        //     }
        // }

        dfs(0, 1);
//rep(i, 1, n) cout << "a " << a[i] << endl;

        ans = 0;
        rep(i, 1, n) {
            if(a[i] >= k && n - a[i] >= k) {
                ans++;
            }
        }

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

    return 0;
}