Advertisement
Guest User

111796

a guest
Feb 22nd, 2020
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. #define mp make_pair
  5. #define pb push_back
  6. #define eb emplace_back
  7. #define sz(x) (int)x.size()
  8. #define all(x) begin(x), end(x)
  9. #define rall(x) rbegin(x), rend(x)
  10. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  11. #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
  12.  
  13. using namespace std;
  14.  
  15. typedef unsigned long long ull;
  16. typedef long long ll;
  17. typedef long double ld;
  18. typedef pair<int, int> pi;
  19. typedef pair<ll, ll> pl;
  20. typedef vector<int> veci;
  21. typedef vector<bool> vecb;
  22. typedef vector<vector<int>> vvi;
  23. typedef vector<vector<bool>> vvb;
  24.  
  25. const int INF_I = 1e9;
  26. const ll INF_LL = 1e18;
  27.  
  28. int n, m, l, timer = 0;
  29. vector<list<int>> g;
  30. veci tin, tout;
  31. vvi up;
  32.  
  33. void dfs(int v, int p){
  34.     tin[v] = timer++;
  35.     up[v][0] = p;
  36.     for (int i = 1; i <= l; i++)
  37.         up[v][i] = up[up[v][i-1]][i-1];
  38.     for (int i : g[v])
  39.         dfs(i, v);
  40.     tout[v] = timer++;
  41. }
  42.  
  43. bool check(int v, int p){
  44.     return (tin[p] <= tin[v] && tout[v] <= tout[p]);
  45. }
  46.  
  47. int lca(int a, int b){
  48.     if (check(a, b)) return b;
  49.     if (check(b, a)) return a;
  50.     for (int i = l; i>= 0; i--)
  51.         if (!check(a, up[b][i]))
  52.             b = up[b][i];
  53.     return up[b][0];
  54. }
  55.  
  56. int main() {
  57.  
  58.     ios::sync_with_stdio(false);
  59.     cin.tie(nullptr);
  60.     cout.tie(nullptr);
  61.  
  62.     cin >> n >> m;
  63.     l = ceil(log((double)n) / log(2));
  64.  
  65.     g.assign(n, list<int>());
  66.     tin.assign(n, 0);
  67.     tout.assign(n, 0);
  68.     up.assign(n, veci(l + 1));
  69.  
  70.     for (int i = 1; i < n; i++){
  71.         int p;
  72.         cin >> p;
  73.         g[p].eb(i);
  74.     }
  75.  
  76.     veci a(2*m + 1);
  77.     ll x, y, z;
  78.     cin >> a[1] >> a[2] >> x >> y >> z;
  79.     for (int i = 3; i <= 2*m; i++)
  80.         a[i] = (x * a[i-2] + y * a[i-1] + z) % (ll)n;
  81.     dfs(0, 0);
  82.     ll v = lca(a[1], a[2]);
  83.     ll res = v;
  84.     for (int i = 2; i <= m; i++)
  85.         res += (v = lca(((ll)a[2*i-1] + v) % (ll)n, a[2*i]));
  86.  
  87.     cout << res << "\n";
  88.  
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement