Ý tưởng

Chúng ta có thể chia các học sinh thành 2 tập nếu các cặp mâu thuẫn tạo thành một đồ thị hai phía. Một đồ thị là đồ thị hai phía khi và chỉ khi không tồn tại chu trình lẻ.

Bài tập này có hai cách giải.

Cách giải 1

Áp dụng kỹ thuật chặt nhị phân song song, lưu giữ ba biến low, high và mid của cả ~Q~ truy vấn một cách đồng thời. Với mỗi ~mid_i~, ta cần kiểm tra xem với ~i~ cạnh lớn nhất kết hợp với ~a_i~ và ~b_i~ có tạo thành một đồ thị hai phía không. Để làm được điều này, ta có thể duy trì cấu trúc dữ liệu Disjoint-set. Mỗi đỉnh ~u~ sẽ tạo ra hai copy ~u0~ và ~u1~. Khi thêm cạnh ~u, v~ ta sẽ nối ~u0~ với ~v1~ và ~v1~ với ~u0~. Chu trình lẻ sẽ xuất hiện khi ~u0~ và ~u1~ ở chung cùng một thành phần liên thông.

Cách giải 2

Nếu không có các truy vấn, ta có thể áp dụng kỹ thuật DSU ở trên để lần lượt add các cạnh từ lớn về nhỏ để xác định khi nào thì đồ thị không còn là hai phía.

Nhận xét: Với đồ thị đã được dựng, tất cả các đường liên thông giữa ~u~ và ~v~ đều dẫn đến cùng một tính chẵn lẻ. Do đó nếu thêm cạnh ~u,~ ~v~ vào đồ thị tạo ra được chu trình lẻ, cách gỡ rối duy nhất là chặn mọi đường liên thông giữa ~u~ và ~v~, tương đương với mọi mâu thuẫn ta cần phải giảng hoà.

Từ nhận xét trên ta quy bài toán về cho một đồ thị, tìm cách xoá đi một vài cạnh trên đồ thị sao cho ~u, v~ không còn liên thông với nhau và cạnh trọng số lớn nhất phải xoá đi là nhỏ nhất. Đây là bài toán dựng cây khung lớn nhất và tìm cạnh nhỏ nhất trên đường đi trên cây cơ bản. Các bạn có thể tham khảo bài LUBENICA trên VNOJ.

Code mẫu

#include <bits/stdc++.h>
#define long long long

using namespace std;

const int maxn = 1000005;
const int LG = 20;

int N, M, Q;
vector<pair<int,int>> E;
vector<pair<int,int>> G[maxn];

int lab[maxn];
int color[maxn];

int height[maxn];
int jump[maxn][LG];
int wmin[maxn][LG];
vector<int> comp[maxn];

int find(int v) {
    return lab[v] < 0 ? v: lab[v] = find(lab[v]);
}

void join(int u, int v) {
    int val = color[u] ^ color[v] ^ 1;
    u = find(u); 
    v = find(v);
    if (comp[u].size() < comp[v].size()) swap(u, v);
    lab[v] = u;
    for(int s: comp[v]) {
        comp[u].push_back(s);
        color[s] ^= val;
    }
    comp[v].clear();
}

void dfs_prepare(int v, int p=-1) {
    for(auto [s, w]: G[v]) if (s != p) {
        jump[s][0] = v;
        wmin[s][0] = w;
        for(int i = 1; i < LG; ++i) {
            if (jump[s][i-1] == -1) continue;
            jump[s][i] = jump[jump[s][i-1]][i-1];
            wmin[s][i] = min(wmin[s][i-1], wmin[jump[s][i-1]][i-1]);
        }
        height[s] = height[v]+1;
        dfs_prepare(s, v);
    }
}

int lca(int u, int v) {
    if (height[u] < height[v]) swap(u, v);
    for(int i = LG-1; i >= 0; --i) {
        if (jump[u][i] != -1 && height[jump[u][i]] >= height[v]) {
            u = jump[u][i];
        }
    }
    if (u == v) return u;
    for(int i = LG-1; i >= 0; --i) {
        if (jump[u][i] != jump[v][i]) {
            u = jump[u][i];
            v = jump[v][i];
        }
    }
    return jump[u][0];
}

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

    cin >> N >> M >> Q;
    for(int i = 1; i <= M; ++i) {
        int u, v; cin >> u >> v;
        --u; --v;
        E.emplace_back(u, v);
    }

    for(int i = 0; i < N; ++i) {
        lab[i] = -1;
        color[i] = 0;
        height[i] = 0;
        comp[i].push_back(i);
        for(int j = 0; j < LG; ++j) {
            wmin[i][j] = M+1;
            jump[i][j] = -1;
        }
    }

    int baseAnswer = 0;
    for(int i = M; i > 0; --i) {
        auto [u, v] = E[i-1];
        if (find(u) == find(v)) {
            if (color[u] == color[v]) {
                baseAnswer = i;
                break;
            }
            continue;
        }
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
        join(u, v);
    }   

    for(int i = 0; i < N; ++i) {
        if (i == find(i)) dfs_prepare(i, -1);
    }

    while(Q--) {
        int u, v; cin >> u >> v;
        --u; --v;
        if (find(u) != find(v) || color[u] != color[v]) {
            cout << baseAnswer << "\n";
            continue;
        }

        int p = lca(u, v), ans = M;
        for(int i = LG-1; i >= 0; --i) {
            if (jump[u][i] != -1 && height[jump[u][i]] >= height[p]) {
                ans = min(ans, wmin[u][i]);
                u = jump[u][i];
            }
            if (jump[v][i] != -1 && height[jump[v][i]] >= height[p]) {
                ans = min(ans, wmin[v][i]);
                v = jump[v][i];
            }
        }
        cout << ans << "\n";
    }

    return 0;
}