Language: C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

/* Задано дерево с корнем, содержащее (1 ≤ n ≤ 100 000) вершин, пронумерованных от 0 до n-1.
 * Требуется ответить на m (1 ≤ m ≤ 10 000 000) запросов о наименьшем общем предке для пары вершин.
 * Запросы генерируются следующим образом. Заданы числа a1, a2 и числа x, y и z.
 * Числа a3, ..., a2m генерируются следующим образом: ai = (x ⋅ ai-2 + y ⋅ ai-1 + z) mod n.
 * Первый запрос имеет вид (a1, a2). Если ответ на i-1-й запрос равен v, то i-й запрос имеет вид ((a2i-1 + v) mod n, a2i).
 * Для решения задачи можно использовать метод двоичного подъёма.
 */

using namespace std;

// Ячейка в дереве отрезков
class Node {
private:
    unsigned long long left, right;
    unsigned long long value;
    // [left, right) - отрезок, за который "отвечает" данная вершина
    // значение на отрезке
    const unsigned long long INF = 1e9 + 7;

public:
    Node() {
        left = 0;
        right = 0;
        value = INF;
    }

    unsigned long long get_left() {
        return left;
    }

    unsigned long long get_right() {
        return right;
    }

    unsigned long long get_value() {
        return value;
    }

    unsigned long long set_left(unsigned long long _left) {
        left = _left;
    }

    unsigned long long set_right(unsigned long long _right) {
        right = _right;
    }

    unsigned long long set_value(unsigned long long _value) {
        value = _value;
    }

    unsigned long long get_INF() {
        return INF;
    }
};

class MyGraph {
private:
    vector<unsigned long long> order;
    vector<unsigned long long> high, first;
    vector<vector<unsigned long long> > gr;
    unsigned long long n, root = 0, m;

public:
    MyGraph() {}

    vector<unsigned long long>& adjacent(unsigned long long v) {
        return gr[v];
    }

    void dfs(unsigned long long v, unsigned long long h) {
        order.push_back(v);
        first[v] = order.size() - 1;
        for (unsigned long long u : adjacent(v)) {
//            cout << v << " " << u << endl;
            if (high[u] == 0) {
                dfs(u, h + 1);
                order.push_back(v);
                high[u] = h + 1;
            }
        }
    }

    unsigned long long get_root() {
        return root;
    }

    vector<unsigned long long>& get_order() {
        return order;
    }

    unsigned long long get_queries_num() {
        return m;
    }

    unsigned long long get_high(unsigned long long v) {
        return high[v];
    }

    unsigned long long get_first(unsigned long long v) {
        return first[v];
    }

    unsigned long long get_order_size() {
        return order.size();
    }

    unsigned long long get_size() {
        return n;
    }

    friend istream& operator >>(istream&, MyGraph&);
};

istream& operator >>(istream& in, MyGraph& g){
    in >> g.n;
    g.high.resize(g.n, 0);
    g.first.resize(g.n);
    g.gr.resize(g.n, vector<unsigned long long>());

    for (int i = 0; i < g.n; i++) {
        unsigned long long k;
        in >> k;
        for (int j = 0; j < k; j++) {
            int c;
            in >> c;
            g.gr[i].push_back(c);
        }
    }

    in >> g.m;
}

class SegmentTree{
private:
    vector<Node> tree; // дерево
    unsigned long long len, n;
    const unsigned long long INF = 1e9 + 7;
    unsigned long long ans = 0;

public:
    SegmentTree() {};

    unsigned long long find_min(MyGraph& g, unsigned long long x, unsigned long long y) {
        if (g.get_high(x) < g.get_high(y))
            return x;
        else
            return y;
    }

    // Находит индексы вершин, отвечающих за отрезки, входящие в запрос
    unsigned long long find_ans(unsigned long long ind, unsigned long long ll, unsigned long long rr, MyGraph& g) {
//        cout << ind << endl;

        // Если индекс выходит за пределы дерева
        if (ind >= len * 2)
            return INF;

        // Если вершина с данным индексом не отвечает за реальные данные
        if (tree[ind].get_value() == tree[ind].get_INF())
            return INF;

        // Если вершина "отвечает" за отрезок, не входящий в запрос
        if ((tree[ind].get_left() >= rr) || (tree[ind].get_right() <= ll))
            return INF;

//        cout << ind << " " << tree[ind].get_left() << " " << tree[ind].get_right() << endl;
//        cout << "  " << ll << " " << rr << endl;

        // Если вершина отвечает за отрезок, полностью лежащий в запросе
        if ((tree[ind].get_left() >= ll) && (tree[ind].get_right() <= rr)) {
//            cout << "value " << tree[ind].get_value() << endl;
            return tree[ind].get_value();
        }

        unsigned long long x = find_ans(ind * 2, ll, rr, g);
//        cout << x << endl;
        unsigned long long y = find_ans(ind * 2 + 1, ll, rr, g);
//        cout << y << endl;

        if (y == INF)
            return x;
        if (x == INF)
            return y;

        return find_min(g, x, y);
    }

    // Выполняет запросы
    void queries(MyGraph& g) {
//        unsigned long long a1, a2, x, y, z;
//        cin >> a1 >> a2 >> x >> y >> z;
        unsigned long long a1, a2;

        for (int i = 0; i < g.get_queries_num(); i++) {
            cin >> a1 >> a2
//            cout << "---query " << i + 1 << "---\n";
            unsigned long long left = g.get_first(a1), right = g.get_first(a2);
            if (right < left)
                swap(left, right);
//            cout << left << " " << r
// << endl;
            unsigned long long v = find_ans(1, left, right + 1, g);
//            a1 = (x * a1 + y * a2 + z) % n;
//            a2 = (x * a2 + y * a1 + z) % n;
//            a1 = (a1 + v) % n;
            ans += v;
            cout << v << endl;
        }
    }

    void build_tree(MyGraph& g) {
        n = g.get_size();
        unsigned long long len_log = (unsigned long long) trunc(log2((double) g.get_order_size())) + 1;
        len = (1 << len_log);
        tree.resize(len * 2);

        vector<unsigned long long>& order1 = g.get_order();
        for (int i = 0; i < len; ++i) {
            if (i < g.get_order_size())
                tree[i + len].set_value(order1[i]);
            else
                tree[i + len].set_value(INF);
            tree[len + i].set_left(i);
            tree[len + i].set_right(i + 1);
        }

        for (int i = len - 1; i > 0; --i) {
            unsigned long long ind1 = 2 * i, ind2 = 2 * i + 1;
            tree[i].set_left(tree[ind1].get_left());
            tree[i].set_right(tree[ind2].get_right());
            if (tree[ind2].get_value() == INF)
                tree[i].set_value(tree[ind1].get_value());
            else
                tree[i].set_value(find_min(g, tree[ind1].get_value(), tree[ind2].get_value()));
        }

//        for (int i = 1; i < tree.size(); i++)
//            cout << tree[i].get_value() << " ";
//        cout << endl;
    }

    friend ostream& operator <<(ostream&, SegmentTree&);
};

ostream& operator <<(ostream& out, SegmentTree& t) {
    out << t.ans << endl;
}

int main() {
    MyGraph graph;
    cin >> graph;
//    cout << "--dfs--" << endl;
    graph.dfs(graph.get_root(), 0);
//    cout << graph.get_size() << endl;
//    for (int i = 0; i < graph.get_size(); i++)
//        cout << graph.get_high(i) << " ";
//    cout << endl;
    SegmentTree st;
//    cout << "keka\n";
    st.build_tree(graph);
//    cout << "peka\n";
    st.queries(graph);
//    cout << st;
    return 0;
}



Compiler output:
a.cc: In member function 'long long unsigned int Node::set_left(long long unsigned int)':
a.cc:46:5: warning: no return statement in function returning non-void [-Wreturn-type]
   46 |     }
      |     ^
a.cc: In member function 'long long unsigned int Node::set_right(long long unsigned int)':
a.cc:50:5: warning: no return statement in function returning non-void [-Wreturn-type]
   50 |     }
      |     ^
a.cc: In member function 'long long unsigned int Node::set_value(long long unsigned int)':
a.cc:54:5: warning: no return statement in function returning non-void [-Wreturn-type]
   54 |     }
      |     ^
a.cc: In function 'std::istream& operator>>(std::istream&, MyGraph&)':
a.cc:136:1: warning: no return statement in function returning non-void [-Wreturn-type]
  136 | }
      | ^
a.cc: In member function 'void SegmentTree::queries(MyGraph&)':
a.cc:202:13: error: expected ';' before 'unsigned'
  202 |             unsigned long long left = g.get_first(a1), right = g.get_first(a2);
      |             ^~~~~~~~
a.cc:204:21: error: no matching function for call to 'swap(std::ios_base& (&)(std::ios_base&), std::ios_base& (&)(std::ios_base&))'
  204 |                 swap(left, right);
      |                 ~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/14/exception:166,
                 from /usr/include/c++/14/ios:41,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/exception_ptr.h:229:5: note: candidate: 'void std::__exception_ptr::swap(exception_ptr&, exception_ptr&)'
  229 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |     ^~~~
/usr/include/c++/14/bits/exception_ptr.h:229:25: note:   no known conversion for argument 1 from 'std::ios_base&(std::ios_base&)' to 'std::__exception_ptr::exception_ptr&'
  229 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |          ~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/14/bits/exception_ptr.h:41:
/usr/include/c++/14/bits/move.h:226:5: note: candidate: 'template<class _Tp> std::_Require<std::__not_<std::__is_tuple_like<_Tp> >, std::is_move_constructible<_Tp>, std::is_move_assignable<_Tp> > std::swap(_Tp&, _Tp&)'
  226 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
/usr/include/c++/14/bits/move.h:226:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/14/bits/move.h:37:
/usr/include/c++/14/type_traits: In substitution of 'template<bool _Cond, class _Tp> using std::__enable_if_t = typename std::enable_if::type [with bool _Cond = false; _Tp = void]':
/usr/include/c++/14/type_traits:2323:11:   required by substitution of 'template<class ... _Cond> using std::_Require = std::__enable_if_t<((bool)std::__and_<_Bn>::value)> [with _Cond = {std::__not_<std::__is_tuple_like<std::ios_base&(std::ios_base&)> >, std::is_move_constructible<std::ios_base&(std::ios_base&)>, std::is_move_assignable<std::ios_base&(std::ios_base&)>}]'
 2323 |     using _Require = __enable_if_t<__and_<_Cond...>::value>;
      |           ^~~~~~~~
/usr/include/c++/14/bits/move.h:226:5:   required by substitution of 'template<class _Tp> std::_Require<std::__not_<std::__is_tuple_like<_Tp> >, std::is_move_constructible<_Tp>, std::is_move_assignable<_Tp> > std::swap(_Tp&, _Tp&) [with _Tp = std::ios_base&(std::ios_base&)]'
  226 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
a.cc:204:21:   required from here
  204 |                 swap(left, right);
      |                 ~~~~^~~~~~~~~~~~~
/usr/include/c++/14/type_traits:138:11: error: no type named 'type' in 'struct std::enable_if<false, void>'
  138 |     using __enable_if_t = typename enable_if<_Cond, _Tp>::type;
      |           ^~~~~~~~~~~~~
/usr/include/c++/14/bits/move.h:250:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> std::__enable_if_t<((bool)std::__is_swappable<_Tp>::value)> std::swap(_Tp (&)[_Nm], _Tp (&)[_Nm])'
  250 |     swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
      |     ^~~~
/usr/include/c++/14/bits/move.h:250:5: note:   template argument deduction/substitution failed:
a.cc:204:21: note:   mismatched types '_Tp [_Nm]' and 'std::ios_base&(std::ios_base&)'
  204 |                 swap(left, right);
      |                 ~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44:
/usr/include/c++/14/bits/stl_pair.h:1089:5: note: candidate: 'template<class _T1, class _T2> typename std::enable_if<std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value>::type std::swap(pair<_T1, _T2>&, pair<_T1, _T2>&)'
 1089 |     swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
      |     ^~~~
/usr/include/c++/14/bits/stl_pair.h:1089:5: note:   template argument deduction/substitution failed:
a.cc:204:21: note:   mismatched types 'std::pair<_T1, _T2>' and 'std::ios_base&(std::ios_base&)'
  204 |                 swap(left, right);
      |                 ~~~~^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1106:5: note: candidate: 'template<class _T1, class _T2> typename std::enable_if<(! std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value)>::type std::swap(pair<_T1, _T2>&, pair<_T1, _T2>&)' (deleted)
 1106 |     swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
      |     ^~~~
/usr/include/c++/14/bits/stl_pair.h:1106:5: note:   template argument deduction/substitution failed:
a.cc:204:21: note:   mismatched types 'std::pair<_T1, _T2>' and 'std::ios_base&(std::ios_base&)'
  204 |                 swap(left, right);
      |                 ~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:54:
/usr/include/c++/14/bits/basic_string.h:4039:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> void std::swap(__cxx11::basic_string<_CharT, _Traits, _Allocator>&, __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 4039 |     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~
/usr/include/c++/14/bits/basic_string.h:4039:5: note:   template argument deduction/substitution failed:
a.cc:204:21: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'std::ios_base&(std::ios_base&)'
  204 |                 swap(left, right);
      |                 ~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/memory_resource.h:47,
                 from /usr/include/c++/14/string:68:
/usr/include/c++/14/tuple:2805:5: note: candidate: 'template<class ... _Elements> typename std::enable_if<std::__and_<std::__is_swappable<_Elements>...>::value>::type std::swap(tuple<_UTypes ...>&, tuple<_UTypes ...>&)'
 2805 |     swap(tuple<_Elements...>& __x, tuple<_Elements...>& __y)
      |     ^~~~
/usr/include/c++/14/tuple:2805:5: note:   template argument deduction/substitution failed:
a.cc:204:21: note:   mismatched types 'std::tuple<_UTypes ...>' and 'std::ios_base&(std::ios_base&)'
  204 |                 swap(left, right);
      |                 ~~~~^~~~~~~~~~~~~
/usr/include/c++/14/tuple:2823:5: note: candidate: 'template<class ... _Elements> typename std::enable_if<(! std::__and_<std::__is_swappable<_Elements>...>::value)>::type std::swap(tuple<_UTypes ...>&, tuple<_UTypes ...>&)' (deleted)
 2823 |     swap(tuple<_Elements...>&, tuple<_Elements...>&) = delete;
      |     ^~~~
/usr/include/c++/14/tuple:2823:5: note:   template argument deduction/substitution failed:
a.cc:204:21: note:   mismatched types 'std::tuple<_UTypes ...>' and 'std::ios_base&(std::ios_base&)'
  204 |                 swap(left, right);
      |                 ~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/14/vector:66,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_vector.h:2122:5: note: candidate: 'template<class _Tp, class _Alloc> void std::swap(vector<_Tp, _Alloc>&, vector<_Tp, _Alloc>&)'
 2122 |     swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
      |     ^~~~
/usr/include/c++/14/bits/stl_vector.h:2122:5: note:   template argument deduction/substitution failed:
a.cc:204:21: note:   mismatched types 'std::vector<_Tp, _Alloc>' and 'std::ios_base&(std::ios_base&)'
  204 |                 swap(left, right);
      |                 ~~~~^~~~~~~~~~~~~
a.cc:207:60: warning: pointer to a function used in arithmetic [-Wpointer-arith]
  207 |             unsigned long long v = find_ans(1, left, right + 1, g);
      |                                                      ~~~~~~^~~
a.cc:207:48: error: invalid conversion from 'std::ios_base& (*)(std::ios_base&)' to 'long long unsigned int' [-fpermissive]
  207 |             unsigned long long v = find_ans(1, left, right + 1, g);
      |                                                ^~~~
      |                                                |
      |                                                std::ios_base& (*)(std::ios_base&)
a.cc:156:76: note:   initializing argument 2 of 'long long unsigned int SegmentTree::find_ans(long long unsigned int, long long unsigned int, long long unsigned int, MyGraph&)'
  156 |     unsigned long long find_ans(unsigned long long ind, unsigned long long ll, unsigned long long rr, MyGraph& g) {
      |                                                         ~~~~~~~~~~~~~~~~~~~^~
a.cc:207:60: error: invalid conversion from 'std::ios_base& (*)(std::ios_base&)' to 'long long unsigned int' [-fpermissive]
  207 |             unsigned long long v = find_ans(1, left, right + 1, g);
      |                                                      ~~~~~~^~~
      |                                                            |
      |                                                            std::ios_base& (*)(std::ios_base&)
a.cc:156:99: note:   initializing argument 3 of 'long long unsigned int SegmentTree::find_ans(long long unsigned int, long long unsigned int, long long unsigned int, MyGraph&)'
  156 |     unsigned long long find_ans(unsigned long long ind, unsigned long long ll, unsigned long long rr, MyGraph& g) {
      |