Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*input
- 1
- 4 2
- 1 2
- 2 3
- 3 4
- */
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- #define int long long
- #define double long double
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define RE(i,n) for (int i = 1; i <= n; i++)
- #define RED(i,n) for (int i = n; i > 0; i--)
- #define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
- #define REP(i,n) for (int i = 0; i < (int)n; i++)
- #define FOR(i,a,b) for (int i = a; i < b; i++)
- #define REPD(i,n) for (int i = n-1; i >= 0; i--)
- #define FORD(i,a,b) for (int i = a; i >= b; i--)
- #define all(v) v.begin(),v.end()
- #define pii pair<int,int>
- #define vi vector<int>
- #define vvi vector<vi>
- #define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
- #define debug(x) cout << x << endl;
- #define debug2(x,y) cout << x << " " << y << endl;
- #define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
- typedef tree<
- int,
- null_type,
- less<int>,
- rb_tree_tag,
- tree_order_statistics_node_update>
- ordered_set;
- const int INF = 1e18+1;
- const int MOD = 1e9+7;
- const double PI = 3.14159265358979323846264338;
- int raise(int a,int n,int m = MOD){
- if(n == 0)return 1;
- if(n == 1)return a;
- int x = 1;
- x *= raise(a,n/2,m);
- x %= m;
- x *= x;
- x %= m;
- if(n%2)x*= a;
- x %= m;
- return x;
- }
- int floor1(int n,int k){
- if(n%k == 0 || n >= 0)return n/k;
- return (n/k)-1;
- }
- int ceil1(int n,int k){
- return floor1(n+k-1,k);
- }
- const int N = 5e5+1;
- int le[N];
- vector<int> adj[N];
- int n;
- int k;
- int vis = 0;
- void dfs(int u,int p){
- //cout << u << endl;
- le[u] = 1;
- vis++;
- if(adj[u].size() == 1){
- le[u] = 1;
- }
- for(auto v:adj[u]){
- if(v == p)continue;
- dfs(v,u);
- le[u] = max(le[u],le[v]+1);
- }
- }
- void solve(){
- cin >> n >> k;
- //assert(n < N and k <= n);
- RE(i,n){
- adj[i].clear();
- }
- RE(i,n-1){
- int a,b;cin >> a >> b;
- adj[a].pb(b);
- adj[b].pb(a);
- }
- dfs(1,1);
- int ans = 0;
- RE(i,n){
- if(le[i] <= k)ans++;
- }
- //cout << vis << endl;
- cout << ans << endl;
- }
- signed main(){
- ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- //freopen("sub1final.txt","r",stdin);freopen("sub1finalout.txt","w",stdout);
- int t = 1;
- cin >> t;
- while(t--){
- solve();
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment