欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU6228

程序员文章站 2022-05-19 20:55:30
...

考虑某条边,则只要两边的2个顶点都大于等于k,则连边时一定会经过这条边,ans++;

#include <bits/stdc++.h>

using namespace std;
const int N = 2E5 + 7;
int a[N], ans, n, k;
vector<int>g[N];
int dfs(int u, int fa)
{
    a[u] = 1;
    for(auto& it : g[u]) {
        if(it != fa) {
            a[u] += dfs(it, u);
        }
    }
    if(a[u] >= k && n - a[u] >= k) ans ++;
    return a[u];
}
int main()
{
    std::ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while(T --) {
        cin >> n >> k;
        for(int i = 1;i <= n;i ++) g[i].clear();
        ans = 0;
        int u, v;
        for(int i = 1;i < n;i ++) {
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, -1);
        cout << ans << '\n';
    }
    return 0;
}