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(vector<vector<int>> &G, int v, int p, long long d, bool findAnswer = false) {
  10. 	dis[v] = d;
  11. 	for (int u : G[v]) {
  12. 		if (u == p || (findAnswer && cyc[u])) continue;
  13. 		findDistance(G, u, v, d + 1);
  14. 	}
  15. }
  16.  
  17. bool captureCycleVert(vector<vector<int>> &G, int v, int p = -1) {
  18. 	if (v == cycU) return cyc[v] = true;
  19. 	for (int 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; cin >> n;
  36.  
  37. 		vector<vector<int>> G(n);
  38. 		dis.assign(n, 0);
  39.  
  40. 		for (int i = 1; i < n; i++) {
  41. 			int u, v;
  42. 			cin >> u >> v;
  43. 			u--, v--;
  44. 			G[u].push_back(v);
  45. 			G[v].push_back(u);
  46. 		}
  47.  
  48. 		findDistance(G, 0, -1, 0);         
  49. 		cycV = max_element(dis.begin(), dis.end()) - dis.begin();
  50. 		findDistance(G, cycV, -1, 0);
  51. 		cycU = max_element(dis.begin(), dis.end()) - dis.begin();
  52.  
  53. 		cyc.assign(n, false);
  54. 		captureCycleVert(G, cycV);
  55.  
  56. 		long long ans = 0;
  57. 		for (int i = 0; i < n; i++) {
  58. 			if (cyc[i]) findDistance(G, i, -1, 0, true);
  59. 		}
  60.  
  61. 		ans = accumulate(dis.begin(), dis.end(), 0ll);
  62. 		cout << "Case " << T << ": " << ans << "\n";
  63. 	}
  64. }
Success #stdin #stdout 0.01s 5220KB
comments (?)
stdin
copy 
2
6
1 5
5 2
5 6
3 5
3 4
13
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
13 10
stdout
copy 
Case 1: 2
Case 2: 11
https://ideone.com/7IySV6
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!