Facebook
From ARIF, 2 Weeks ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 181
  1. /* "بِسْمِ اللهِ الرَّحْمٰنِ الرَّحِيْمِ  " -In the name of Allah."
  2. -------------------- A R I F ----------------------- */
  3.  
  4. #include<bits/stdc++.h>
  5. // for order set ---------------------
  6. #include<ext/pb_ds/assoc_container.hpp>
  7. #include<ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9. #define        ordered_set   tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
  10. #define        index_of(x) find_by_order(x) // index_of the value x
  11. #define        number_of(x) order_of_key(x) // how many value are stricly less then x
  12. // ------------------------------------
  13. #define        int long long int
  14. #define        INF 1e18
  15. #define        PI 3.141592653
  16. #define        PB push_back
  17. #define        F first
  18. #define        S second
  19. #define        MP(x, y) push_back(make_pair(x, y))
  20. #define        srt(v) sort(v.begin(), v.end())
  21. #define        all(x) x.begin(), x.end()
  22. #define        rsrt(v) reverse(v.begin(), v.end())
  23. #define        no cout << "NO" << endl
  24. #define        yes cout << "YES" << "\n"
  25. #define        e "\n"
  26. #define        pair  vector< pair <int ,int> >
  27. #define        deb(args...){string _s = #args;replace(_s.begin(), _s.end(), ',', ' ');stringstream _ss(_s);istream_iterator<string> _it(_ss);err(_it, args);}
  28.  
  29. using namespace std;
  30.  
  31. template <typename T>
  32. ostream &operator;<<(ostream &os;, const vector<T> &v){ os << '{'; for (const auto &x : v) os << " " << x; return os << '}';}
  33. void err(istream_iterator<string> it) {} template <typename T, typename... Args>
  34. void err(istream_iterator<string> it, T a, Args... args){ cerr << *it <<"  = " << a << endl; err(++it, args...);}
  35. /*----------------------------------------------------------------------------------------*/
  36. int expo(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
  37. int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
  38. int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
  39. int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
  40. int mminvprime(int a, int b) {return expo(a, b - 2, b);}
  41. int mod_div(int a, int b, int m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
  42. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  43. int getRandomNumber(int l, int r) {return uniform_int_distribution<int>(l, r)(rng);}
  44. bool isBitSet(int num, int bitPosition) { return (num & (1 << bitPosition)) > 0 ; }
  45. /*----------------------------------------------------------------------------------------*/
  46. //---------DFS----------------------------------------------------------------
  47. const int mx = 1e6+7 ;
  48. vector<int> g[mx] ;
  49. int vis[mx] = {0} ;
  50. int arr[mx] = {0} ;
  51. void graph(int u , int v )
  52. {
  53.     g[u].PB(v) ; g[v].PB(u) ;
  54. }
  55. int k , final = 0 ;
  56. void dfs(int node , int par)
  57. {
  58.     vis[node] = 1 ;
  59.     if(g[node].size() == 1){
  60.         arr[node] = 1 ;
  61.     }
  62.     for(auto it : g[node])
  63.         if(!vis[it])
  64.             dfs(it , node) ;
  65.    std::map<int, int> mp;
  66.    if(g[node].size() != 1){
  67.         for(auto it : g[node]){
  68.             mp[arr[it]]++;
  69.         }
  70.         if(par != -1  and g[par].size() == 1) mp[1]++;
  71.         for(int i =1 ; i<= k ; i++){
  72.             if(!mp[i]){
  73.                 arr[node] = i ;
  74.                 break ;
  75.             }
  76.         }
  77.    }
  78. }
  79.  
  80. void dfs2(int node , int value)
  81. {
  82.     vis[node] = 1 ;
  83.     if(value == 1){
  84.         arr[node] = 2 ;
  85.     }else arr[node] = 1 ;
  86.     for(auto it : g[node])
  87.         if(!vis[it])
  88.             dfs2(it , arr[node]) ;
  89. }
  90. void dfs3(int node , int value)
  91. {
  92.     vis[node] = 1 ;
  93.     if(value == 1){
  94.         arr[node] = 2 ;
  95.     }else if(value == 1 and g[node].size() != 1){
  96.         arr[node] = 3 ;
  97.     }
  98.     else arr[node] = 1 ;
  99.     for(auto it : g[node])
  100.         if(!vis[it])
  101.             dfs3(it , arr[node]) ;
  102. }
  103. void Clear(int n)
  104. {
  105.   for(int i =0 ; i<=n ; i++)
  106.   {
  107.     vis[i] =0 ;
  108.     arr[i] = 0 ;
  109.     final = 0 ;
  110.   }
  111. }
  112. int ok(int n )
  113. {
  114.     std::map<int, int> mp;
  115.     for(int i =1 ; i<=n ; i++){
  116.         mp[arr[i]]++ ;
  117.     }
  118.     int ind = 1 ;
  119.     std::vector<int> v;
  120.     for(auto it : mp){
  121.         v.PB(it.S) ;
  122.     }
  123.     srt(v) ; rsrt(v) ;
  124.     int ans = 0 ;
  125.     for(auto it : v){
  126.         ans += (it*ind);
  127.         ind++ ;
  128.     }
  129.     return ans ;
  130. }
  131. //---------DFS----------------------------------------------------------------
  132. void   solve()
  133. {
  134.     int n = 0 , m = 0 , ans = 0 , cnt  = 0 ;
  135.     cin >> n >> k ;
  136.     for(int i =0 ; i<n-1 ; i++){
  137.         int u , v ;
  138.         cin >> u >> v ;
  139.         graph(u , v) ;
  140.     }
  141.     if(n == 1){
  142.         cout << 1 << e ; return ;
  143.     }
  144.     if(k == 1){
  145.         cout << -1 << e ; return ;
  146.     }
  147.     if(k>2){
  148.         for(int i =1 ; i<= n ; i++)
  149.             if(!vis[i])
  150.                 dfs(i, -1) ;
  151.         ans = ok(n) ;
  152.         Clear(n) ;
  153.          for(int i= 1; i<=n ; i++)
  154.             if(!vis[i])
  155.                 dfs2(i , 0) ;
  156.         ans = min(ans , ok(n)) ;
  157.           Clear(n) ;
  158.          for(int i= 1; i<=n ; i++)
  159.             if(!vis[i])
  160.                 dfs3(i , 0) ;
  161.         ans = min(ans , ok(n)) ;
  162.     }
  163.     else{
  164.         for(int i= 1; i<=n ; i++)
  165.             if(!vis[i])
  166.                 dfs2(i , 0) ;
  167.         ans = ok(n) ;
  168.     }
  169.    
  170.     cout << ans << e ;
  171. }
  172. int32_t main()
  173. {
  174.  
  175.     ios_base::sync_with_stdio(false);cin.tie(NULL);
  176.     // freopen("input.txt", "r", stdin);
  177.     // freopen("output.txt", "w", stdout);
  178.     int test_case =1;
  179.     // cin >> test_case ;
  180.     int c = 0 ;
  181.     while( test_case --)
  182.     {
  183.       // c ++ ; cout << "Case " << c << ": " ;
  184.        solve() ;  
  185.     }
  186. }
  187. //vector<int>::iterator lower, upper;
  188. //lower = lower_bound(v.begin(), v.end(), value) - v.begin() ;
  189. //upper = upper_bound(v.begin(), v.end(), value) - v.begin() ; --&gt;
  190. // scanf("%s%d",s,&x) != EOF
  191.