fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <string>
  4. #include <cstring>
  5. #include <cstdio>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <unordered_map>
  12. #include <queue>
  13. #include <deque>
  14. #include <stack>
  15. #include <bitset>
  16. #include <iomanip>
  17.  
  18. #define ll long long
  19. #define ld long double
  20. #define ull unsigned long long
  21. #define endl "\n"
  22. #define MohamedMotaz ios::sync_with_stdio(0); cin.tie(0); ios_base::sync_with_stdio(0);
  23. #define f(a, b, c) for(int a = b; a < c; a++)
  24. #define fr(a, b, c) for(int a = b; a >= c; a--)
  25. using namespace std;
  26.  
  27.  
  28. //ll fact[1000001]; ll inv[1000001];
  29. //ll primes[100007];
  30. //ll arr[1000007];
  31. //ll modPower(ll b, ll p) {
  32. //	if (p == 0)
  33. //		return 1;
  34. //
  35. //	ll halfpow = modPower(b, p / 2);
  36. //	ll toReturn = (halfpow * halfpow) % mod;
  37. //	if (p % 2)
  38. //		toReturn = (toReturn * b) % mod;
  39. //
  40. //	return toReturn;
  41. //}
  42. //
  43. //ll fastPower(ll b, ll p) {
  44. //	if (p == 0)
  45. //		return 1;
  46. //	ll ans = fastPower(b, p / 2);
  47. //	ans = (ans * ans);
  48. //	if (p % 2 != 0)
  49. //		ans = (ans * b);
  50. //	return ans;
  51. //}
  52. //ll GcdRecursive(ll a, ll b) {
  53. //	if (b == 0) return a;
  54. //	return GcdRecursive(b, a % b);
  55. //}
  56. //ll modLCM(ll a, ll b) {
  57. //	ll val = GcdRecursive(a, b);
  58. //	ll tmp = ((a % mod) * (b % mod)) % mod;
  59. //	ll finalVal = ((tmp % mod) * (arr[val] % mod)) % mod;
  60. //	return finalVal;
  61. //
  62. //}
  63. //ll LCM(ll a, ll b) {
  64. //	return (a * b) / GcdRecursive(a, b);
  65. //}
  66. //void move1step(ll& a, ll& b, ll q) { // a and b by reference
  67. //	ll c = a - q * b;
  68. //	a = b;
  69. //	b = c;
  70. //}
  71. //ll GcdIterative(ll a, ll b) {
  72. //	while (b) move1step(a, b, a / b);
  73. //	return a;
  74. //}
  75. //
  76. //void pre(ll n) {
  77. //
  78. //	fact[0] = 1;
  79. //	inv[0] = 1;
  80. //
  81. //	for (ll i = 1; i <= n; i++) {
  82. //		fact[i] = (i * fact[i - 1]) % mod;
  83. //		inv[i] = modPower(fact[i], mod - 2);
  84. //		arr[i] = modPower(i, mod - 2);
  85. //	}
  86. //}
  87. //
  88. //ll npr(ll n, ll r) {
  89. //	return ((fact[n] * inv[n - r]) % mod);
  90. //}
  91. //
  92. //ll ncr(ll n, ll r) {
  93. //	return ((((fact[n] * inv[n - r]) % mod) * inv[r]) % mod);
  94. //}
  95. //
  96. //void sieve(ll val) {
  97. //	memset(primes, 1, sizeof primes);
  98. //	primes[0] = primes[1] = false;
  99. //	for (int i = 2; i <= val; i++) {
  100. //		if (primes[i]) {
  101. //			for (int j = i * i; j <= val; j += i) {
  102. //				primes[j] = 0;
  103. //			}
  104. //		}
  105. //	}
  106. //
  107. //}
  108.  
  109. const ll mod = 1e9 + 7;
  110. const ll N = 2e6 + 7;
  111. const ll inf = 1e9 + 5;
  112.  
  113.  
  114. ll n, k, a, b;
  115. vector<ll> adjList[N];
  116. vector<ll> allPaths;
  117. bool visited[N] = {false};
  118.  
  119. void dfs(ll node, ll lvl){
  120.     ll counter = 0;
  121.     if (visited[node]) return;
  122.     visited[node] = 1;
  123.  
  124.     for (auto child: adjList[node]){
  125.         if (!visited[child]){
  126.             counter++;
  127.             dfs(child, lvl + 1);
  128.         }
  129.     }
  130.     if (!counter){
  131.         allPaths.push_back(lvl + 1);
  132.     }
  133. }
  134.  
  135. int main()
  136. {
  137.     MohamedMotaz;
  138.     memset(visited, false, sizeof(visited));
  139.     cin >> n >> k;
  140.     f(i,0,n - 1){
  141.         cin >> a >> b;
  142.         adjList[a].push_back(b);
  143.         adjList[b].push_back(a);
  144.     }
  145.     dfs(1, 0);
  146.     sort(allPaths.begin(), allPaths.end());
  147.     //for (auto elem: allPaths) cout << elem << " ";cout << endl;
  148.     vector<ll> copy;
  149.     for (auto elem: allPaths) copy.push_back(elem);
  150.  
  151.     while (k){
  152.         sort(copy.begin(), copy.end());
  153.         fr(i,copy.size() - 1, 0){
  154.             copy[i]--;
  155.             k--;
  156.             if (k <= 0) break;
  157.         }
  158.     }
  159.     sort(copy.begin(), copy.end());
  160.     //for (auto elem: copy) cout << elem << " ";cout << endl;
  161.     ll s = 0;
  162.     fr(i, allPaths.size() - 1, 0){
  163.  
  164.             s += copy[i] * (allPaths[i] - copy[i]);
  165.  
  166.     }
  167.     if (k > copy.size()) s -= copy.size() *(k - copy.size());
  168.     cout << max(s, (ll)0) << endl;
  169.  
  170. }
  171.  
  172.  
  173.  
  174.  
Success #stdin #stdout 0.02s 52328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/EhLzvj
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!