Advertisement
Dimaush

Untitled

Dec 16th, 2022
728
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.94 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4.  
  5. unsigned BitWidth(unsigned n) {
  6.     unsigned p = 0;
  7.     while (n > 0) {
  8.         n >>= 1;
  9.         ++p;
  10.     }
  11.     return p;
  12. }
  13.  
  14. class TRootTree {
  15. private:
  16.     unsigned number;
  17.     std::vector<unsigned> parent;
  18.     std::vector<std::vector<unsigned>> children;
  19.     unsigned requests;
  20.     unsigned long long a_odd, a_even;
  21.     unsigned x, y, z;
  22.  
  23.     std::vector<std::pair<unsigned, unsigned>> time;
  24.     unsigned timer;
  25.     unsigned width;
  26.     std::vector<std::vector<unsigned>> up;
  27.  
  28.     TRootTree(unsigned n, unsigned m) : number(n), parent(number),
  29.             children(number), requests(m),
  30.             a_odd(0), a_even(0), x(0), y(0), z(0),
  31.             time(number), timer(0), width(BitWidth(number)),
  32.             up(number, std::vector<unsigned>(width + 1, 0)) {}
  33.  
  34.     void ReadFromStream(std::istream& stream) {
  35.         for (auto iter = parent.begin() + 1; iter != parent.end(); ++iter) {
  36.             stream >> *iter;
  37.         }
  38.         stream >> a_odd >> a_even >> x >> y >> z;
  39.     }
  40.  
  41.     void DFS(unsigned v, unsigned p = 0) {
  42.         time[v].first = ++timer;
  43.         {
  44.             unsigned curr;
  45.             curr = up[v][0] = p;
  46.             for (unsigned i = 1; i <= width; ++i) {
  47.                 curr = up[v][i] = up[curr][i - 1];
  48.             }
  49.         }
  50.         for (unsigned to: children[v]) {
  51.             if (to != p) {
  52.                 DFS(to, v);
  53.             }
  54.         }
  55.         time[v].second = ++timer;
  56.     }
  57.  
  58.     void Preprocessing() {
  59.         for (unsigned i = 1; i < number; ++i) {
  60.             children[parent[i]].push_back(i);
  61.         }
  62.         DFS(0);
  63.     }
  64.  
  65.     bool IsAncestor(unsigned v1, unsigned v2) {
  66.         return time[v1].first <= time[v2].first && time[v1].second >= time[v2].second;
  67.     }
  68.  
  69.     unsigned LCA(unsigned v1, unsigned v2) {
  70.         if (IsAncestor(v1, v2)) {
  71.             return v1;
  72.         } else if (IsAncestor(v2, v1)) {
  73.             return v2;
  74.         } else {
  75.             for (int i = width; i >= 0; --i) {
  76.                 if (!IsAncestor(up[v1][i], v2)) {
  77.                     v1 = up[v1][i];
  78.                 }
  79.             }
  80.             return up[v1][0];
  81.         }
  82.     }
  83.  
  84. public:
  85.     unsigned Respond() {
  86.         unsigned ans = LCA(a_odd, a_even);
  87.         unsigned long long sum = ans;
  88.         for (unsigned i = 1; i < requests; ++i) {
  89.             a_odd = (x * a_odd + y * a_even + z) % number;
  90.             a_even = (x * a_even + y * a_odd + z) % number;
  91.             ans = LCA((a_odd + ans) % number, a_even);
  92.             sum += ans;
  93.         }
  94.         return sum;
  95.     }
  96.  
  97.     friend TRootTree create(std::istream&);
  98. };
  99.  
  100. TRootTree create(std::istream& stream) {
  101.     unsigned n, m;
  102.     stream >> n >> m;
  103.     TRootTree t(n, m);
  104.     t.ReadFromStream(stream);
  105.     t.Preprocessing();
  106.     return t;
  107. }
  108.  
  109. int main() {
  110.     TRootTree a = create(std::cin);
  111.     std::cout << a.Respond() << std::endl;
  112.     return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement