fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class SemiRing {
  6.   public:
  7.     SemiRing(int el=0):
  8.         el_(el)
  9.     { }
  10.  
  11.     SemiRing& operator +=(const SemiRing& rhs) {
  12.         if (el_ < rhs.el_) {
  13.             el_ = rhs.el_;
  14.         }
  15.         return *this;
  16.     }
  17.  
  18.     SemiRing& operator *=(const SemiRing& rhs) {
  19.         if (el_ == inf or rhs.el_ == inf) {
  20.             el_ = inf;
  21.         } else {
  22.             el_ += rhs.el_;
  23.         }
  24.         return *this;
  25.     }
  26.  
  27.     SemiRing operator +(const SemiRing& rhs) const { return SemiRing(*this) += rhs; }
  28.     SemiRing operator *(const SemiRing& rhs) const { return SemiRing(*this) *= rhs; }
  29.  
  30.     int value() const { return el_; }
  31.  
  32.     static SemiRing ONE() { return SemiRing(1); }
  33.     static SemiRing INF() { return SemiRing(inf); }
  34.  
  35.   private:
  36.     static constexpr int inf = -0x3f3f3f3f;
  37.     int el_;
  38. };
  39.  
  40. class Mat22 {
  41.   public:
  42.     Mat22(SemiRing x00=0, SemiRing x01=SemiRing::INF(),
  43.           SemiRing x10=SemiRing::INF(), SemiRing x11=0):
  44.         a00(x00),
  45.         a01(x01),
  46.         a10(x10),
  47.         a11(x11)
  48.    { }
  49.  
  50.     Mat22 operator *=(const Mat22& rhs) {
  51.         return *this = *this * rhs;
  52.     }
  53.  
  54.     Mat22 operator *(const Mat22& rhs) const {
  55.         return Mat22(
  56.             a00 * rhs.a00 + a01 * rhs.a10,
  57.             a00 * rhs.a01 + a01 * rhs.a11,
  58.             a10 * rhs.a00 + a11 * rhs.a10,
  59.             a10 * rhs.a01 + a11 * rhs.a11
  60.         );
  61.     }
  62.  
  63.     int Get00() const { return a00.value(); }
  64.     int Get01() const { return a01.value(); }
  65.     int Get10() const { return a10.value(); }
  66.     int Get11() const { return a11.value(); }
  67.  
  68.   private:
  69.     SemiRing a00, a01, a10, a11;
  70. };
  71.  
  72. class LCTree {
  73.   public:
  74.     LCTree(int n=0):
  75.         parent(n + 1),
  76.         path_parent(n + 1),
  77.         first(n + 1),
  78.         last(n + 1),
  79.         value(n + 1),
  80.         cvalue(n + 1),
  81.         child(n + 1),
  82.         light_dp(n + 1),
  83.         num_nodes(0)
  84.     { }
  85.  
  86.     void AddPoint(const int parent) {
  87.         if (parent != 0) {
  88.             Access(parent);
  89.             Splay(parent, 0);
  90.             light_dp[parent].first *= SemiRing::ONE();
  91.             value[parent] = LightMatrix(parent);
  92.             Update(parent);
  93.         }
  94.  
  95.         ++num_nodes;
  96.         path_parent[num_nodes] = parent;
  97.         value[num_nodes] = HeavyMatrix(num_nodes);
  98.         Update(num_nodes); Access(num_nodes); Splay(num_nodes,0);
  99.     }
  100.  
  101.     int Query() {
  102.         Access(1);
  103.         return num_nodes - HeavyMatrix(1).Get01();
  104.     }
  105.  
  106.   protected:
  107.     Mat22 HeavyMatrix(const int node) const {
  108.         return Mat22(SemiRing::INF(),
  109.                      light_dp[node].first + light_dp[node].second * SemiRing::ONE(),
  110.                      SemiRing::INF(),
  111.                      light_dp[node].first);
  112.     }
  113.  
  114.     Mat22 LightMatrix(const int node) const {
  115.         return Mat22(light_dp[node].first,
  116.                      light_dp[node].second * SemiRing::ONE(),
  117.                      light_dp[node].first,
  118.                      SemiRing::INF());
  119.     }
  120.  
  121.   private:
  122.     bool IsRightSon(const int node) const {
  123.         return child[parent[node]][1] == node;
  124.     }
  125.  
  126.     void Update(const int node) {
  127.         if (child[node][0]) {
  128.             first[node] = first[child[node][0]];
  129.             cvalue[node] = cvalue[child[node][0]] * value[node];
  130.         } else {
  131.             first[node] = node;
  132.             cvalue[node] = value[node];
  133.         }
  134.  
  135.         if (child[node][1] != 0) {
  136.             last[node] = last[child[node][1]];
  137.             cvalue[node] = cvalue[node] * cvalue[child[node][1]];
  138.         } else {
  139.             last[node] = node;
  140.         }
  141.     }
  142.  
  143.     void Rotate(const int node) {
  144.         const int par = parent[node];
  145.         const bool where = IsRightSon(node);
  146.  
  147.         if (parent[par] != 0) {
  148.             child[parent[par]][IsRightSon(par)] = node;
  149.         }
  150.         if (child[node][where ^ 1] != 0) {
  151.             parent[child[node][where ^ 1]] = par;
  152.         }
  153.  
  154.         child[par][where] = child[node][where ^ 1];
  155.         child[node][where ^ 1] = par;
  156.  
  157.         parent[node] = parent[par];
  158.         parent[par] = node;
  159.  
  160.         if (path_parent[par] != 0) {
  161.             path_parent[node] = path_parent[par];
  162.             path_parent[par] = 0;
  163.         }
  164.  
  165.         Update(par);
  166.     }
  167.  
  168.     void Splay(int from, const int to) {
  169.         while (parent[from] != to) {
  170.             if (parent[parent[from]] != to) {
  171.                 Rotate(IsRightSon(from) != IsRightSon(parent[from]) ? from : parent[from]);
  172.             }
  173.  
  174.             Rotate(from);
  175.         }
  176.         Update(from);
  177.     }
  178.  
  179.     template <bool is_heavy>
  180.     int Get(const int node, int to) {
  181.         int foo;
  182.         to = first[to]; Splay(to, is_heavy ? 0 : node);
  183.         foo = last[to]; Splay(foo, is_heavy ? 0 : node);
  184.  
  185.         auto r = cvalue[child[foo][0]] * HeavyMatrix(foo);
  186.  
  187.         light_dp[node].first  *= is_heavy ? -r.Get01() : r.Get01();
  188.         light_dp[node].second *= is_heavy ? -r.Get11() : r.Get11();
  189.  
  190.         value[node] = LightMatrix(node);
  191.  
  192.         Splay(to, is_heavy ? 0 : node);
  193.         Update(node);
  194.         return to;
  195.     }
  196.  
  197.     int Access(int node) {
  198.         int to = 0;
  199.         while (node != 0) {
  200.             Splay(node, 0);
  201.             if (child[node][1] != 0) {
  202.                 Get<false>(node, child[node][1]);
  203.                 parent[child[node][1]] = 0;
  204.                 path_parent[child[node][1]] = node;
  205.             }
  206.             if (to != 0) {
  207.                 to = Get<true>(node, to);
  208.                 parent[to] = node;
  209.                 path_parent[to] = 0;
  210.             }
  211.  
  212.             child[node][1] = to;
  213.             Update(node);
  214.             to = node;
  215.             node = path_parent[node];
  216.         }
  217.         return to;
  218.     }
  219.  
  220.     vector<int> parent, path_parent;
  221.     vector<int> first, last;
  222.     vector<Mat22> value, cvalue;
  223.     vector<array<int, 2>> child;
  224.     vector<pair<SemiRing, SemiRing>> light_dp;
  225.     int num_nodes;
  226. };
  227.  
  228. int BoatSize(int num_nodes, int mvc) {
  229.     if (num_nodes <= 3) {
  230.         return 2;
  231.     }
  232.     if (mvc == 1) {
  233.         return 3;
  234.     }
  235.  
  236.     return 1 + mvc;
  237. }
  238.  
  239. int main() {
  240.     cin.tie(0);
  241.     ios_base::sync_with_stdio(false);
  242.  
  243.     int num_tests; cin >> num_tests;
  244.     assert(1 <= num_tests && num_tests <= 200000);
  245.     int sum_n = 0;
  246.     while (num_tests--> 0) {
  247.         int n; cin >> n;
  248.         assert(2 <= n);
  249.         sum_n += n;
  250.         LCTree tree(n); tree.AddPoint(0);
  251.         for (int i = 2; i <= n; ++i) {
  252.             int parent; cin >> parent;
  253.             assert(1 <= parent && parent <= i);
  254.             tree.AddPoint(parent);
  255.             cout << BoatSize(i, tree.Query()) << " \n"[i == n];
  256.         }
  257.     }
  258.     assert(sum_n <= 1000000);
  259.     return 0;
  260. }
Success #stdin #stdout 0s 4292KB
comments (?)
stdin
copy 
2
7
1 1 2 2 3 5
16
1 1 2 2 3 3 4 4 5 6 6 6 1 11 11
stdout
copy 
2 2 3 3 3 4
2 2 3 3 3 3 4 4 5 6 6 6 6 7 7
https://ideone.com/5UDCn3
language:
C++14 (gcc 8.3)
created:
5 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!