fork(2) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, k, degree[301], deleted[301], seen[301], distnce[301], diameter;
  5. vector<int> G[301];
  6.  
  7. void getDist(int node, int dist)
  8. {
  9. seen[node] = 1;
  10. for(auto i: G[node]) {
  11. if(not seen[i]) {
  12. if(not deleted[i]) {
  13. getDist(i, dist+1);
  14. }
  15. }
  16. }
  17. distnce[node] = dist;
  18. }
  19.  
  20. int getDiameter()
  21. {
  22. memset(distnce, -1, sizeof distnce);
  23. memset(seen, 0, sizeof seen);
  24. for(int i=0; i<n; i++) {
  25. if(not deleted[i]) {
  26. getDist(i, 0);
  27. break;
  28. }
  29. }
  30. int mxd = -1, mxi;
  31. for(int i=0; i<n; i++) {
  32. if(distnce[i] > mxd) {
  33. mxd = distnce[i];
  34. mxi = i;
  35. }
  36. }
  37. // cout << mxi << endl;
  38. memset(distnce, -1, sizeof distnce);
  39. memset(seen, 0, sizeof seen);
  40. getDist(mxi, 0);
  41. return *(max_element(distnce, distnce+n));
  42. }
  43.  
  44. int calculate(int node)
  45. {
  46. // cout << "calc " << node << endl;
  47. memset(distnce, 0, sizeof distnce);
  48. memset(seen, 0, sizeof seen);
  49. getDist(node, 0);
  50. int ret = 0;
  51. for(int i=0; i<n; i++)
  52. if(distnce[i] == diameter)
  53. ret++;
  54. return ret;
  55. }
  56.  
  57. int main()
  58. {
  59. ios::sync_with_stdio(false);
  60. cin >> n >> k;
  61. for(int i=0, u, v; i<n-1; i++) {
  62. cin >> u >> v;
  63. --u; --v;
  64. G[u].push_back(v);
  65. G[v].push_back(u);
  66. degree[u]++; degree[v]++;
  67. }
  68. memset(deleted, 0, sizeof deleted);
  69. pair<int, int> best(0, -1);
  70. memset(seen, 0, sizeof seen);
  71. diameter = getDiameter();
  72. // cout << "fuck " << endl;
  73. for(int removed = 1; removed <= k; removed++) {
  74. for(int i=0; i<n; i++) {
  75. if(not deleted[i]) {
  76. if(degree[i] == 1) {
  77. int temp = calculate(i);
  78. if(temp > best.first)
  79. best = {temp, i};
  80. }
  81. }
  82. }
  83. deleted[best.second] = 1;
  84. for(auto i: G[best.second])
  85. if(not deleted[i])
  86. degree[i]--;
  87. best = {0, -1};
  88. memset(seen, 0, sizeof seen);
  89. diameter = getDiameter();
  90. }
  91. cout << diameter << endl;
  92. }
  93.  
Success #stdin #stdout 0s 3444KB
stdin
Standard input is empty
stdout
0