Cod sursa(job #3372121)

Utilizator StasBrega Stanislav Stas Data 2 noiembrie 2026 15:30:08
Problema Lowest Common Ancestor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.04 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

namespace
{
#define ll long long
#define int ll
#undef INT_MAX
#define INT_MAX LLONG_MAX
#define ull unsigned long long
#define PI acos(-1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vector<int>>
#define vf vector<long double>
#define vvf vector<vector<long double>>
#define cmplxd complex<double>
#define float long double
#define fs first
#define sc second
#define pb push_back
#define lsh(i) (1 << (i))
#define fi(i, n) for (int i = 0; (i) < (n); ++(i))
#define fe(x, a) for (auto &x : (a))
#define all(a) (a).begin(), (a).end()
#define YES (cout << "YES\n")
#define NO (cout << "NO\n")
#define endl '\n'
const int mod = (1e9 + 7);
const int pmod = 998244353;
const int altmod = 999999937;

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; // be careful deletion

struct custom_hash
{
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
    size_t operator()(pair<uint64_t, uint64_t> x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM) ^ (splitmix64(x.second + FIXED_RANDOM) >> 1);
    }
};
#define us unordered_set<int, custom_hash>
#define um unordered_map<int, int, custom_hash>
void multiply(vvi &Z, vvi B)
{
    int N = Z.size();
    vvi A(Z);
    Z = vvi(N, vi(N, 0));
    fi(i, N)
        fi(j, N)
            fi(k, N)
                Z[i][j] = (Z[i][j] + 1ll * A[i][k] * B[k][j] % altmod) % altmod;
}
[[maybe_unused]] void f(vvi &Z, int n)
{
    vvi aux(Z);
    while (n)
    {
        if (n % 2)
            multiply(Z, aux);
        multiply(aux, aux);
        n /= 2;
    }
}
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vvi graph(n);
    fi(i, n - 1)
    {
        int x;
        cin >> x;
        graph[x - 1].pb(i + 1);
    }

    vi el, h(n), v(n, -1);
    function<void(int, int)> dfs = [&](int x, int d)
    {
        if(v[x] == -1)
        {
            v[x] = el.size();
        }
        h[x] = d;
        el.pb(x);
        fe(y, graph[x])
        {
            dfs(y, d + 1);
            el.pb(x);
        }
    };
    dfs(0, 0);

    int k = 20, t = el.size();
    vvi rmq(t, vi(k));
    fi(i, t)
    {
        rmq[i][0] = el[i];
    }
    for(int j = 1; j < k; ++j)
    {
        for(int i = 0; i + (1 << j) <= t; ++i)
        {
            int x = rmq[i][j - 1], y = rmq[i + (1 << (j - 1))][j - 1];
            rmq[i][j] = h[x] < h[y] ? x : y;
        }
    }

    fi(i, m)
    {
        int x, y;
        cin >> x >> y;
        --x, --y;
        int l = v[x], r = v[y];
        if(l > r)
            swap(l, r);
        int len = 31 - __builtin_clz(r - l + 1);
        int a = rmq[l][len], b = rmq[r - (1 << len) + 1][len];
        cout << (h[a] < h[b] ? a : b) + 1 << endl;
    }
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("lca.in", "r", stdin);
    freopen("lca.out", "w", stdout);
#endif // ! ONLINE_JUDGE
    ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout.tie(nullptr);

    // int t;
    // cin >> t;
    int t = 1;

    fi(i, t)
    {
        // cout << "Case #" << i + 1 << ": ";
        solve();
    }

    return 0;
}