Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- #define mp make_pair
- #define pb push_back
- #define eb emplace_back
- #define sz(x) (int)x.size()
- #define all(x) begin(x), end(x)
- #define rall(x) rbegin(x), rend(x)
- #define FOR(i,a,b) for (int i = (a); i < (b); i++)
- #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- typedef vector<int> veci;
- typedef vector<bool> vecb;
- typedef vector<vector<int>> vvi;
- typedef vector<vector<bool>> vvb;
- const int INF_I = 1e9;
- const ll INF_LL = 1e18;
- int n, m, l, timer = 0;
- vector<list<int>> g;
- veci tin, tout;
- vvi up;
- void dfs(int v, int p){
- tin[v] = timer++;
- up[v][0] = p;
- for (int i = 1; i <= l; i++)
- up[v][i] = up[up[v][i-1]][i-1];
- for (int i : g[v])
- dfs(i, v);
- tout[v] = timer++;
- }
- bool check(int v, int p){
- return (tin[p] <= tin[v] && tout[v] <= tout[p]);
- }
- int lca(int a, int b){
- if (check(a, b)) return b;
- if (check(b, a)) return a;
- for (int i = l; i>= 0; i--)
- if (!check(a, up[b][i]))
- b = up[b][i];
- return up[b][0];
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cin >> n >> m;
- l = ceil(log((double)n) / log(2));
- g.assign(n, list<int>());
- tin.assign(n, 0);
- tout.assign(n, 0);
- up.assign(n, veci(l + 1));
- for (int i = 1; i < n; i++){
- int p;
- cin >> p;
- g[p].eb(i);
- }
- veci a(2*m + 1);
- ll x, y, z;
- cin >> a[1] >> a[2] >> x >> y >> z;
- for (int i = 3; i <= 2*m; i++)
- a[i] = (x * a[i-2] + y * a[i-1] + z) % (ll)n;
- dfs(0, 0);
- ll v = lca(a[1], a[2]);
- ll res = v;
- for (int i = 2; i <= m; i++)
- res += (v = lca(((ll)a[2*i-1] + v) % (ll)n, a[2*i]));
- cout << res << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement