fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<long long> dis;
  5. vector<bool> cyc;
  6.  
  7. int cycV, cycU;
  8.  
  9. void findDistance(auto &G, int v, int p, long long d, bool findAnswer = false) {
  10. 	dis[v] = d;
  11. 	for (auto u : G[v]) {
  12. 		if (u == p || (findAnswer && cyc[u])) continue;
  13. 		findDistance(G, u, v, d + 1);
  14. 	}
  15. }
  16.  
  17. bool captureCycleVert(auto &G, int v, int p = -1) {
  18. 	if (v == cycU) return cyc[v] = true;
  19. 	for (auto u : G[v]) {
  20. 		if (u == p) continue;
  21. 		if (captureCycleVert(G, u, v)) {
  22. 			return cyc[v] = true;
  23. 		}
  24. 	}
  25. 	return cyc[v];
  26. }
  27.  
  28. int main() {
  29. 	ios::sync_with_stdio(false);
  30. 	cin.tie(nullptr);
  31.  
  32. 	int t;
  33. 	cin >> t;
  34. 	for (int T = 1; T <= t; T++) {
  35. 		int n;
  36. 		cin >> n;
  37.  
  38. 		vector<vector<int>> G(n);
  39. 		dis.assign(n, 0);
  40.  
  41. 		for (int i = 1; i < n; i++) {
  42. 			int u, v;
  43. 			cin >> u >> v;
  44. 			u--, v--;
  45. 			G[u].push_back(v);
  46. 			G[v].push_back(u);
  47. 		}
  48.  
  49. 		findDistance(G, 0, -1, 0);         
  50. 		cycV = max_element(dis.begin(), dis.end()) - dis.begin();
  51. 		findDistance(G, cycV, -1, 0);
  52. 		cycU = max_element(dis.begin(), dis.end()) - dis.begin();
  53.  
  54. 		cyc.assign(n, false);
  55. 		captureCycleVert(G, cycV);
  56.  
  57. 		long long ans = 0;
  58. 		for (int i = 0; i < n; i++) {
  59. 			if (cyc[i]) findDistance(G, i, -1, 0, true);
  60. 		}
  61.  
  62. 		ans = accumulate(dis.begin(), dis.end(), 0ll);
  63. 		cout << "Case " << T << ": " << ans << "\n";
  64. 	}
  65. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aif9xk
language:
C++14 (gcc 8.3)
created:
10 days 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!