fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n, k;
  10. 	cin >> n >> k;
  11.  
  12. 	vector<vector<int>> g(n + 1, vector<int>());
  13.  
  14.  
  15. 	vector<int> dep;
  16. 	for(int i = 0; i < n - 1; i++){
  17. 		int x, y;
  18. 		cin >> x >> y;
  19. 		g[x].push_back(y);
  20. 		g[y].push_back(x);
  21. 	}
  22.  
  23. 	auto dfs = [&](int x, int par, int d, auto && self) -> int {
  24. 		int cnt = 0;
  25. 		for(auto y: g[x]){
  26. 			if(y != par){
  27. 				cnt += self(y, x, d + 1, self);
  28. 			}
  29. 		}
  30. 		dep.push_back(d - cnt);
  31. 		return cnt + 1;
  32. 	};
  33.  
  34. 	dfs(1, 0, 0, dfs);
  35.  
  36. 	sort(dep.rbegin(), dep.rend());
  37.  
  38. 	ll ans = 0;
  39.  
  40. 	for(int i = 0; i < k; i++){
  41. 		ans += dep[i];
  42. 	}
  43.  
  44. 	cout << ans << "\n";
  45.  
  46.  
  47.  
  48.  
  49.  
  50. }
  51.  
  52. int main(){
  53. 	ios_base::sync_with_stdio(false);
  54. 	cin.tie(nullptr);
  55.  
  56. 	int t = 1;
  57. 	// cin >> t;
  58.  
  59. 	for(int i = 1; i <= t; i++){
  60. 		solve();
  61. 	}
  62. 	return 0;
  63. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
8 5
7 5
1 7
6 1
3 7
8 3
2 1
4 5
stdout
copy 
9
https://ideone.com/nJAVJx
language:
C++14 (gcc 8.3)
created:
7 hours 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!