fork(1) download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. long long dist[1001][1001];
  8. long long cost[1001][1001];
  9.  
  10. vector<int> g[1001];
  11.  
  12. void dfs(int v, int p, int f, long long c)
  13. {
  14. dist[f][v] = dist[v][f] = c;
  15.  
  16. for (int adj_v : g[v])
  17. if (adj_v != p)
  18. dfs(adj_v, v, f, c + cost[v][adj_v]);
  19. }
  20.  
  21. int main()
  22. {
  23. int T;
  24. cin >> T;
  25.  
  26. for (int test_case = 1; test_case <= T; test_case++)
  27. {
  28. int n, k;
  29. cin >> n >> k;
  30.  
  31. for (int v = 1; v <= n; v++)
  32. g[v].clear();
  33.  
  34. for (int v = 2; v <= n; v++)
  35. {
  36. int parent, length;
  37. cin >> parent >> length;
  38.  
  39. cost[parent][v] = cost[v][parent] = length;
  40. g[v].push_back(parent);
  41. g[parent].push_back(v);
  42. }
  43.  
  44. for (int v = 1; v <= n; v++)
  45. dfs(v, v, v, 0);
  46.  
  47. int max_v = 2;
  48. for (int v = 3; v <= n; v++)
  49. if (dist[1][v] > dist[1][max_v])
  50. max_v = v;
  51.  
  52. bool used[1001] = {};
  53. int next[1001] = {};
  54.  
  55. next[1] = max_v;
  56. next[max_v] = 1;
  57. used[max_v] = true;
  58.  
  59. long long max_path_length = 2 * dist[1][max_v];
  60.  
  61. for (int i = 2; i <= k; i++)
  62. {
  63. int best_v = -1;
  64. int best_place = -1;
  65. long long best_increase = -1;
  66.  
  67. for (int v = 2; v <= n; v++)
  68. if (!used[v])
  69. {
  70. int v0 = 1;
  71. int v1 = next[v0];
  72. do
  73. {
  74. long long cur_dist = dist[v0][v1];
  75. long long new_dist = dist[v0][v] + dist[v][v1];
  76. long long increase = new_dist - cur_dist;
  77.  
  78. if (increase > best_increase)
  79. {
  80. best_increase = increase;
  81. best_v = v;
  82. best_place = v0;
  83. }
  84.  
  85. v0 = v1;
  86. v1 = next[v0];
  87.  
  88. } while (v0 != 1);
  89. }
  90.  
  91. used[best_v] = true;
  92.  
  93. int tmp = next[best_place];
  94. next[best_place] = best_v;
  95. next[best_v] = tmp;
  96.  
  97. max_path_length += best_increase;
  98. }
  99.  
  100. cout << "Case #" << test_case << ": " << max_path_length;
  101. if (test_case < T)
  102. cout << '\n';
  103. }
  104. }
Success #stdin #stdout 0s 31744KB
stdin
1
5 3
1 10
2 20
1 20
2 20
stdout
Case #1: 160