fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<cmath>
  4. using namespace std;
  5.  
  6. const int N = 2e5 + 8;
  7. int n, k, root;
  8. vector<int> g[N], group[N >> 1];
  9.  
  10. int h[N], up[N][18];
  11.  
  12. void dfs(int u) {
  13.     for (int v : g[u]) {
  14.         h[v] = h[u] + 1;
  15.  
  16.         for (int j = 1; j < 18; ++j)
  17.             up[v][j] = up[up[v][j - 1]][j - 1];
  18.  
  19.         dfs(v);
  20.     }
  21. }
  22.  
  23. int lca(int u, int v) {
  24.     if (h[u] != h[v]) {
  25.         if (h[u] < h[v]) swap(u, v);
  26.  
  27.         int k = h[u] - h[v];
  28.         for (int j = 0; (1 << j) <= k; ++j)
  29.             if (k >> j & 1)
  30.                 u = up[u][j];
  31.     }
  32.     if (u == v) return u;
  33.  
  34.     int k = __lg(h[u]);
  35.     for (int j = k; j >= 0; --j)
  36.         if (up[u][j] != up[v][j])
  37.             u = up[u][j], v = up[v][j];
  38.     return up[u][0];
  39. }
  40.  
  41. int dist(int u, int v) {
  42.     int p = lca(u, v);
  43.     return h[u] + h[v] - 2 * h[p];
  44. }
  45.  
  46. int diameter(vector<int> &meeting) {
  47.     int A = meeting[0], max_dist = 0, B = A, d;
  48.  
  49.     for (int x : meeting) {
  50.         d = dist(A, x);
  51.         if (max_dist < d) {
  52.             max_dist = d;
  53.             B = x;
  54.         }
  55.     }
  56.  
  57.     max_dist = 0;
  58.     for (int x : meeting) {
  59.         d = dist(B, x);
  60.         max_dist = max(max_dist, d);
  61.     }
  62.     return max_dist;
  63. }
  64.  
  65. int main() {
  66.     cin.tie(NULL)->sync_with_stdio(false);
  67.     cin >> n >> k;
  68.     for (int i = 1, x; i <= n; ++i) {
  69.         cin >> x >> up[i][0];
  70.         group[x].push_back(i);
  71.         g[up[i][0]].push_back(i);
  72.         if (up[i][0] == 0) root = i;
  73.     }
  74.  
  75.     dfs(root);
  76.  
  77.     for (int i = 1; i <= k; ++i)
  78.         cout << diameter(group[i]) << '\n';
  79. }
Success #stdin #stdout 0.01s 11124KB
comments (?)
stdin
copy 
6 2
1 3
2 1
1 0
2 1
2 1
1 5
stdout
copy 
3
2
https://ideone.com/9ywhfA
language:
C++14 (gcc 8.3)
created:
21 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!