Codeforces - Company

Source: Codeforces Round #520 (Div. 2): E. Company
Tags: Graph, Data Structures

Problem:
Cho một cây gồm N đỉnh có gốc là đỉnh 1, độ cao h[u] của một đỉnh u là khoảng cách từ đỉnh gốc tới nó. Cho Q truy vấn L, R, với tập những đỉnh có số hiệu từ L đến R, bạn được phép loại một đỉnh duy nhất ra khỏi tập này, in ra độ cao lớn nhất của đỉnh là cha của tất cả những đỉnh trong tập.
Dòng đầu là N, Q. Dòng sau là N - 1 số p[2], p[3], ..., p[N] với p[u] là đỉnh cha trực tiếp của đỉnh u.
Q dòng sau mỗi dòng 2 số L, R thể hiện truy vấn.
In ra output đáp án trên một dòng cho mỗi truy vấn tương ứng là 2 số lần lượt là đỉnh bị loại khỏi tập đỉnh trong truy vấn và độ cao lớn nhất của cha chung của tất cả những đỉnh còn lại trong tập, nếu có nhiều cách loại, in ra đáp án bất kỳ.
2 ≤ N ≤ 1e5. 1 ≤ Q ≤ 1e5.

Ví dụ:
Input:
11 5
1 1 3 3 3 4 2 7 7 6
4 6
4 8
1 11
9 11
8 11

Output:

4 1

8 1

1 0

11 3

8 1

Explanation:

Trong truy vấn 1, dù ta có loại đỉnh 4, 5 hoặc 6 thì cha chung của những đỉnh còn lại đều là 3.

Trong truy vấn 2, nếu ta chọn loại các đỉnh khác đỉnh 8, thì cha chung của những đỉnh còn lại đều sẽ là 1, nếu ta loại đỉnh 8, cha chung của những đỉnh còn lại sẽ là 3, do h[3] > h[1] (1 > 0) do đó ta sẽ loại đỉnh 8.

Solution:

Đây là một đề trong contest do một bạn Việt Nam của chúng ta host :v

Nếu không có điều kiện được phép loại 1 đỉnh, chúng ta có thể nghĩ ngay đến một thuật toán đơn giản chính là sử dụng IT + LCA.

Tuy nhiên để xử lý bài này, chúng ta cần sử dụng DFS Parenthesis Theorem.

Gọi in[u] là thời điểm chúng ta DFS đến đỉnh u, và out[u] = max(in[v]) với mọi v là đỉnh con của u (dù trực tiếp hay không trực tiếp). Dựa vào định lý ta có: nếu v là con của u thì in[u] ≤ in[v] ≤ out[u]. Từ đó ta thấy, LCA của các đỉnh từ L đến R thực chất ta chỉ cần quan tâm đến LCA của 2 đỉnh u và v có in[u] = min(in[L..R]) và in[v] = max(in[L..R]), vì ta có:

in[u] ≤ in[x1] ≤ in[x2] ≤ ... ≤ in[v]

do đó nếu một đỉnh a là LCA của u và v

thì in[a] ≤ in[u] ≤ in[x1] ≤ in[x2] ≤ ... ≤ in[v] ≤ out[a]

=> in[a] ≤ in[u] ≤ out[a]; in[a] ≤ in[x1] ≤ out[a]; in[a] ≤ in[x2] ≤ out[a]; ...; in[a] ≤ in[v] ≤ out[a]

=> a là đỉnh cha chung của tất cả các đỉnh từ L đến R

Vậy bây giờ nếu chúng ta muốn loại trừ một đỉnh, để tối ưu thì chúng ta cần loại đỉnh u hoặc v ở trên. Chúng ta chỉ cần thử với u thì nếu loại u sẽ chia thành 2 tập đỉnh là L..u - 1 và u + 1..R, tìm LCA của mỗi tập rồi tìm LCA của 2 đỉnh cha đó, tương tự với v.

Để tìm được 2 đỉnh u và v, chúng ta cần dựng sparse table hoặc IT gì đó để lưu lại.

Độ phức tạp: O((N + Q)logN)

Code:

#include <iostream>

#include <vector>

#include <math.h>

using namespace std;

int n, q, p[20][100015], h[100015], num[100015], out[100015], dfsCnt, umin[20][100015], nmin[20][100015], umax[20][100015], nmax[20][100015];

vector <int> a[100015];

void dfs(int u) {

    num[u] = ++dfsCnt;

    umin[0][u] = umax[0][u] = u;

    nmin[0][u] = nmax[0][u] = num[u];

    for (int v: a[u])

        h[v] = h[u] + 1, dfs(v);

    out[u] = dfsCnt;

}

int minv(int l, int r) {

    if (l > r) return 0;

    int i = log2(r - l + 1);

    int u = umin[i][l + (1 << i) - 1];

    int v = umin[i][r];

    return (num[u] < num[v] ? u : v);

}

int maxv(int l, int r) {

    if (l > r) return 0;

    int i = log2(r - l + 1);

    int u = umax[i][l + (1 << i) - 1];

    int v = umax[i][r];

    return (num[u] > num[v] ? u : v);

}

int LCA(int u, int v) {

    if (!u) return v;

    if (!v) return u;

    if (h[u] < h[v]) swap(u, v);

    for (int i = log2(h[u]); i >= 0; --i)

        if (h[p[i][u]] >= h[v]) u = p[i][u];

    if (u == v) return u;

    for (int i = log2(h[u]); i >= 0; --i)

        if (p[i][u] != p[i][v])

            u = p[i][u], v = p[i][v];

    return p[0][u];

}

int main() {

    cin >> n >> q;

    for (int u = 2; u <= n; ++u)

        cin >> p[0][u],

        a[p[0][u]].push_back(u);

    h[1] = 1; dfs(1);

    for (int i = 1; 1 << i <= n; ++i)

        for (int u = 1 << i; u <= n; ++u) {

            if (nmin[i - 1][u] < nmin[i - 1][u - (1 << i - 1)])

                nmin[i][u] = nmin[i - 1][u],

                umin[i][u] = umin[i - 1][u];

            else

                nmin[i][u] = nmin[i - 1][u - (1 << i - 1)],

                umin[i][u] = umin[i - 1][u - (1 << i - 1)];

            if (nmax[i - 1][u] > nmax[i - 1][u - (1 << i - 1)])

                nmax[i][u] = nmax[i - 1][u],

                umax[i][u] = umax[i - 1][u];

            else

                nmax[i][u] = nmax[i - 1][u - (1 << i - 1)],

                umax[i][u] = umax[i - 1][u - (1 << i - 1)];

        }

    for (int i = 1; 1 << i <= n; ++i)

        for (int u = 1; u <= n; ++u)

            p[i][u] = p[i - 1][p[i - 1][u]];

    for (int l, r, x1, x2, h1, h2, u, v; q--;) {

        cin >> l >> r;

        x1 = maxv(l, r);

        u = LCA(maxv(l, x1 - 1), minv(l, x1 - 1));

        v = LCA(maxv(x1 + 1, r), minv(x1 + 1, r));

        h1 = h[LCA(u, v)];

        x2 = minv(l, r);

        u = LCA(maxv(l, x2 - 1), minv(l, x2 - 1));

        v = LCA(maxv(x2 + 1, r), minv(x2 + 1, r));

        h2 = h[LCA(u, v)];

        if (h1 > h2) cout << x1 << ' ' << h1 - 1 << '\n';

        else cout << x2 << ' ' << h2 - 1 << '\n';

    }

}