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 <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n nodes. For <math><semantics><mrow><mi>q</mi></mrow><annotation encoding="application/x-tex">q</annotation></semantics></math>q queries <math><semantics><mrow><mo>[</mo><mi>l</mi><mo separator="true">,</mo><mi>r</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[l,r]</annotation></semantics></math>[l,r], you can ignore one of the nodes and find the maximum depth of the lowest common ancestor of remaining nodes.

**Constraints:** <math><semantics><mrow><mn>2</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn>100000</mn><mo separator="true">,</mo><mn>2</mn><mo>≤</mo><mi>q</mi><mo>≤</mo><mn>100000</mn></mrow><annotation encoding="application/x-tex">2\le n \le 100000, 2 \le q \le 100000</annotation></semantics></math>2≤n≤100000,2≤q≤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 <math><semantics><mrow><mo>[</mo><mi>l</mi><mo separator="true">,</mo><mi>r</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[l,r]</annotation></semantics></math>[l,r], find the first and last node, name them by <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u and <math><semantics><mrow><mi>v</mi></mrow><annotation encoding="application/x-tex">v</annotation></semantics></math>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 <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u and <math><semantics><mrow><mi>v</mi></mrow><annotation encoding="application/x-tex">v</annotation></semantics></math>v). 
 * If we ignore some node, say <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u, just find the LCA of <math><semantics><mrow><mo>[</mo><mi>l</mi><mo separator="true">,</mo><mi>u</mi><mo>−</mo><mn>1</mn><mo>]</mo></mrow><annotation encoding="application/x-tex">[l,u-1]</annotation></semantics></math>[l,u−1] and <math><semantics><mrow><mo>[</mo><mi>u</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><mi>r</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[u+1,r]</annotation></semantics></math>[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 <math><semantics><mrow><msup><mn>2</mn><mi>k</mi></msup></mrow><annotation encoding="application/x-tex">2^k</annotation></semantics></math>2k-th ancestor of all nodes. Move up <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u and <math><semantics><mrow><mi>v</mi></mrow><annotation encoding="application/x-tex">v</annotation></semantics></math>v until they meet.
2. RMQ - LCA problems can be reduced to RMQ. Find the euler tour of dfs (as a vector <math><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>V), and record the position of the first occurence of each node in the euler tour (as array <math><semantics><mrow><mi>I</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">In</annotation></semantics></math>In). RMQ is applied on array <math><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>V with comparator key <math><semantics><mrow><mi>D</mi><mi>e</mi><mi>p</mi><mo>[</mo><mi>u</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">Dep[u]</annotation></semantics></math>Dep[u]. The LCA of <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u and <math><semantics><mrow><mi>v</mi></mrow><annotation encoding="application/x-tex">v</annotation></semantics></math>v is the RMQ query answer of range <math><semantics><mrow><mo>[</mo><mi>I</mi><mi>n</mi><mo>[</mo><mi>u</mi><mo>]</mo><mo separator="true">,</mo><mi>I</mi><mi>n</mi><mo>[</mo><mi>v</mi><mo>]</mo><mo>]</mo></mrow><annotation encoding="application/x-tex">[In[u], In[v]]</annotation></semantics></math>[In[u],In[v]] (suppose <math><semantics><mrow><mi>I</mi><mi>n</mi><mo>[</mo><mi>u</mi><mo>]</mo><mo>≤</mo><mi>I</mi><mi>n</mi><mo>[</mo><mi>v</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">In[u] \le In[v]</annotation></semantics></math>In[u]≤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)

コメント

コメントを投稿