fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.   ios::sync_with_stdio(false);
  7.   cin.tie(nullptr);
  8.   int m;
  9.   cin >> m;
  10.   const int N = 2 * m + 100;
  11.   const int h = 32 - __builtin_clz(N);
  12.   vector<vector<int>> pr(N, vector<int>(h));
  13.   vector<int> depth(N);
  14.   auto add = [&](int p, int x) { // p 为 x 的父节点
  15.     depth[x] = depth[p] + 1;
  16.     pr[x][0] = p;
  17.     for (int j = 0; j < h; j++) {
  18.       if (pr[x][j] == -1) {
  19.         pr[x][j + 1] = -1;
  20.       } else {
  21.         pr[x][j + 1] = pr[pr[x][j]][j];
  22.       }
  23.     }
  24.   };
  25.   auto lca = [&](int x, int y) {
  26.     if (depth[x] < depth[y]) {
  27.       swap(x, y);
  28.     }
  29.     int d = depth[x] - depth[y];
  30.     for (int j = 0; j < h; j++) {
  31.       if ((d >> j) & 1) {
  32.         x = pr[x][j];
  33.       }
  34.     }
  35.     if (x == y) {
  36.       return x;
  37.     }
  38.     for (int j = h - 1; j >= 0; j--) {
  39.       if (pr[x][j] != -1 && pr[x][j] != pr[y][j]) {
  40.         x = pr[x][j];
  41.         y = pr[y][j];
  42.       }
  43.     }
  44.     return pr[x][0];
  45.   };
  46.   int diam = 2;
  47.   int dx = 1, dy = 2;
  48.   add(0, 1); add(0, 2); add(0, 3);
  49.   auto update = [&](int x, int y) {
  50.     int z = lca(x, y);
  51.     int dist = depth[x] + depth[y] - 2 * depth[z];
  52.     if (dist > diam) {
  53.       diam = dist;
  54.       dx = x;
  55.       dy = y;
  56.     }
  57.   };
  58.   for (int i = 0, n = 4; i < m; i++, n += 2) {
  59.     int x;
  60.     cin >> x;
  61.     x--;
  62.     add(x, n); add(x, n + 1);
  63.     update(dx, n); update(dy, n); // 把新插入的节点和原来的直径起点终点组合一下
  64.     cout << diam << '\n';
  65.   }
  66.   cerr << "Time: " << double(clock()) / CLOCKS_PER_SEC << '\n';
  67.   return 0;
  68. }
  69.  
Success #stdin #stdout #stderr 0s 4196KB
comments (?)
stdin 
5
2
3
4
8
5
stdout 
3
4
4
5
6
stderr 
Time: 0.002882
https://ideone.com/ZXjeD3
language:
C++14 (gcc 8.3)
created:
6 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!