Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define D 100007
- #define lg 25
- using namespace std;
- typedef long long ll;
- vector <ll> a[D];
- ll tin[D], tout[D], dp[D][lg + 1], za[2*D], timer, x, y, z, n, m;
- void dfs();
- void questions();
- ll lca();
- bool upper();
- bool upper(ll parent, ll v)
- {
- return (tin[parent] <= tin[v] && tout[v] <= tout[parent]);
- }
- void dfs(ll v, ll parent)
- {
- tin[v] = ++timer;
- dp[v][0] = parent;
- ll i, nn = a[v].size();
- for (i = 1; i < lg; i++)
- dp[v][i] = dp[dp[v][i - 1]][i - 1];
- for (i = 0; i < nn; i++)
- if (a[v][i] != parent)
- dfs(a[v][i], v);
- tout[v] = ++timer;
- }
- ll lca(ll a1, ll a2)
- {
- if (upper(a1, a2))
- return a1;
- if (upper(a2, a1))
- return a2;
- for (ll i = lg - 1; i >= 0; i--)
- if (!upper(dp[a1][i], a2))
- a1 = dp[a1][i];
- return dp[a1][0];
- }
- void questions()
- {
- ll i;
- for (i = 3; i <= m + 3; i++)
- za[i] = (x*za[i - 2] + y*za[i - 1] + z) % n;
- ll res = 0;
- ll v = lca(za[1], za[2]);
- res += v;
- for (ll i = 2; i <= m; i++)
- {
- ll p1 = (za[2*i-1] + v) % n, p2 = za[2*i];
- v = lca(p1, p2);
- res += v;
- }
- cout << res << endl;
- }
- int main()
- {
- ll i, v;
- cin >> n >> m;
- for (i = 0; i < n - 1; i++)
- {
- cin >> v;
- a[i].push_back(v);
- a[v].push_back(i);
- }
- cin >> za[1] >> za[2] >> x >> y >> z;
- dfs(0, 0);
- questions();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement