Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include<iostream>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <cassert>
- #include <unordered_map>
- #include <unordered_set>
- #include<math.h>
- using namespace std;
- typedef unsigned int ui;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- #define endl "\n"
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- #define pb push_back
- #define pikachu push_back
- #define F first
- #define S second
- ll inf = 1e18;
- ld eps = 1e-18;
- const ll maxn = 2e5 + 10;
- const ll LG = 20;
- ll lg[maxn];
- ll h[maxn], tout[maxn], tin[maxn];
- ll n, m;
- vector<ll> g[maxn];
- ll t = 0;
- vector<ll> tr;
- ll sp[LG][2 * maxn][2];
- void dfs(ll a, ll ls) {
- if (tin[a] == -1) {
- tin[a] = t;
- }
- tr.pb(a);
- t++;
- if (ls != -1)
- h[a] = h[ls] + 1;
- for (ll &x : g[a]) {
- if (x != ls) {
- dfs(x, a);
- tr.pb(a);
- t++;
- }
- }
- tout[a] = t;
- }
- ll lca(ll a, ll b) {
- if (tin[a] > tin[b])
- swap(a, b);
- ll d = (tin[b] - tin[a] + 1);
- ll kek = lg[d];
- if (sp[kek][tin[a]][0] < sp[kek][tin[b] - (1 << kek) + 1][0]) {
- return sp[kek][tin[a]][1];
- }
- return sp[kek][tin[b] - (1 << kek) + 1][1];
- }
- void solve() {
- for (ll i = 0; i < maxn; i++) {
- tin[i] = -1;
- }
- for (ll i = 2; i < maxn;i++) {
- lg[i] = lg[i / 2] + 1;
- }
- cin >> n >> m;
- for (ll i = 1; i < n;i++) {
- ll a;
- cin >> a;
- g[i].pb(a);
- g[a].pb(i);
- }
- dfs(0, -1);
- ll sz = t;
- for (ll i = 0; i < sz;i++) {
- sp[0][i][0] = h[tr[i]];
- sp[0][i][1] = tr[i];
- }
- for (ll i = sz; i < 2 * maxn;i++) sp[0][i][0] = 1e9;
- for (ll i = 1; i < LG;i++) {
- for (ll j = 0; j + (1 << i) <= sz; j++) {
- if (sp[i - 1][j][0] < sp[i - 1][j + (1 << (i - 1))][0]) {
- sp[i][j][0] = sp[i - 1][j][0];
- sp[i][j][1] = sp[i - 1][j][1];
- }
- else {
- sp[i][j][0] = sp[i - 1][j + (1 << (i - 1))][0];
- sp[i][j][1] = sp[i - 1][j + (1 << (i - 1))][1];
- }
- }
- }
- ll a, b;
- cin >> a >> b;
- ll x, y, z;
- ll ans = 0;
- cin >> x >> y >> z;
- ll sum = 0;
- while (m--) {
- ll a1 = (a + ans) % n;
- ll a2 = b;
- ans = lca(a1, a2);
- sum += ans;
- a = (x * a + b * y + z) % n;
- b = (x * b + a * y + z) % n;
- }
- cout << sum << endl;
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- ll t = 1;
- //cin >> t;
- //cout << fixed << setprecision(18);
- while (t--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement