fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 2e5 + 5;
  5. //
  6. int N, K;
  7. int root, h[mx], up[20][mx];
  8. vector<int> adj[mx], meeting[mx];
  9. //
  10. void DFS (int u = root)
  11. {
  12.     for (int v : adj[u])
  13.     {
  14.         if (v == up[0][u])
  15.             continue;
  16.         h[v] = h[u] + 1;
  17.         up[0][v] = u;
  18.         for (int i = 1; i < 20; ++i)
  19.             up[i][v] = up[i - 1][up[i - 1][v]];
  20.         DFS(v);
  21.     }
  22. }
  23. int dist (int u, int v)
  24. {
  25.     int res = 0;
  26.     //
  27.     if (h[u] != h[v])
  28.     {
  29.         if (h[u] < h[v])
  30.             swap(u, v);
  31.         res = h[u] - h[v];
  32.         for (int i = 0; (1 << i) <= res; ++i)
  33.             if (res >> i & 1)
  34.                 u = up[i][u];
  35.     }
  36.     if (u == v)
  37.         return res;
  38.     for (int i = __lg(h[v]); i >= 0; --i)
  39.         if (up[i][u] != up[i][v])
  40.             res += 2 << i,
  41.             u = up[i][u],
  42.             v = up[i][v];
  43.     return res + 2;
  44. }
  45. int solve (int idx)
  46. {
  47.     int u, tmp, res = 0;
  48.     //
  49.     u = meeting[idx].front();
  50.     for (int v : meeting[idx])
  51.         if (res < dist(u, v))
  52.             res = dist(u, v),
  53.             tmp = v;
  54.     u = tmp;
  55.     for (int v : meeting[idx])
  56.         if (res < dist(u, v))
  57.             res = dist(u, v);
  58.     return res;
  59. }
  60. //
  61. void process (void)
  62. {
  63.     cin >> N >> K;
  64.     for (int i = 1; i <= N; ++i)
  65.     {
  66.         int x, y;
  67.         //
  68.         cin >> x >> y;
  69.         meeting[x].emplace_back(i);
  70.         if (y == 0)
  71.             root = i;
  72.         else
  73.             adj[i].emplace_back(y),
  74.             adj[y].emplace_back(i);
  75.     }
  76.     DFS();
  77.     for (int i = 1; i <= K; ++i)
  78.         cout << solve(i) << '\n';
  79. }
  80. //
  81. signed main (void)
  82. {
  83.     ios_base::sync_with_stdio(false);
  84.     cin.tie(nullptr), cout.tie(nullptr);
  85.     process();
  86. }
  87.  
Success #stdin #stdout 0.01s 14388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/S1mFyN
https://o...content-available-to-author-only...i.info/problem/fselect
language:
C++14 (gcc 8.3)
created:
4 hours 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!