Advertisement
ke_timofeeva7

LCA

Dec 24th, 2021
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.50 KB | None | 0 0
  1. /*
  2. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⠤⠲⠦⠉⠉⠉⠏⠉⠒⢄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  3. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡠⠲⠃⢀⣤⠀⠀⠀⠲⠂⠀⠠⠆⠀⠙⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  4. ⠀⠀⠀⠀⠀⠀⠀⠀⢀⡔⠁⣤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  5. ⠀⠀⠀⠀⠀⠀⠀⢀⠊⠁⠀⢁⡴⠚⠉⣉⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠠⠤⠔⠒⡄⠀⠀⠀⠀⠀⠀
  6. ⠀⠀⠀⠀⠀⠀⠀⡆⢰⠆⠀⠋⣠⠔⠉⠁⣀⡠⠄⠒⠂⠀⠀⠀⠀⠀⠀⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠔⠊⠁⠀⠀⠀⠀⠀⣠⡴⠀⠀⠀⠀⠀⠀⠀
  7. ⠀⠀⠀⠀⠀⠀⢠⡆⠀⠀⠀⡜⠁⣠⠔⠋⢁⡔⠒⠒⠤⡀⠀⠀⠀⠀⡐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠎⠀⠀⠀⢀⣀⣤⣶⡾⠋⠀⠀⠀⠀⠀⠀⠀⠀
  8. ⠀⠀⠀⠀⠀⠀⠀⡆⡶⠀⠀⢀⡜⠁⢀⣀⢸⠀⠀⠀⠀⠈⢆⠀⠀⡜⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠤⠊⠁⠀⢀⡀⣴⡿⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  9. ⠀⠀⠀⠀⠀⠀⠀⠰⡀⠀⠀⠘⠀⡞⠁⠀⠉⢇⠀⣿⣄⠀⠈⡆⠀⠕⠒⠉⣉⡒⡄⠀⠀⠀⠀⢀⠤⠊⠁⢀⡠⠔⠊⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  10. ⠀⠀⠀⠀⠀⠀⠀⠀⠑⢄⡀⠀⠀⢇⠀⣤⡄⠈⢢⡈⠻⡖⢀⡞⣀⠔⠊⠁⠀⠀⠉⠐⠒⠠⢎⢁⡠⠔⠂⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  11. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⢂⠘⢿⣦⡇⠉⠓⢶⡫⠞⠁⣀⣤⣤⣤⣤⣤⣤⣤⠴⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  12. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢡⠦⠭⡇⠀⡠⠊⠀⣠⣮⣬⣿⣿⣿⣿⣿⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  13. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠁⢀⠔⡧⠊⠀⢀⡜⠁⠙⣿⣿⣿⡿⠟⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  14. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣀⣡⠎⠀⠀⢠⠊⠀⠀⠀⣸⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  15. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠃⠀⠀⣰⣧⣀⣀⡠⣴⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  16. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⣤⣤⣾⡿⠿⠋⠁⠀⢹⣿⣿⣿⣿⣿⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  17. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  18. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  19. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⠿⠛⠛⠛⠛⠻⢿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  20. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡸⠀⠀⠀⠀⠀⠀⠀⡸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  21. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠁⡰⢤⣀⣀⡄⢠⠞⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  22. */
  23.  
  24. #include <iostream>
  25. #include <string>
  26. #include <sstream>
  27. #include <cmath>
  28. #include <memory.h>
  29. #include <algorithm>
  30. #include <stack>
  31. #include <deque>
  32. #include <iomanip>
  33. #include <stdio.h>
  34. #include <queue>
  35. #include <map>
  36. #include <set>
  37. #include <unordered_map>
  38. #include <unordered_set>
  39. #include <random>
  40. #include <ctime>
  41. #include <cstdlib>
  42. #define int long long
  43. #define pii pair <int, int>
  44. #define pb push_back
  45. #define all(vc) vc.begin(), vc.end()
  46. #define fir first
  47. #define sec second
  48. #define endl "\n"
  49. #define un unsigned
  50. #define INF 1000000009
  51. #define double long double
  52. using namespace std;
  53.  
  54. const int N = 100009, R = 1 << 20, MOD = 1e9 + 7, ABC = 26;
  55.  
  56. int logn = 0;
  57. int cur = 0;
  58.  
  59. void dfs(vector<vector<int>> &jump, vector<vector<int>> &gr, vector<int>& up_time, vector<int>& time_in, int v, int p)
  60. {
  61.     time_in[v] = cur;
  62.     cur++;
  63.  
  64.     jump[v][0] = p;
  65.  
  66.     for (int i = 1; i < logn; i++)
  67.     {
  68.         jump[v][i] = jump[jump[v][i - 1]][i - 1];
  69.     }
  70.  
  71.     for (auto u : gr[v])
  72.     {
  73.         if (u != p)
  74.         {
  75.             dfs(jump, gr, up_time, time_in, u, v);
  76.         }
  77.     }    
  78.  
  79.     up_time[v] = cur;
  80.     cur++;
  81.     return;
  82. }
  83.  
  84. bool check(vector<int>& time_in, vector<int>& up_time, int a, int b)
  85. {
  86.     if (time_in[a] <= time_in[b] && up_time[b] <= up_time[a])
  87.     {
  88.         return true;
  89.     }
  90.     else
  91.     {
  92.         return false;
  93.     }
  94. }
  95.  
  96. int lca(vector<vector<int>>& jump, vector<int>& time_in, vector<int>& up_time, int a, int b)
  97. {
  98.     if (check(time_in, up_time, a, b))
  99.     {
  100.         return a;
  101.     }
  102.  
  103.     if (check(time_in, up_time, b, a))
  104.     {
  105.         return b;
  106.     }
  107.  
  108.     for (int i = logn - 1; i >= 0; i--)
  109.     {
  110.         if (!check(time_in, up_time, jump[a][i], b))
  111.         {
  112.             a = jump[a][i];
  113.         }
  114.     }
  115.  
  116.     return jump[a][0];
  117. }
  118.  
  119. signed main()
  120. {
  121.     ios_base::sync_with_stdio(false);
  122.     cin.tie(0);
  123.     cout.tie(0);
  124.     srand(time(0));
  125.  
  126.     int n, m;
  127.     cin >> n >> m;
  128.  
  129.     vector<int> pr(n);
  130.     vector<vector<int>> vc(n);
  131.  
  132.     for (int i = 1; i < n; i++)
  133.     {
  134.         cin >> pr[i];
  135.         vc[pr[i]].push_back(i);
  136.     }
  137.  
  138.     while ((1 << logn) <= n)
  139.     {
  140.         logn++;
  141.     }
  142.  
  143.     vector<int> up_time(n), time_in(n);
  144.     vector<vector<int>> jump(n, vector<int>(logn));
  145.  
  146.     dfs(jump, vc, up_time, time_in, 0, 0);
  147.    
  148.     vector<int> a(2 * m + 1);
  149.  
  150.     cin >> a[1] >> a[2];
  151.  
  152.     int x, y, z;
  153.     cin >> x >> y >> z;
  154.  
  155.     int anss = 0;  
  156.  
  157.     for (int i = 3; i <= 2 * m; i++)
  158.     {
  159.         a[i] = (x * a[i - 2] + y * a[i - 1] + z) % n;
  160.     }
  161.  
  162.     int aa = a[1], b = a[2];
  163.  
  164.     for (int i = 2; i <= m + 1; i++)
  165.     {
  166.         int ans = lca(jump, time_in, up_time, aa, b);
  167.  
  168.         //cout << aa << " " << b << " " << ans << endl;
  169.  
  170.         anss += ans;
  171.  
  172.         if (i != m + 1)
  173.         {
  174.             aa = (a[2 * i - 1] + ans) % n;
  175.             b = a[2 * i];
  176.         }
  177.     }
  178.  
  179.     cout << anss;
  180.     return 0;
  181. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement