Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <set>
- #include <map>
- #include <deque>
- #include <list>
- #include <iterator>
- #include <functional>
- #include <sstream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cctype>
- #include <cmath>
- #include <climits>
- #include <ctime>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair<double, double> pii;
- typedef pair<ll, ll> pll;
- typedef pair<ld, ld> pld;
- typedef pair<short, short> pss;
- #define fi first
- #define se second
- #define mp make_pair
- #define pb push_back
- /////// begin
- const int MAXN = 200 * 1000;
- vector <int> g[MAXN];
- int tin[MAXN], tout[MAXN], pr[20][MAXN];
- bool was[MAXN];
- int t = 0;
- void dfs(int v, int _pr){
- if (was[v]) return;
- was[v] = 1;
- tin[v] = t++;
- pr[0][v] = _pr;
- for (int u: g[v])
- dfs(u, v);
- tout[v] = t++;
- }
- bool is_pr(int v, int u){
- return (tin[v] >= tin[u] && tout[v] <= tout[u]);
- }
- int get_lca(int u, int v){
- if (is_pr(u, v)) return v;
- for (int i = 19; i >= 0; i--){
- if (!is_pr(u, pr[i][v]))
- v = pr[i][v];
- }
- return pr[0][v];
- }
- int main() {
- #ifdef HOME
- assert(freopen("input.txt", "r", stdin));
- assert(freopen("output.txt", "w", stdout));
- #else
- //freopen(FILE ".in", "r", stdin);
- //freopen(FILE ".out", "w", stdout);
- #endif
- //ios_base::sync_with_stdio(false);
- //cin.tie(0);
- int n, m;
- cin >> n >> m;
- for (int i = 1; i < n; i ++){
- int a;
- cin >> a;
- g[a].pb(i);
- g[i].pb(a);
- }
- memset(was, 0, sizeof was);
- dfs(0, 0);
- for (int i = 1; i < 20; i++)
- for (int j = 0; j < n; j++){
- pr[i][j] = pr[i - 1][pr[i - 1][j]];
- }
- int a1, a2;
- ll x, y, z;
- int la = 0;
- ll ans = 0;
- cin >> a1 >> a2 >> x >> y >> z;
- for (int i = 0; i < m; i++){
- //cout << (a1 + la) % n << " " << a2 << endl;
- la = get_lca((a1 + la) % n, a2) ;
- ans += la;
- a1 = (int)((a1 * x + a2 * y + z) % n);
- a2 = (int)((a2 * x + a1 * y + z) % n);
- }
- cout << ans << endl;
- return 0;
- }
- // end
Advertisement
Add Comment
Please, Sign In to add comment