fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. typedef pair<int, int> ii;
  5. typedef vector<int> vi;
  6. typedef vector<ll> vl;
  7. typedef vector<vi> vvi;
  8. typedef vector<vl> vvl;
  9. typedef vector<ii> vii;
  10. #define rep(i, n) for(int i = 0; i < n; ++i)
  11. #define repd(i, n) for(int i = n-1; i >= 0; --i)
  12. #define sz(x) (int)(x).size()
  13. #define all(v) v.begin(), v.end()
  14.  
  15. struct st { int m1, rv, m2; };
  16.  
  17. st dfs(int u, int p, vvi& g) {
  18. 	unordered_map<int, int> diff; int sum = 0;
  19. 	for (int v : g[u]) if (v!=p) {
  20. 		st ch = dfs(v, u, g);
  21. 		sum += ch.m1;
  22. 		diff[ch.rv] += ch.m2-ch.m1;
  23. 	}
  24. 	int rv = 1, gap = 0; st ch{INT_MAX, 0, 0};
  25. 	while (true) {
  26. 		int val = rv+sum+diff[rv];
  27. 		if (val<ch.m1) ch.m2 = ch.m1, ch.m1 = val, ch.rv = rv;
  28. 		else if (val<ch.m2) ch.m2 = val;
  29. 		if (diff[rv]==0) gap++;
  30. 		if (gap==2) break;
  31. 		rv++;
  32. 	}
  33. 	return ch;
  34. }
  35.  
  36. int main(int argc, char* argv[]) {
  37. 	int t; cin>>t;
  38. 	rep(ti, t) {
  39. 		int n; cin>>n;
  40. 		vvi g(n, vi());
  41. 		rep(i, n) {
  42. 			int u = i, v; cin>>v; v--;
  43. 			if (v<0) continue;
  44. 			g[u].push_back(v);
  45. 			g[v].push_back(u);
  46. 		}
  47. 		int res = dfs(0, -1, g).m1;
  48. 		cout<<"Case #"<<(ti+1)<<": "<<res<<endl;
  49. 	}
  50. }
  51.  
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
5
3
0 1 1
8
0 1 1 2 2 3 3 3
5
0 1 2 3 4
9
0 1 2 3 4 5 5 5 5
8
0 1 1 1 1 2 2 2
stdout
copy 
Case #1: 4
Case #2: 10
Case #3: 7
Case #4: 12
Case #5: 11
https://ideone.com/iwXNyQ
language:
C++14 (gcc 8.3)
created:
6 years 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!