yicongli

CF1068E

Jan 21st, 2021 (edited)
617
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=1e5+7;
  17.  
  18. int sta[N],tot;
  19. int cnt[N];
  20. set<int>G[N];
  21.  
  22. int main(){
  23.     // freopen(".in","r",stdin);
  24.     // freopen(".out","w",stdout);
  25.     int n,k;r(n),r(k);
  26.     if(k>10){
  27.         return puts("No"),0;
  28.     }
  29.     for(int i=1;i<n;++i){
  30.         int u,v;r(u),r(v);
  31.         G[u].insert(v);
  32.         G[v].insert(u);
  33.     }
  34.     int dep=0,del=0;
  35.     while(del < n-1 && dep <=k){
  36.         for(int i=1;i<=n;++i){
  37.             if(G[i].size()==1){
  38.                 int u=*G[i].begin();
  39.                 sta[++tot]=i;
  40.                 ++cnt[u];
  41.             }
  42.         }
  43.         for(int i=1;i<=tot;++i){
  44.             int u=sta[i];
  45.             int v=*G[u].begin();
  46.             G[u].erase(v);
  47.             G[v].erase(u);
  48.             if(cnt[v]<3){
  49.                 return puts("No"),0;
  50.             }
  51.         }
  52.         del+=tot;
  53.         tot=0;
  54.         ++dep;
  55.     }
  56.     puts(dep==k?"Yes":"No");
  57.     return 0;
  58. }
RAW Paste Data