Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define endl "\n"
- #define ll long long
- constexpr int N = 1e5+1, L = 18;
- vector<int> dp[N], g[N];
- int tin[N], tout[N], a[2*N], t=0;
- void dfs(int v, int p = 0)
- {
- tin[v]=++t;
- dp[v][0] = p;
- for (int i = 1; i < L; i++)
- {
- dp[v][i] = dp[dp[v][i-1]][i-1];
- }
- for(auto u:g[v])
- {
- if (u!=p)
- dfs(u, v);
- }
- tout[v]=++t;
- }
- bool upper(int a, int b)
- {
- return (tin[a]<=tin[b]&&tout[a]>=tout[b]);
- }
- int lca(int a, int b)
- {
- if (upper(a, b)) return a;
- if (upper(b, a)) return b;
- for (int i = L-1; i >= 0; i--)
- {
- if(!upper(dp[a][i], b))
- a = dp[a][i];
- }
- return dp[a][0];
- }
- void change_root(int r)
- {
- }
- void Solve()
- {
- ll n, m, x, y, z, ans = 0, la = 0;
- cin >> n >> m;
- for (int i = 1; i < n; i++)
- {
- int par;
- cin >> par;
- g[par].push_back(i);
- }
- cin >> a[0] >> a[1] >> x >> y >> z;
- for (int i = 2; i < 2*m; i++)
- {
- a[i] = (x*a[i-2]+y*a[i-1]+z)%n;
- }
- dfs(0);
- for(int i = 1; i < 2*m; i+=2)
- {
- la = lca((a[i-1]+la)%n, a[i]);
- ans+=la;
- }
- cout << ans;
- return;
- }
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
- Solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement