fork download
  1. using namespace std;
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <set>
  7. #include <cctype>
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <algorithm>
  12. #include <stack>
  13. #include <cctype>
  14. #include <cstring>
  15. #include <string>
  16.  
  17. #define MAX 10100
  18. #define PRIME 31
  19. #define MOD 1000000007
  20. #define PI 3.1415926535897932384
  21. #define F first
  22. #define S second
  23. #define pb push_back
  24. #define mp make_pair
  25. #define pii pair<int, int>
  26. typedef long long ll;
  27.  
  28. vector<int> adj[MAX];
  29. int maxi, dia_end, n;
  30.  
  31. void dfs(int ind, int prev, int cont){
  32.  
  33. if(cont > maxi){
  34. maxi = cont;
  35. dia_end = ind; // Possible end of tree's diameter
  36. }
  37.  
  38. for(int i = 0;i < adj[ind].size();i++){
  39. if(adj[ind][i] == prev) continue;
  40. dfs(adj[ind][i], ind, cont+1);
  41. }
  42. }
  43.  
  44. int main(){
  45. ios::sync_with_stdio(false);
  46. //freopen("in.txt", "r", stdin);
  47.  
  48. while(cin >> n && n != -1){
  49.  
  50. // Initialize
  51. for(int i = 1;i <= n;i++) adj[i] = vector<int>();
  52. maxi = 0;
  53.  
  54. for(int x, i = 2;i <= n;i++){
  55. cin >> x;
  56. adj[x].pb(i);
  57. adj[i].pb(x);
  58. }
  59.  
  60. // Find one end of the tree's diameter
  61. dfs(1, -1, 1);
  62. // Find the total length of the tree's diameter
  63. dfs(dia_end, -1, 1);
  64.  
  65. // Time needed is total length/2
  66. cout << maxi/2 << endl;
  67. }
  68.  
  69. return 0;
  70. }
  71.  
Success #stdin #stdout 0s 3528KB
stdin
Standard input is empty
stdout
Standard output is empty