fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define mod 1000000007
  3. #define DEBUG(x) cout << '>' << #x << ':' << x << endl;
  4. #define REP(i, n) for (int i = 0; i < (n); i++)
  5. #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
  6. #define FORD(i, a, b) for (int i = (a); i >= (b); i--)
  7. #define pb push_back
  8. #define eb emplace_back
  9. #define sv()         \
  10.     int t;           \
  11.     scanf("%d", &t); \
  12.     while (t--)
  13. inline bool EQ(double a, double b)
  14. {
  15.     return fabs(a - b) < 1e-9;
  16. }
  17. const int INF = 1 << 29;
  18. typedef long long ll;
  19. inline int two(int n)
  20. {
  21.     return 1 << n;
  22. }
  23. inline int test(int n, int b)
  24. {
  25.     return (n >> b) & 1;
  26. }
  27. inline void set_bit(int &n, int b)
  28. {
  29.     n |= two(b);
  30. }
  31. inline void unset_bit(int &n, int b)
  32. {
  33.     n &= ~two(b);
  34. }
  35. inline int last_bit(int n)
  36. {
  37.     return n & (-n);
  38. }
  39. inline int ones(int n)
  40. {
  41.     int res = 0;
  42.     while (n && ++res)
  43.         n -= n & (-n);
  44.     return res;
  45. }
  46. template <class T>
  47. void chmax(T &a, const T &b)
  48. {
  49.     a = max(a, b);
  50. }
  51. template <class T>
  52. void chmin(T &a, const T &b)
  53. {
  54.     a = min(a, b);
  55. }
  56. ll gcd(ll a, ll b)
  57. {
  58.     if (a == 0 || b == 0)
  59.         return 0;
  60.     if (a == b)
  61.         return a;
  62.     if (a > b)
  63.         return gcd(a - b, b);
  64.     return gcd(a, b - a);
  65. }
  66. ll lcm(ll a, ll b)
  67. {
  68.     return (a * b) / gcd(a, b);
  69. }
  70. ll max(ll a, ll b)
  71. {
  72.     if (a > b)
  73.         return a;
  74.     return b;
  75. }
  76. ll power(ll x, ll y)
  77. {
  78.     ll res = 1;
  79.     while (y > 0)
  80.     {
  81.         if (y & 1)
  82.             res = res * x;
  83.         y = y >> 1;
  84.         x = x * x;
  85.     }
  86.     return res;
  87. }
  88. ll powermod(ll x, ll y)
  89. {
  90.     ll res = 1;
  91.     x = x % mod;
  92.     while (y > 0)
  93.     {
  94.         if (y & 1)
  95.             res = (res * x) % mod;
  96.         y = y >> 1;
  97.         x = (x * x) % mod;
  98.     }
  99.     return res;
  100. }
  101. ll mulmod(ll a, ll b)
  102. {
  103.     ll res = 0;
  104.     a %= mod;
  105.     while (b)
  106.     {
  107.         if (b & 1)
  108.             res = (res + a) % mod;
  109.         a = (2 * a) % mod;
  110.         b >>= 1;
  111.     }
  112.     return res;
  113. }
  114. bool isPrime(ll n)
  115. {
  116.     if (n <= 1)
  117.         return false;
  118.     if (n <= 3)
  119.         return true;
  120.     if (n % 2 == 0 || n % 3 == 0)
  121.         return false;
  122.     for (int i = 5; i * i <= n; i += 6)
  123.     {
  124.         if ((n % i == 0) || (n % (i + 2) == 0))
  125.             return false;
  126.     }
  127.     return true;
  128. }
  129. long double dist(ll x1, ll y1, ll x2, ll y2)
  130. {
  131.     return (long double)sqrt((long double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
  132. }
  133. ll squaredist(ll x1, ll y1, ll x2, ll y2)
  134. {
  135.     return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  136. }
  137. ll nCr(ll n, ll r)
  138. {
  139.     if (r == 0)
  140.         return 1;
  141.     return (n * nCr(n - 1, r - 1)) / r;
  142. }
  143. ll countDivisors(ll n)
  144. {
  145.     ll cnt = 0;
  146.     for (int i = 1; i <= sqrt(n); i++)
  147.     {
  148.         if (n % i == 0)
  149.         {
  150.             if (n / i == i)
  151.                 cnt++;
  152.             else
  153.                 cnt = cnt + 2;
  154.         }
  155.     }
  156.     return cnt;
  157. }
  158. ll modulo(ll a, ll b)
  159. {
  160.     ll r = a % b;
  161.     return r < 0 ? r + b : r;
  162. }
  163. #define int long long
  164. using namespace std;
  165. class Graph
  166. {
  167.     int n;
  168.     vector<vector<int>> adj;
  169.  
  170. public:
  171.     vector<bool> used;
  172.     vector<int> d, p;
  173.     int mx;
  174.     Graph(int n);
  175.     void addEdge(int v, int w);
  176.     int BFS(int s);
  177.     void shortestPath(int u);
  178. };
  179.  
  180. Graph::Graph(int n)
  181. {
  182.     this->n = n;
  183.     adj.resize(n);
  184.     used.resize(n);
  185.     d.resize(n);
  186.     p.resize(n);
  187.     mx = INT_MIN;
  188.     for (int i = 0; i < n; i++)
  189.     {
  190.         adj[i].resize(n);
  191.     }
  192. }
  193.  
  194. void Graph::addEdge(int v, int w)
  195. {
  196.     adj[v].push_back(w);
  197.     adj[w].push_back(v);
  198. }
  199.  
  200. int Graph::BFS(int s)
  201. {
  202.     queue<int> q;
  203.     q.push(s);
  204.     used[s] = true;
  205.     p[s] = -1;
  206.     int farthest = s;
  207.     while (!q.empty())
  208.     {
  209.         int v = q.front();
  210.         q.pop();
  211.         for (int u : adj[v])
  212.         {
  213.             if (!used[u])
  214.             {
  215.                 used[u] = true;
  216.                 q.push(u);
  217.                 d[u] = d[v] + 1;
  218.                 farthest = u;
  219.                 p[u] = v;
  220.                 mx = d[u];
  221.             }
  222.         }
  223.     }
  224.     return farthest;
  225. }
  226.  
  227. int32_t main()
  228. {
  229.     ios_base::sync_with_stdio(0);
  230.     cin.tie(0);
  231.     cout.tie(0);
  232.     int t;
  233.     cin >> t;
  234.     while (t--)
  235.     {
  236.         int n;
  237.         cin >> n;
  238.         Graph g(n);
  239.         REP(i, n - 1)
  240.         {
  241.             int a, b;
  242.             cin >> a >> b;
  243.             g.addEdge(a, b);
  244.         }
  245.         int u = g.BFS(0);
  246.         REP(i, n)
  247.         {
  248.             g.used[i] = false;
  249.             g.p[i] = 0;
  250.             g.d[i] = 0;
  251.         }
  252.         int v = g.BFS(u);
  253.         // REP(i, n)
  254.         // {
  255.         //     mx = max(mx, g.d[i]);
  256.         // }
  257.         cout << (g.mx + 1) / 2 << "\n";
  258.     }
  259.     return 0;
  260. }
Runtime error #stdin #stdout #stderr 0s 80768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/xoFg2v
language:
C++14 (gcc 8.3)
created:
4 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!