【Pet HDU – 4707 】【利用並查集找深度】
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 100000; int T, N, D; int x, y; int f[maxn]; void init() { for(int i = 0; i <= N - 1; i++) f[i] = i; } int Find(int root) { while(root != f[root]) root = f[root]; return root; } int Solve(int x) { int d = 0; while(x != f[x]) { x = f[x]; d++; } return d; } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%d", &T); while(T--) { scanf("%d %d", &N, &D); init(); for(int i = 0; i < N - 1; i++) { scanf("%d %d", &x, &y); f[y] = x; } int ans = 0; for(int i = 0; i < N; i++) { if(Find(i) == 0) { if(Solve(i) > D) ans++; } } printf("%dn",ans); } }
