Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int INF = 2'100'000'000;
- void
- count_heights(int now, vector<std::vector<int>> &m_adj, vector<bool> &visited,
- vector<int> &heights, vector<int> &ancestors) {
- visited[now] = true;
- if (now == 0) {
- heights[now] = 0;
- } else {
- heights[now] = heights[ancestors[now]] + 1;
- }
- for (auto neig : m_adj[now]) {
- if (!visited[neig]) {
- count_heights(neig, m_adj, visited, heights, ancestors);
- }
- }
- }
- void balance_h(int &v_first, int &v_second, const vector<int> &heights, const vector<int> &ancestors) {
- if (heights[v_first] == heights[v_second]) {
- return;
- }
- if (heights[v_first] > heights[v_second]) {
- while (heights[v_first] != heights[v_second]) {
- v_first = ancestors[v_first];
- }
- } else {
- balance_h(v_second, v_first, heights, ancestors);
- }
- }
- int LCA(int v_first, int v_second,
- vector<vector<int>> &up,
- const vector<int> &ancestors,vector<int>&heights) {
- balance_h(v_first, v_second,heights,ancestors);
- if (v_first == v_second) {
- return v_first;
- }
- int k = up.size() - 1;
- while (k >= 0) {
- if (up[k][v_first] != up[k][v_second]) {
- v_first = up[k][v_first];
- v_second = up[k][v_second];
- }
- --k;
- }
- if (v_first == v_second) {
- return v_first;
- }
- return ancestors[v_first];
- }
- int main() {
- int N, M;
- cin >> N >> M;
- vector<int> arr(N);
- vector<int> ancestors(N, -1);
- ancestors[0] = -1;
- vector<vector<int>> m_adj;
- m_adj.resize(N);
- vector<bool> visited(N, false);
- for (int i = 1; i < N; ++i) {
- cin >> arr[i];
- ancestors[i] = arr[i];
- m_adj[arr[i]].push_back(i);
- m_adj[i].push_back(arr[i]);
- }
- vector<int> heights(N);
- count_heights(0, m_adj, visited, heights, ancestors);
- int max_degree = 0;
- while (pow(2, max_degree + 1) < N) {
- ++max_degree;
- }
- vector<vector<int>> up(max_degree + 1, vector<int>(N, 0));
- up[0][0] = -1;
- for (int el = 1; el < N; ++el) {
- up[0][el] = ancestors[el];
- }
- for (int i = 1; i <= max_degree; ++i) {
- for (int el = 1; el < N; ++el) {
- if (up[i - 1][el] == -1) {
- up[i][el] = -1;
- } else {
- up[i][el] = up[i - 1][up[i - 1][el]];
- }
- }
- }
- int a_first, a_second;
- cin >> a_first >> a_second;
- int x, y, z;
- cin >> x >> y >> z;
- int sum_ = 0;
- int a_third = a_first;
- int a_fouth = a_second;
- // balance_h(a_third, a_fouth, heights, ancestors);
- int last_ans = LCA(a_third, a_fouth, up, ancestors,heights);
- sum_ += last_ans;
- for (int i = 2; i <= M; ++i) {
- a_first = (x * a_third + y * a_fouth + z) % N;
- a_second = (x * a_fouth + y * a_first + z) % N;
- a_third = a_first;
- a_fouth = a_second;
- // balance_h(query_first, query_second, heights, ancestors);
- last_ans = LCA((a_first + last_ans) % N, a_second, up, ancestors,heights);
- sum_ += last_ans;
- }
- cout << sum_;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement