Language: C++

#include <algorithm>
#include <assert.h>
#include <cstdlib>
#include <vector>
??
template <typename T>
struct RMQ {
????using Index = int;
????using BitIndex = int;
??
????const std::vector<T>& A;
????const int N, S, L, LG_L;
??
????std::vector<int> lg;
????BitIndex* const small;
????Index* const large;
??
????bool f(Index a, Index b) const {
????????if (A[a] != A[b]) return A[a] < A[b];
????????return a < b;
????}
????RMQ(const std::vector<T>& A) : RMQ(A, A.size()) {}
????Index query(Index l, Index r) const {
????????const int a = l / S, b = r / S;
????????if (a == b) return query_small(l, r);
??
????????Index ans = F(query_small(l, a * S + (S - 1)), query_small(b * S, r));
????????if (a + 1 <= b - 1) ans = F(ans, query_large(a + 1, b - 1));
????????return ans;
????}
????~RMQ() {
????????std::free(small);
????????std::free(large);
????}
private:
????inline Index F(Index a, Index b) const { return f(a, b) ? a : b; }
??
????RMQ(const std::vector<T>& A, int N) : RMQ(A, N, std::__lg(N) + 1) {}
????RMQ(const std::vector<T>& A, int N, int S) : RMQ(A, N, S, (N + S - 1) / S) {}
????RMQ(const std::vector<T>& A, int N, int S, int L) : RMQ(A, N, S, L, std::__lg(L) + 1) {}
????RMQ(const std::vector<T>& A, int N, int S, int L, int LG_L)
????????????: A(A), N(N), S(S), L(L), LG_L(LG_L), lg(1 << S), small((BitIndex*)std::malloc(N * sizeof(BitIndex))), large((Index*)std::malloc(L * LG_L * sizeof(Index))) {
????????assert(small != nullptr);
????????assert(large != nullptr);
????????for (int i = 1, sz = lg.size(); i < sz; i++) {
????????????lg[i] = std::__lg(i);
????????}
????????for (int li = 0; li < L; li++) {
????????????int i = li * S;
????????????large[li * LG_L + 0] = i;
????????????for (int si = 0; si < S && i + si < N; si++) {
????????????????large[li * LG_L + 0] = F(large[li * LG_L + 0], i + si);
????????????}
????????}
????????for (int x = 0; x < LG_L - 1; x++) {
????????????for (int li = 0; li + (1 << x) < L; li++) {
????????????????large[li * LG_L + x + 1] = F(large[li * LG_L + x], large[(li + (1 << x)) * LG_L + x]);
????????????}
????????}
????????Index st[32];
????????for (int li = 0; li < L; li++) {
????????????int i = li * S;
????????????int sti = 0;
????????????for (int si = 0; si < S && i + si < N; si++) {
????????????????while (sti > 0 && f(i + si, st[sti - 1])) --sti;
????????????????small[i + si] |= 1 << si;
????????????????if (sti > 0) small[i + si] |= small[st[sti - 1]];
????????????????st[sti] = i + si;
????????????????++sti;
????????????}
????????}
????}
????inline int ntz(int x) const { return lg[x & -x]; }
????inline int bitmask(int l, int r) const { return ((1 << (r - l + 1)) - 1) << l; }
????inline Index query_small(Index l, Index r) const { return (l - l % S) + ntz(small[r] & bitmask(l % S, r % S)); }
????inline Index query_large(Index l, Index r) const {
????????int x = lg[r - l + 1];
????????return F(large[l * LG_L + x], large[(r - (1 << x) + 1) * LG_L + x]);
????}
};
#include <vector>
#include <unordered_map>
??
struct EulerTour {
????using tree_type = std::vector<std::vector<int>>;
????tree_type T;
????std::vector<int> id, depth;
????std::vector<int> ord;
??
????EulerTour(int N) : T(N), ord(N) {}
??
????void add_edge(int s, int t) {
????????T[s].push_back(t);
????????T[t].push_back(s);
????}
??
????void build(int root) {
????????id.reserve(T.size() * 3);
????????depth.reserve(T.size() * 3);
????????traverse(root);
????????id.shrink_to_fit();
????????depth.shrink_to_fit();
????}
??
????void traverse(int u, int p=-1, int d=0) {
????????ord[u] = id.size();
????????id.push_back(u);
????????depth.push_back(d);
????????for (int v : T[u]) {
????????????if (v == p) continue;
????????????traverse(v, u, d + 1);
????????????id.push_back(u);
????????????depth.push_back(d);
????????}
????}
};
#include <vector>
??
struct LCA {
????EulerTour& euler_tour;
????const RMQ<int> rmq;
??
????LCA(EulerTour& euler_tour) : euler_tour(euler_tour), rmq(euler_tour.depth) {}
??
????int query(int u, int v) const {
????????int l = euler_tour.ord[u];
????????int r = euler_tour.ord[v];
????????if (r < l) std::swap(r, l);
????????int x = rmq.query(l, r);
????????return euler_tour.id[x];
????}
};
??
#include <bits/stdc++.h>
using namespace std;
??
#define mygc(c) (c) = getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
??
template<typename T=int>
T rd(){T x=0,m=0,k;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||'9'<k)break;x=x*10+k-'0';}return x;}
template<typename T=int>
void wr(T x,char c='\n'){int s=0,m=0;char b[32];if(x<0)m=1,x=-x;for(;x;x/=10)b[s++]=x%10;if(!s)b[s++]=0;if(m)mypc('-');for(;s--;)mypc(b[s]+'0');mypc(c);}
??
int main() {
????int N = rd();
????EulerTour et(N);
????for (int i = 0; i < N; i++) {
????????int k = rd();
????????et.T[i].reserve(k);
????????for (int j = 0; j < k; j++) {
????????????et.T[i].push_back(rd());
????????}
????}
????et.build(0);
????LCA lca(et);
????int Q = rd();
????for (int i = 0; i < Q; i++) {
????????int u = rd(), v = rd();
????????wr(lca.query(u, v));
????}
????return 0;
}

Compiler output:
a.cc:5:1: error: expected unqualified-id before '?' token
    5 | ??
      | ^
a.cc:83:1: error: expected unqualified-id before '?' token
   83 | ??
      | ^
a.cc:118:1: error: expected unqualified-id before '?' token
  118 | ??
      | ^
a.cc:133:1: error: expected unqualified-id before '?' token
  133 | ??
      | ^
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:35,
                 from a.cc:134:
/usr/include/c++/14/cctype:64:11: error: 'isalnum' has not been declared in '::'
   64 |   using ::isalnum;
      |           ^~~~~~~
/usr/include/c++/14/cctype:65:11: error: 'isalpha' has not been declared in '::'
   65 |   using ::isalpha;
      |           ^~~~~~~
/usr/include/c++/14/cctype:66:11: error: 'iscntrl' has not been declared in '::'
   66 |   using ::iscntrl;
      |           ^~~~~~~
/usr/include/c++/14/cctype:67:11: error: 'isdigit' has not been declared in '::'
   67 |   using ::isdigit;
      |           ^~~~~~~
/usr/include/c++/14/cctype:68:11: error: 'isgraph' has not been declared in '::'
   68 |   using ::isgraph;
      |           ^~~~~~~
/usr/include/c++/14/cctype:69:11: error: 'islower' has not been declared in '::'
   69 |   using ::islower;
      |           ^~~~~~~
/usr/include/c++/14/cctype:70:11: error: 'isprint' has not been declared in '::'
   70 |   using ::isprint;
      |           ^~~~~~~
/usr/include/c++/14/cctype:71:11: error: 'ispunct' has not been declared in '::'
   71 |   using ::ispunct;
      |           ^~~~~~~
/usr/include/c++/14/cctype:72:11: error: 'isspace' has not been declared in '::'
   72 |   using ::isspace;
      |           ^~~~~~~
/usr/include/c++/14/cctype:73:11: error: 'isupper' has not been declared in '::'
   73 |   using ::isupper;
      |           ^~~~~~~
/usr/include/c++/14/cctype:74:11: error: 'isxdigit' has not been declared in '::'
   74 |   using ::isxdigit;
      |           ^~~~~~~~
/usr/include/c++/14/cctype:75:11: error: 'tolower' has not been declared in '::'
   75 |   using ::tolower;
      |           ^~~~~~~
/usr/include/c++/14/cctype:76:11: error: 'toupper' has not been declared in '::'
   76 |   using ::toupper;
      |           ^~~~~~~
/usr/include/c++/14/cctype:87:11: error: 'isblank' has not been declared in '::'
   87 |   using ::isblank;
      |           ^~~~~~~
In file included from /usr/include/c++/14/bits/locale_facets.h:41,
                 from /usr/include/c++/14/bits/basic_ios.h:37,
                 from /usr/include/c++/14/ios:46,
                 from /usr/include/c++/14/istream:40,
                 from /usr/include/c++/14/sstream:40,
                 from /usr/include/c++/14/complex:45,
                 from /usr/include/c++/14/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:127:
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:49:35: error: '_ISupper' was not declared in this scope; did you mean '_ISwupper'?
   49 |     static const mask upper     = _ISupper;
      |                                   ^~~~~~~~
      |                                   _ISwupper
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:50:35: error: '_ISlower' was not declared in this scope; did you mean '_ISwlower'?
   50 |     static const mask lower     = _ISlower;
      |                                   ^~~~~~~~
      |                                   _ISwlower
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:51:35: error: '_ISalpha' was not declared in this scope; did you mean '_ISwalpha'?
   51 |     static const mask alpha     = _ISalpha;
      |                                   ^~~~~~~~
      |                                   _ISwalpha
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:52:35: error: '_ISdigit' was not declared in this scope; did you mean '_ISwdigit'?
   52 |     static const mask digit     = _ISdigit;
      |                                   ^~~~~~~~
      |                                   _ISwdigit
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:53:35: error: '_ISxdigit' was not declared in this scope; did you mean '_ISwxdigit'?
   53 |     static const mask xdigit    = _ISxdigit;
      |                                   ^~~~~~~~~
      |                                   _ISwxdigit
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:54:35: error: '_ISspace' was not declared in this scope; did you mean '_ISwspace'?
   54 |     static const mask space     = _ISspace;
      |                                   ^~~~~~~~
      |                                   _ISwspace
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:55:35: error: '_ISprint' was not declared in this scope; did you mean '_ISwprint'?
   55 |     static const mask print     = _ISprint;
      |                                   ^~~~~~~~
      |                                   _ISwprint
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:56:35: error: '_ISalpha' was not declared in this scope; did you mean '_ISwalpha'?
   56 |     static const mask graph     = _ISalpha | _ISdigit | _ISpunct;
      |                                   ^~~~~~~~
      |                                   _ISwalpha
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:56:46: error: '_ISdigit' was not declared in this scope; did you mean '_ISwdigit'?
   56 |     static const mask graph     = _ISalpha | _ISdigit | _ISpunct;
      |                                              ^~~~~~~~
      |                                              _ISwdigit
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:56:57: error: '_ISpunct' was not declared in this scope; did you mean '_ISwpunct'?
   56 |     static const mask graph     = _ISalpha | _ISdigit | _ISpunct;
      |                                                         ^~~~~~~~
      |                                                         _ISwpunct
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:57:35: error: '_IScntrl' was not declared in this scope; did you mean '_ISwcntrl'?
   57 |     static const mask cntrl     = _IScntrl;
      |                                   ^~~~~~~~
      |                                   _ISwcntrl
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:58:35: error: '_ISpunct' was not declared in this scope; did you mean '_ISwpunct'?
   58 |     static const mask punct     = _ISpunct;
      |                                   ^~~~~~~~
      |                                   _ISwpunct
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:59:35: error: '_ISalpha' was not declared in this scope; did you mean '_ISwalpha'?
   59 |     static const mask alnum     = _ISalpha | _ISdigit;
      |                                   ^~~~~~~~
      |                                   _ISwalpha
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:59:46: error: '_ISdigit' was not declared in this scope; did you mean '_ISwdigit'?
   59 |     static const mask alnum     = _ISalpha | _ISdigit;
      |                                              ^~~~~~~~
      |                                              _ISwdigit
/usr/include/x86_64-linux-gnu/c++/14/bits/ctype_base.h:61:35: error: '_ISblank' was not declared in this scope; did you mean '_ISwblank'?
   61 |     static const mask blank     = _ISblank;
      |                                   ^~~~~~~~
      |                                   _ISwblank
a.cc:136:1: error: expected unqualified-id before '?' token
  136 | ??
      | ^
a.cc:144:1: error: expected unqualified-id before '?' token
  144 | ??
      | ^