Hướng giải của Quan hệ huyết thống

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Nhận xét

Bài toán yêu cầu kiểm tra quan hệ tổ tiên giữa hai đỉnh trên cây. Có thể giải bằng cách duy trì mảng \(tin\) và \(tout\) từ Euler Tour.

Ý tưởng giải

  1. Thực hiện DFS từ gốc, ghi lại \(tin[u]\) (thời điểm vào) và \(tout[u]\) (thời điểm ra).
  2. Đỉnh \(u\) là tổ tiên của đỉnh \(v\) khi và chỉ khi:
    • \(tin[u] \le tin[v]\) (v được thăm sau u)
    • \(tout[v] \le tout[u]\) (v kết thúc trước khi u kết thúc)
  3. Chứng minh: Nếu \(u\) là tổ tiên của \(v\) thì \(v\) nằm trong subtree của \(u\), do đó \(tin[u] \le tin[v] \le tout[v] \le tout[u]\).

Độ phức tạp

  • Tiền xử lý DFS: \(O(N)\)
  • Mỗi truy vấn: \(O(1)\)
  • Tổng: \(O(N + Q)\)

Code mẫu

// Giải thuật ett cho bài toán ett-ancestor\n#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN];
int timer_dfs = 0;

void dfs(int u, int parent) {
    tin[u] = ++timer_dfs;
    for (int v : adj[u]) {
        if (v != parent) {
            dfs(v, u);
        }
    }
    tout[u] = timer_dfs;
}

// Kiem tra u co phai la to tien cua v khong
bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int main() {
    // Doc du lieu dau vao
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0);

    while (q--) {
        int u, v;
        cin >> u >> v;
        if (is_ancestor(u, v)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.