Codeforces 1062E. Company (LCA+RMQ)

日付: 11月 24, 2018

[Problem - 1062E - Codeforces](https://codeforces.com/contest/1062/problem/E)
## Problem
Given a tree (root index is 1) with $n$ nodes. For $q$ queries $[l,r]$, you can ignore one of the nodes and find the maximum depth of the lowest common ancestor of remaining nodes.

**Constraints:** $2\le n \le 100000, 2 \le q \le 100000$

## Solution
The key observation is: **The LCA of some nodes of a tree is the LCA of the first and last node in dfs order**

With this observation, this problem is quite simple.
1. Do a dfs, calculate the dfs order, the depth and necessary information for later calculating LCA
2. Maintain the RMQ of dfs order array (for this problem, sparse table is suitable)
3. For query $[l,r]$, find the first and last node, name them by $u$ and $v$. Only these two nodes may be ignored in the optimal answer. (if we ignore another node, the LCA of remaining nodes is also the LCA of $u$ and $v$). 
 * If we ignore some node, say $u$, just find the LCA of $[l,u-1]$ and $[u+1,r]$
 * To find LCA of a range, just find the LCA of the first and last node in dfs order in that range

To find LCA of two nodes, there are two common ways:

1. Doubling - Store the $2^k$-th ancestor of all nodes. Move up $u$ and $v$ until they meet.
2. RMQ - LCA problems can be reduced to RMQ. Find the euler tour of dfs (as a vector $V$),  and record the position of the first occurence of each node in the euler tour (as array $In$). RMQ is applied on array $V$ with comparator key $Dep[u]$. The LCA of $u$ and $v$ is the RMQ query answer of range $[In[u], In[v]]$ (suppose $In[u] \le In[v]$, if not satisfied, just swap them)

<details><summary>Doubling LCA</summary>

```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
#define FD(i,b,a) for(int i=(b);i>=(a);--i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;
constexpr LL inv(LL x, LL m) { return x > m ? inv(x % m, m) : x > 1 ? inv(m % x, m) * (m - m / x) % m : x; }
constexpr LL mpow(LL a, LL k, LL m) { LL r(1); for (a %= m; k; k >>= 1, a = a * a % m) if (k & 1)r = r * a % m; return r; }

template <typename T> struct STable {
    vector<vector<T>> F;
    function<T(T, T)> op;
    STable(const vector<T> &A, function<T(T, T)> op = [](T a, T b) { return min(a, b); }
          ): F(32 - __builtin_clz(A.size()), A), op(op)  {
        for (size_t c = 0; c + 1 < F.size(); c++) for (size_t i = 0; i < A.size(); i++)
                F[c + 1][i] = i + (1 << c) < A.size() ? op(F[c][i], F[c][i + (1 << c)]) : F[c][i];
    }
    T query(int l, int r) { int c = 31 - __builtin_clz(r - l); return op(F[c][l], F[c][r - (1 << c)]); }
};

const int N = 1e5 + 5;
int n, q, P[N][21];

int main() {
    scanf("%d%d", &n, &q);
    vector<vector<int>> G(n + 1);
    FI(i, 2, n) {
        int j;
        scanf("%d", &j);
        G[j].push_back(i);
    }
    int ts = 0;
    vector<int> In(n + 1), Dep(n + 1);
    auto dfs = [&](int u, int p, auto f) -> void {
        P[u][0] = p, In[u] = ++ts, Dep[u] = Dep[p] + 1;
        FI(i, 1, 20) P[u][i] = P[P[u][i - 1]][i - 1];
        for (auto v : G[u]) f(v, u, f);
    };
    dfs(1, 0, dfs);
    auto lca = [&](int u, int v) {
        if (Dep[u] < Dep[v]) swap(u, v);
        int d = Dep[u] - Dep[v];
        for (int i = 0; i <= 20; i++) if (d & 1 << i) u = P[u][i];
        if (u == v) return u;
        for (int i = 20; i >= 0; i--) if (P[u][i] != P[v][i]) u = P[u][i], v = P[v][i];
        return P[u][0];
    };
    vector<int> I(n + 1);
    iota(I.begin(), I.end(), 0);
    STable<int> stmi(I, [&](int i, int j) { return In[i] < In[j] ? i : j; });
    STable<int> stma(I, [&](int i, int j) { return In[i] < In[j] ? j : i; });
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        auto calc = [&](int u) {
            if (u == l) return Dep[lca(stmi.query(l + 1, r + 1), stma.query(l + 1, r + 1))];
            if (u == r) return Dep[lca(stmi.query(l, r), stma.query(l, r))];
            return Dep[lca(lca(stmi.query(l, u), stma.query(l, u)), lca(stmi.query(u + 1, r + 1),
                                                                        stma.query(u + 1, r + 1)))];
        };
        int u = stmi.query(l, r + 1), au = calc(u) - 1;
        int v = stma.query(l, r + 1), av = calc(v) - 1;
        if (au > av) printf("%d %d\n", u, au);
        else printf("%d %d\n", v, av);
    }
}
```
</details>
<details><summary>RMQ LCA</summary>

const int N = 1e5 + 5;
int n, q;

int main() {
    scanf("%d%d", &n, &q);
    vector<vector<int>> G(n + 1);
    for (int i = 2, j; i <= n; i++) scanf("%d", &j), G[j].push_back(i);
    vector<int> In(n + 1), Dep(n + 1), V;
    auto dfs = [&](int u, int p, auto f) -> void {
        In[u] = V.size(), V.push_back(u), Dep[u] = Dep[p] + 1;
        for (auto v : G[u]) f(v, u, f), V.push_back(u);
    };
    dfs(1, 0, dfs);
    vector<int> I(n + 1);
    iota(I.begin(), I.end(), 0);
    STable<int> stmi(I, [&](int i, int j) { return In[i] < In[j] ? i : j; });
    STable<int> stma(I, [&](int i, int j) { return In[i] < In[j] ? j : i; });
    STable<int> lcav(V, [&](int u, int v) { return Dep[u] < Dep[v] ? u : v; });
    auto lca = [&](int u, int v) { auto [i, j] = minmax(In[u], In[v]); return lcav.query(i, j + 1); };
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        auto calc = [&](int u) {
            if (u == l) return Dep[lca(stmi.query(l + 1, r + 1), stma.query(l + 1, r + 1))];
            if (u == r) return Dep[lca(stmi.query(l, r), stma.query(l, r))];
            return Dep[lca(lca(stmi.query(l, u), stma.query(l, u)), lca(stmi.query(u + 1, r + 1),
                                                                        stma.query(u + 1, r + 1)))];
        };
        int u = stmi.query(l, r + 1), au = calc(u) - 1;
        int v = stma.query(l, r + 1), av = calc(v) - 1;
        if (au > av) printf("%d %d\n", u, au);
        else printf("%d %d\n", v, av);
    }
}
```
</details>

KONGROOの基地

このブログを検索

Codeforces 1062E. Company (LCA+RMQ)

コメント

コメントを投稿