fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. static const int N = 200005;
  5. vector<int> adj[N];
  6.  
  7. int arr[N], visited[N], root;
  8.  
  9. int dfs(int node)
  10. {
  11.     visited[node] = 1;
  12.     vector<int>v; v.push_back(0);
  13.  
  14.     for(auto x:adj[node])
  15.     {
  16.         if(visited[x]==0)
  17.         {
  18.             v.push_back(dfs(x));
  19.         }
  20.     }
  21.  
  22.     if(v.size()==1)
  23.     {
  24.      arr[node] = 0;
  25.      return 1;
  26.     }
  27.  
  28.     sort(v.rbegin(), v.rend());
  29.     arr[node] = v[0] + v[1];
  30.  
  31.     if(node==root) return arr[root]; 
  32.     return v[0]+1;
  33. }
  34.  
  35. int main() {
  36.  
  37. int n; cin >> n;
  38.  
  39. if(n==1) { cout<<0<<endl; return 0; }
  40.  
  41. for(int i=1; i<n; i++)
  42. {
  43.     int u,v; cin >> u >> v;
  44.     adj[u].push_back(v);
  45.     adj[v].push_back(u);
  46. }
  47.  
  48. root = 1;
  49. int ans = dfs(root);
  50.  
  51. for(int i=1; i<=n; i++) ans = max(ans,arr[i]); 
  52.  
  53. cout<<ans<<endl;
  54.  
  55. return 0;
  56. }
Success #stdin #stdout 0.01s 8288KB
comments (?)
stdin
copy 
5
1 2
1 3
3 4
3 5
stdout
copy 
3
https://ideone.com/8SriAN
language:
C++ (gcc 8.3)
created:
2 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!