fork download 
  1.  
  2. #include <bits/stdc++.h>
  3. #define ll long long int
  4. #define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. #define ff first
  6. #define ss second
  7. #define pb push_back
  8. #define po pop_back()
  9. #define lb lower_bound
  10. #define ub upper_bound
  11. #define nl "\n"
  12. #define dbg(x) cout << (#x) << " = " << (x) << nl
  13. #define fl(i,a,b,c) for(int i=a;i<b;i+=c)
  14. #define rl(i,a,b,c) for(int i=a;i>b;i-=c)
  15. #define sn(a,l) fl(i,0,l,1) cin >> a[i]
  16. #define pr(a,l) fl(i,0,l,1) cout << a[i] << ' '
  17. #define all(a) a.begin(),a.end()
  18. #define sz(a) (int)a.size()
  19. #define test() int ts; cin>>ts; while(ts--)
  20. const int INF = 1e9 + 1;
  21. const int MOD = 1e9 + 7;
  22. const int N = 1e5 + 5;
  23. const int K = 20;
  24. using namespace std;
  25.  
  26. // #include <ext/pb_ds/assoc_container.hpp> 
  27. // #include <ext/pb_ds/tree_policy.hpp> 
  28. // using namespace __gnu_pbds; 
  29.  
  30. // template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. // CODE BEGINS HERE --- 
  33.  
  34. int n, node, mx;
  35. vector<int> lst[N];
  36.  
  37. void reset()
  38. {
  39.     fl(i,0,n+1,1)
  40.         lst[i].clear();
  41. }
  42.  
  43. void dfs(int u, int p=0, int d=0)
  44. {
  45.     if(d > mx)
  46.     {
  47.         mx = d;
  48.         node = u;
  49.     }
  50.     for(auto v : lst[u])
  51.         if(v ^ p)
  52.             dfs(v, u, d+1);
  53. }
  54.  
  55. void solve()
  56. {
  57.     cin >> n;
  58.  
  59.     reset();
  60.  
  61.     fl(i,1,n,1)
  62.     {
  63.         int u, v;
  64.         cin >> u >> v;
  65.         lst[u].pb(v);
  66.         lst[v].pb(u);
  67.     }
  68.  
  69.     mx = 0;
  70.     dfs(1);
  71.  
  72.     mx = 0;
  73.     dfs(node);
  74.  
  75.     cout << (mx + 1)/2;
  76.  
  77.     cout << nl;
  78. }
  79.  
  80. int main()
  81. {
  82.     fastIO
  83.     test()
  84.     solve();
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0s 5996KB
comments (?)
stdin 
2
3
1 2
2 3
7
1 2
2 3
2 4
1 5
5 6
6 7
stdout 
1
3
https://ideone.com/Tk94Nm
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!