Advertisement
ivnikkk

Untitled

Dec 24th, 2021
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.97 KB | None | 0 0
  1. #include <vector>
  2. #include<iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <fstream>
  7. #include <string>
  8. #include <set>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <bitset>
  13. #include <random>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include<math.h>
  18. using namespace std;
  19. typedef unsigned int ui;
  20. typedef long long             ll;
  21. typedef unsigned long long     ull;
  22. typedef long double            ld;
  23. #define endl              "\n"
  24. #define all(a)            a.begin(), a.end()
  25. #define allr(a)           a.rbegin(), a.rend()
  26. #define pb                push_back
  27. #define pikachu           push_back
  28. #define F                 first
  29. #define S                 second
  30. ll inf = 1e18;
  31. ld eps = 1e-18;
  32. const ll maxn = 2e5 + 10;
  33. const ll LG = 20;
  34. ll lg[maxn];
  35. ll h[maxn], tout[maxn], tin[maxn];
  36. ll n, m;
  37. vector<ll> g[maxn];
  38. ll t = 0;
  39. vector<ll> tr;
  40. ll sp[LG][2 * maxn][2];
  41. void dfs(ll a, ll ls) {
  42.     if (tin[a] == -1) {
  43.         tin[a] = t;
  44.     }
  45.     tr.pb(a);
  46.     t++;
  47.     if (ls != -1)
  48.         h[a] = h[ls] + 1;
  49.     for (ll &x : g[a]) {
  50.         if (x != ls) {
  51.             dfs(x, a);
  52.             tr.pb(a);
  53.             t++;
  54.         }
  55.     }
  56.     tout[a] = t;
  57. }
  58.  
  59. ll lca(ll a, ll b) {
  60.     if (tin[a] > tin[b])
  61.         swap(a, b);
  62.     ll d = (tin[b] - tin[a] + 1);
  63.     ll kek = lg[d];
  64.     if (sp[kek][tin[a]][0] < sp[kek][tin[b] - (1 << kek) + 1][0]) {
  65.         return sp[kek][tin[a]][1];
  66.     }
  67.     return sp[kek][tin[b] - (1 << kek) + 1][1];
  68. }
  69.  
  70. void solve() {
  71.     for (ll i = 0; i < maxn; i++) {
  72.         tin[i] = -1;
  73.     }
  74.     for (ll i = 2; i < maxn;i++) {
  75.         lg[i] = lg[i / 2] + 1;
  76.     }
  77.     cin >> n >> m;
  78.     for (ll i = 1; i < n;i++) {
  79.         ll a;
  80.         cin >> a;
  81.         g[i].pb(a);
  82.         g[a].pb(i);
  83.     }
  84.     dfs(0, -1);
  85.     ll sz = t;
  86.     for (ll i = 0; i < sz;i++) {
  87.         sp[0][i][0] = h[tr[i]];
  88.         sp[0][i][1] = tr[i];
  89.     }
  90.     for (ll i = sz; i < 2 * maxn;i++) sp[0][i][0] = 1e9;
  91.     for (ll i = 1; i < LG;i++) {
  92.         for (ll j = 0; j + (1 << i) <= sz; j++) {
  93.             if (sp[i - 1][j][0] < sp[i - 1][j + (1 << (i - 1))][0]) {
  94.                 sp[i][j][0] = sp[i - 1][j][0];
  95.                 sp[i][j][1] = sp[i - 1][j][1];
  96.             }
  97.             else {
  98.                 sp[i][j][0] = sp[i - 1][j + (1 << (i - 1))][0];
  99.                 sp[i][j][1] = sp[i - 1][j + (1 << (i - 1))][1];
  100.             }
  101.         }
  102.     }
  103.     ll a, b;
  104.     cin >> a >> b;
  105.     ll x, y, z;
  106.     ll ans = 0;
  107.     cin >> x >> y >> z;
  108.     ll sum = 0;
  109.     while (m--) {
  110.         ll a1 = (a + ans) % n;
  111.         ll a2 = b;
  112.         ans = lca(a1, a2);
  113.         sum += ans;
  114.         a = (x * a + b * y + z) % n;
  115.         b = (x * b + a * y + z) % n;
  116.     }
  117.     cout << sum << endl;
  118. }
  119.  
  120. signed main() {
  121.     ios_base::sync_with_stdio(false);
  122.     cin.tie(nullptr);
  123.     ll t = 1;
  124.     //cin >> t;
  125.     //cout << fixed << setprecision(18);
  126.     while (t--) {
  127.         solve();
  128.     }
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement