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;
}
上一篇: 后序中序求层序