Thuật toán

Tóm đề

~dist_{u, v}~ là khoảng cách từ đỉnh ~u~ đến đỉnh ~v~.

Cho một cây có ~n~ đỉnh, mỗi truy vấn cho một tập đỉnh, tìm ~max(dist_{u, v})~ với ~u~ và ~v~ thuộc tập đỉnh đã cho.

Trường hợp ~n \le 1000~

Ta chọn một đỉnh bất kỳ làm gốc. Giả sử đỉnh đó là ~1~.

• Tìm đỉnh ~u~ thuộc tập đỉnh đã cho thỏa ~dist_{1, u}~ là lớn nhất.
• Tìm đỉnh ~v~ thuộc tập đỉnh đã cho thỏa ~dist_{u, v}~ là lớn nhất.

Kết quả bài toán là ~dist_{u, v}~.

Với mỗi ngày, ta tìm đỉnh ~u~ trong ~O(1)~ và bfs từ đỉnh ~u~ đến các đỉnh khác để tìm đỉnh ~v~ trong ~O(n)~.

Do đó độ phức tạp thuật toán sẽ là ~O(n\times k)~

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 1;

int n, k;
vector<int> adj[N], group[N];
int h[N], d[N];

void Input() {
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        if (y) {
            adj[i].push_back(y);
            adj[y].push_back(i);
        }
        group[x].push_back(i);
    }
}

void bfs(int s) {
    memset(d, -1, sizeof d);
    queue<int> q;
    q.push(s);
    d[s] = 0;
    while(q.size()) {
        int u = q.front();
        q.pop();
        for(int &v : adj[u]) if (d[v] == -1) {
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    Input();

    bfs(1);
    for(int i = 1; i <= n; ++i) h[i] = d[i];

    for(int i = 1; i <= k; ++i) {
        int deepest = group[i][0];
        for(int &u : group[i]) if (h[deepest] < h[u])
            deepest = u;
        bfs(deepest);
        int res = 0;
        for(int &u : group[i]) if (deepest != u)
            res = max(res, d[u]);
        cout << res << '\n';
    }

    return 0;
}

Trường hợp ~n \le 2\times10^5~

Ta sẽ tối ưu bước tìm đỉnh ~v~ trong ~log_{2}(n)~ bằng LCA. Tìm hiểu thêm tại: https://vnoi.info/wiki/algo/data-structures/lca-binlift.md .

Sau khi tìm được đỉnh ~u~, khoảng cách từ đỉnh ~u~ đến một đỉnh ~v~ bất kỳ bằng ~dist_{1,u} + dist_{1, v} - 2*dist_{1,LCA(u, v)}~.

Độ phức tạp thuật toán ~O(n\times log_{2}(n))~.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 1;
const int LOG = log2(N) + 2;

int n, k;
vector<int> adj[N], group[N];
int P[LOG][N], h[N];

void Input() {
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        if (y) {
            adj[i].push_back(y);
            adj[y].push_back(i);
        }
        group[x].push_back(i);
    }
}

void dfs(int u) {
    for(int &v : adj[u]) if (h[v] == 0) {
        h[v] = h[u] + 1;
        P[0][v] = u;
        dfs(v);
    }
}

void prepareLCA() {
    memset(h, 0, sizeof h);
    h[1] = 1; P[0][1] = 1;
    dfs(1);
    for(int i = 1; i < LOG; ++i) {
        for(int j = 1; j <= n; ++j) {
            P[i][j] = P[i - 1][P[i - 1][j]];
        }
    }
}

int LCA(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    for(int i = LOG - 1; i >= 0; --i)
        if (h[P[i][u]] >= h[v])
            u = P[i][u];
    for(int i = LOG - 1; i >= 0; --i)
        if (P[i][u] != P[i][v])
            u = P[i][u],
            v = P[i][v];
    if (u != v) return P[0][u];
    return u;
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    Input();
    prepareLCA();
    for(int i = 1; i <= k; ++i) {
        int deepest = group[i][0];
        for(int &u : group[i])
            if (h[deepest] < h[u])
                deepest = u;
        int res = 0;
        for(int &u : group[i]) if (deepest != u) {
            int p = LCA(deepest, u);
            res = max(res, h[deepest] + h[u] - 2 * h[p]);
        }
        cout << res << '\n';
    }

    return 0;
}