Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("O3")
- #pragma GCC optimize("unroll-loops")
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <cmath>
- //#include <ext/pb_ds/assoc_container.hpp>
- //include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- //using namespace __gnu_pbds;
- typedef long long ll;
- typedef long double ld;
- #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
- #define all(x) (x).begin(),(x).end()
- #define pii pair<int, int>
- #define sz(x) (int)x.size()
- vector<vector<int>> v;
- vector<int> order, first, h, tree;
- vector<bool> used;
- void dfs(int i, int _h) {
- used[i] = 1;
- h[i] = _h;
- order.push_back(i);
- for (int x : v[i]) {
- if (!used[x]) {
- dfs(x, _h + 1);
- order.push_back(i);
- }
- }
- }
- void build(int v, int tl, int tr) {
- if (tr - tl == 1) {
- tree[v] = order[tl];
- }
- else {
- int tm = (tl + tr) / 2;
- build(2 * v + 1, tl, tm);
- build(2 * v + 2, tm, tr);
- if (h[tree[2 * v + 1]] < h[tree[2 * v + 2]]) {
- tree[v] = tree[2 * v + 1];
- }
- else {
- tree[v] = tree[2 * v + 2];
- }
- }
- }
- int get(int v, int tl, int tr, int l, int r) {
- if (tl >= l && tr <= r) {
- return tree[v];
- }
- int tm = (tl + tr) / 2;
- if (r <= tm) {
- return get(2 * v + 1, tl, tm, l, r);
- }
- else if (l >= tm) {
- return get(2 * v + 2, tm, tr, l, r);
- }
- else {
- int ans1 = get(2 * v + 1, tl, tm, l, tm);
- int ans2 = get(2 * v + 2, tm, tr, tm, r);
- return (h[ans1] < h[ans2] ? ans1 : ans2);
- }
- }
- int lca(int a, int b) {
- int left = first[a], right = first[b];
- if (left > right) swap(left, right);
- return get(0, 0, sz(order), left, right + 1);
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int n, m;
- cin >> n >> m;
- v.resize(n);
- first.resize(n, -1);
- h.resize(n);
- used.resize(n, 0);
- for (int i = 1; i <= n - 1; ++i) {
- int x; cin >> x;
- v[i].push_back(x);
- v[x].push_back(i);
- }
- dfs(0, 0);
- tree.resize(8 * sz(order));
- build(0, 0, sz(order));
- for (int i = 0; i < sz(order); ++i) {
- if (first[order[i]] == -1) {
- first[order[i]] = i;
- }
- }
- long long x, y, z;
- vector<int> a(2 * m + 4);
- cin >> a[1] >> a[2] >> x >> y >> z;
- long long ans = 0;
- int v;
- for (int i = 1; i <= 2 * m - 1; i += 2) {
- if (i == 1) {
- //cout << a[i] << " " << a[i + 1] << " " << lca(a[i], a[i + 1]) << "\n";
- v = lca(a[i], a[i + 1]);
- }
- else {
- //cout << (a[i] + v) % n << " " << a[i + 1] << " " << lca((a[i] + v) % n, a[i + 1]) << "\n";
- v = lca((a[i] + v) % n, a[i + 1]);
- }
- ans += v;
- a[i + 2] = (int)((x * (long long)(a[i]) + y * (long long)(a[i + 1]) + z) % (long long)(n));
- a[i + 3] = (int)((x * (long long)(a[i + 1]) + y * (long long)(a[i + 2]) + z) % (long long)(n));
- }
- cout << ans;
- return 0;
- }
- /*
- 7 8
- 0 1 1 1 0 5
- 6 3
- 1 1 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement