Hướng dẫn cho PVHOI3 - Bài 3: Đếm chu trình

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: nhphucqt

Subtask 1

Tutorial

Với mỗi truy vấn, bỏ đi 2 cạnh trong danh sách và thêm 2 cạnh mới vào theo yêu cầu, sau đó duyệt hết tất cả các tập cạnh và đếm số lượng tập thoả mãn là chu trình.

Độ phức tạp: \(O(q \cdot 2^n \cdot n)\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const int MOD = (int)1e9 + 19972207;
int q, mul, add;
int cur;

const int N = 20;
int numNode;
pair<int,int> edges[N];
int mark[N];
int fa[N], cnt[N], res;

int root(int x) {
    return fa[x] < 0 ? x : fa[x] = root(fa[x]);
}

void unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) {
        return;
    }
    if (fa[u] > fa[v]) {
        swap(u, v);
    }
    fa[u] += fa[v];
    fa[v] = u;
}

void process() {
    memset(fa, -1, sizeof fa);
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= numNode+1; ++i) {
        if (mark[i] == 1) {
            cnt[edges[i].first]++;
            cnt[edges[i].second]++;
            unite(edges[i].first, edges[i].second);
        }
    }
    int last = -1;
    for (int i = 1; i <= numNode; ++i) {
        if (cnt[i] != 0 && cnt[i] != 2) {
            return;
        }
        if (cnt[i] == 2) {
            if (last != -1 && last != root(i)) {
                return;
            }
            last = root(i);
        }
    }
    res++;
}

void backtrack(int p) {
    if (p == numNode+2) {
        process();
        return;
    }
    backtrack(p+1);
    if (mark[p] != -1) {
        mark[p] = 1;
        backtrack(p+1);
        mark[p] = 0;
    }
}

int query(int e1, int u1, int v1, int e2, int u2, int v2) {
    memset(mark, 0, sizeof mark);
    mark[e1] = -1;
    mark[e2] = -1;
    edges[numNode] = make_pair(u1, v1);
    edges[numNode+1] = make_pair(u2, v2);
    res = 0;
    backtrack(1);
    return res-1;
}

int getRandom(int n) {
    cur = (1LL * mul * cur + add) % MOD;
    return 1 + cur % n;
}
int gspvhcute(void) {
    int res = 0;
    for (int i = 1; i <= q; i++) {
        int e1 = getRandom(numNode - 1);
        int u1 = getRandom(numNode); int v1 = getRandom(numNode);
        int e2 = getRandom(numNode - 1);
        int u2 = getRandom(numNode); int v2 = getRandom(numNode);
        int tmp = e1 == e2 || u1 == v1 || u2 == v2 
                ? MOD - 1 : query(e1, u1, v1, e2, u2, v2);
        res = (227LL * res + tmp) % MOD;
    }
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("chutrinh.inp", "r", stdin);
    freopen("chutrinh.out", "w", stdout);

    int t; cin >> t;
    cin >> numNode;
    for (int i = 1; i < numNode; ++i) {
        cin >> edges[i].first >> edges[i].second;
    }
    cin >> q >> cur >> mul >> add;

    cout << gspvhcute();

    return 0;
}

Các subtask sau, ta có nhận xét: Chọn đỉnh \(1\) là gốc của cây, khi bỏ đi hai cạnh, cây sẽ bị tách ra thành ba cây con.

Ví dụ, khi bỏ đi hai cạnh \((x_1, y_1)\) và \((x_2, y_2)\) với \(x_1\) là cha của \(y_1\) và \(x_2\) là cha của \(y_2\), thì cây sẽ tách thành ba cây con gốc \(1, \ x_1,\) và \(x_2\).

Thêm hai cạnh \((u_1, v_1)\) và \((u_2, v_2)\), gọi \(A(x)\) là cây con trong ba cây con gốc \(1, \ x_1, \text{hoặc} \ x_2\) chứa đỉnh x, xét các trường hợp sau:

  • Nếu \(A(u_1) \neq A(v_1)\) và \(A(u_2) \neq A(v_2)\),
    • Nếu cặp \((A(u_1),A(v_1))\) khác cặp \((A(u_2),A(v_2))\), số lượng chu trình đơn là \(0\) vì đồ thị sẽ thành một cái cây.
    • Nếu cặp \((A(u_1),A(v_1))\) giống cặp \((A(u_2),A(v_2))\), số lượng chu trình đơn là \(1\) vì khi đó đồ thị sẽ gồm 2 cây và một thành phần có số lượng đỉnh bằng số lượng cạnh (đồ thị có đúng \(1\) chu trình đơn).
  • Nếu \(A(u_1) \neq A(v_1)\) và \(A(u_2) = A(v_2)\), thì số lượng chu trình đơn là \(1\) vì khi thêm cạnh \((u_1,v_1)\) vào, đồ thị sẽ gồm hai cây, khi thêm cạnh \((u_2,v_2)\) vào một trong hai cây sẽ tạo ra đúng \(1\) chu trình đơn.
  • Nếu \(A(u_1) = A(v_1)\) và \(A(u_2) = A(v_2)\),
    • Nếu \(A(u_1) \neq A(u_2)\), thì số lượng chu trình đơn là \(2\) vì đồ thị bây giờ gồm \(1\) cây và \(2\) thành phần liên thông có số đỉnh bằng số cạnh.
    • Nếu \(A(u_1) = A(u_2)\), giả sử chưa thêm hai cạnh vào,
      • Nếu đường đi từ \(u_1\) đến \(v_1\) có giao với đường đi từ \(u_2\) đến \(v_2\) ít nhất một cạnh, thì số lượng chu trình đơn là \(3\), một chu trình có chứa cạnh \((u_1,v_1)\), một chu trình có chứa cạnh \((u_2,v_2)\), và một chu trình có chứa cả hai cạnh \((u_1,v_1)\) và \((u_2,v_2)\).
      • Nếu hai đường đi không có giao cạnh, thì số lượng chu trình đơn là \(2\), một chu trình có chứa cạnh \((u_1,v_1)\), và một chu trình có chứa cạnh \((u_2,v_2)\).

Ở các subtask sẽ có các cách khác nhau để kiểm tra tồn tại cạnh giao giữa hai đường đi.

Subtask 2

Tutorial

Cây có dạng chuổi thẳng, vậy nên ta có thể kiểm tra tương tự như kiểu tra hai đoạn thẳng giao nhau trên mảng một chiều.

Độ phức tạp: \(O(n+q)\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const int MOD = (int)1e9 + 19972207;
int q, mul, add;
int cur;

const int N = 15e4+7;
int numNode;
vector<int> adj[N];
pair<int,int> edges[N];
int nodes[N];

void buildGraph() {
    int rt = -1; 
    for (int i = 1; i <= numNode; ++i) {
        if (adj[i].size() == 1) {
            rt = i;
            break;
        }
    }
    assert(rt != -1);
    int siz = 0;
    int last = 0;
    for (int i = 1; i <= numNode; ++i) {
        nodes[rt] = ++siz;
        for (int j = 0; j < 2; ++j) {
            if (adj[rt][j] != last) {
                last = rt;
                rt = adj[rt][j];
                break;
            }
        }
    }
}

void updateAnc(int &a, int x, int u, int v) {
    if (x >= u) a = max(a, u);
    if (x >= v) a = max(a, v);
}

int query(int e1, int u1, int v1, int e2, int u2, int v2) {
    int x1, y1, x2, y2;
    tie(x1, y1) = edges[e1];
    tie(x2, y2) = edges[e2];
    x1 = nodes[x1]; y1 = nodes[y1];
    x2 = nodes[x2]; y2 = nodes[y2];
    if (x1 < y1) swap(x1, y1);
    if (x2 < y2) swap(x2, y2);
    u1 = nodes[u1]; v1 = nodes[v1];
    u2 = nodes[u2]; v2 = nodes[v2];
    int pu1, pv1, pu2, pv2;
    pu1 = pv1 = pu2 = pv2 = 1;
    updateAnc(pu1, u1, x1, x2);
    updateAnc(pv1, v1, x1, x2);
    updateAnc(pu2, u2, x1, x2);
    updateAnc(pv2, v2, x1, x2);
    if (pu1 > pv1) swap(pu1, pv1);
    if (pu2 > pv2) swap(pu2, pv2);
    if (pu2 != pv2) {
        swap(pu1, pu2);
        swap(pv1, pv2);
        swap(u1, u2);
        swap(v1, v2);
    }
    if (pu1 != pv1) {
        if (pu2 == pv2) return 1;
        else return pu1 == pu2 && pv1 == pv2;
    } else {
        if (pu1 != pu2) {
            return 2;
        } else {
            if (u1 > v1) swap(u1, v1);
            if (u2 > v2) swap(u2, v2);
            if (max(u1, u2) < min(v1, v2)) {
                return 3;
            } else {
                return 2;
            }
        }
    }
    assert(false);
    return 0;
}

int getRandom(int n) {
    cur = (1LL * mul * cur + add) % MOD;
    return 1 + cur % n;
}
int gspvhcute(void) {
    int res = 0;
    for (int i = 1; i <= q; i++) {
        int e1 = getRandom(numNode - 1);
        int u1 = getRandom(numNode); int v1 = getRandom(numNode);
        int e2 = getRandom(numNode - 1);
        int u2 = getRandom(numNode); int v2 = getRandom(numNode);
        int tmp = e1 == e2 || u1 == v1 || u2 == v2 
                ? MOD - 1 : query(e1, u1, v1, e2, u2, v2);
        res = (227LL * res + tmp) % MOD;
    }
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("chutrinh.inp", "r", stdin);
    freopen("chutrinh.out", "w", stdout);

    int t; cin >> t;
    cin >> numNode;
    for (int i = 1; i < numNode; ++i) {
        cin >> edges[i].first >> edges[i].second;
        adj[edges[i].first].push_back(edges[i].second);
        adj[edges[i].second].push_back(edges[i].first);
    }
    cin >> q >> cur >> mul >> add;
    buildGraph();
    cout << gspvhcute();
    return 0;
}

Subtask 3

Tutorial

DFS/BFS, đánh dấu các cạnh nằm trên đường đi từ \(u_1\) đến \(v_1\) và từ \(u_2\) đến \(v_2\), kiểm tra có tồn tại cạnh được đánh dấu ở cả hai con đường.

Độ phức tạp: \(O(q \cdot n)\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int x, y;
    Edge() {
        x = y = 0;
    }
    Edge(int _x, int _y) {
        x = _x; y = _y;
    }
};

const int MOD = (int)1e9 + 19972207;
int q, mul, add;
int cur;

const int N = 3007;
int numNode;
Edge edges[N];
vector<int> adj[N];
int in[N], out[N], tim;
bool mark[2][N];

void dfs(int u, int p) {
    in[u] = ++tim;
    for (int e : adj[u]) {
        int v = u ^ edges[e].x ^ edges[e].y;
        if (v!=p) {
            dfs(v, u);
        }
    }
    out[u] = tim;
}

void dfs(int u, int p, int dest, bool *mk) {
    if (u == dest) {
        throw 1;
    }
    for (int e : adj[u]) {
        int v = u ^ edges[e].x ^ edges[e].y;
        if (v != p) {
            mk[e] = true;
            dfs(v, u, dest, mk);
            mk[e] = false;
        }
    }
}

bool isAnc(int u, int v) {
    return in[u] <= in[v] && in[v] <= out[u];
}

void updateAnc(int &a, int x, int u, int v) {
    if (isAnc(u, x) && isAnc(a, u)) a = u;
    if (isAnc(v, x) && isAnc(a, v)) a = v;
}

int query(int e1, int u1, int v1, int e2, int u2, int v2) {
    int x1, y1, x2, y2;
    x1 = edges[e1].x; y1 = edges[e1].y;
    x2 = edges[e2].x; y2 = edges[e2].y;
    if (isAnc(x1, y1)) swap(x1, y1);
    if (isAnc(x2, y2)) swap(x2, y2);
    int pu1, pv1, pu2, pv2;
    pu1 = pv1 = pu2 = pv2 = 1;
    updateAnc(pu1, u1, x1, x2);
    updateAnc(pv1, v1, x1, x2);
    updateAnc(pu2, u2, x1, x2);
    updateAnc(pv2, v2, x1, x2);
    if (pu1 > pv1) swap(pu1, pv1);
    if (pu2 > pv2) swap(pu2, pv2);
    if (pu2 != pv2) {
        swap(pu1, pu2);
        swap(pv1, pv2);
        swap(u1, u2);
        swap(v1, v2);
    }
    if (pu1 != pv1) {
        if (pu2 == pv2) return 1;
        else return pu1 == pu2 && pv1 == pv2;
    } else {
        if (pu1 != pu2) {
            return 2;
        } else { // pu1 == pu2
            memset(mark[0], false, numNode * sizeof(bool));
            try {
                dfs(u1, 0, v1, mark[0]);
            } catch(...) {}
            memset(mark[1], false, numNode * sizeof(bool));
            try {
                dfs(u2, 0, v2, mark[1]);
            } catch(...) {}
            for (int i = 1; i < numNode; ++i) {
                if (mark[0][i] && mark[1][i]) {
                    return 3;
                }
            }
            return 2;
        }
    }
    assert(false);
    return 0;
}

int getRandom(int n) {
    cur = (1LL * mul * cur + add) % MOD;
    return 1 + cur % n;
}
int gspvhcute(void) {
    int res = 0;
    for (int i = 1; i <= q; i++) {
        int e1 = getRandom(numNode - 1);
        int u1 = getRandom(numNode); int v1 = getRandom(numNode);
        int e2 = getRandom(numNode - 1);
        int u2 = getRandom(numNode); int v2 = getRandom(numNode);
        int tmp = e1 == e2 || u1 == v1 || u2 == v2 
                ? MOD - 1 : query(e1, u1, v1, e2, u2, v2);
        res = (227LL * res + tmp) % MOD;
    }
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("chutrinh.inp", "r", stdin);
    freopen("chutrinh.out", "w", stdout);

    int t; cin >> t;
    cin >> numNode;
    for (int i = 1; i < numNode; ++i) {
        cin >> edges[i].x >> edges[i].y;
        adj[edges[i].x].push_back(i);
        adj[edges[i].y].push_back(i);
    }
    cin >> q >> cur >> mul >> add;

    dfs(1, 0);
    cout << gspvhcute();
    return 0;
}

Subtask 4

Tutorial

Gọi \(\texttt{lca}(u, v)\) là tổ tiên chung gần nhất của \(u\) và \(v\) (lưu ý: một đỉnh cũng là tổ tiên của chính nó), chia đường đi từ \(u_1\) đến \(v_1\) thành hai đường từ \(u_1\) đến \(\texttt{lca}(u_1,v_1)\) và \(v_1\) đến \(\texttt{lca}(u_1,v_1)\), đánh dấu các cạnh trên đường đi, tương tự với \((u_2,v_2)\), kiểm tra có tồn tại cạnh chung ở hai đường đi.

Độ phức tạp: \(O(q \cdot n)\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int x, y;
    Edge() {
        x = y = 0;
    }
    Edge(int _x, int _y) {
        x = _x; y = _y;
    }
};

const int MOD = (int)1e9 + 19972207;
int q, mul, add;
int cur;

const int N = 3007;
int numNode;
Edge edges[N];
vector<int> adj[N];
int in[N], out[N], tim;
int depth[N], par[N];
bool mark[N];

void dfs(int u, int p) {
    in[u] = ++tim;
    for (int e : adj[u]) {
        int v = u ^ edges[e].x ^ edges[e].y;
        if (v!=p) {
            depth[v] = depth[u] + 1;
            par[v] = u;
            dfs(v, u);
        }
    }
    out[u] = tim;
}

bool isAnc(int u, int v) {
    return in[u] <= in[v] && in[v] <= out[u];
}

void updateAnc(int &a, int x, int u, int v) {
    if (isAnc(u, x) && isAnc(a, u)) a = u;
    if (isAnc(v, x) && isAnc(a, v)) a = v;
}

bool goUp(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    while (depth[u] > depth[v]) {
        if (mark[u]) return true;
        mark[u] = true;
        u = par[u];
    }
    while (u != v) {
        if (mark[u]) return true;
        if (mark[v]) return true;
        mark[u] = true;
        mark[v] = true;
        u = par[u];
        v = par[v];
    }
    return false;
}

int query(int e1, int u1, int v1, int e2, int u2, int v2) {
    int x1, y1, x2, y2;
    x1 = edges[e1].x; y1 = edges[e1].y;
    x2 = edges[e2].x; y2 = edges[e2].y;
    if (isAnc(x1, y1)) swap(x1, y1);
    if (isAnc(x2, y2)) swap(x2, y2);
    int pu1, pv1, pu2, pv2;
    pu1 = pv1 = pu2 = pv2 = 1;
    updateAnc(pu1, u1, x1, x2);
    updateAnc(pv1, v1, x1, x2);
    updateAnc(pu2, u2, x1, x2);
    updateAnc(pv2, v2, x1, x2);
    if (pu1 > pv1) swap(pu1, pv1);
    if (pu2 > pv2) swap(pu2, pv2);
    if (pu2 != pv2) {
        swap(pu1, pu2);
        swap(pv1, pv2);
        swap(u1, u2);
        swap(v1, v2);
    }
    if (pu1 != pv1) {
        if (pu2 == pv2) return 1;
        else return pu1 == pu2 && pv1 == pv2;
    } else {
        if (pu1 != pu2) {
            return 2;
        } else { // pu1 == pu2
            memset(mark, false, (numNode+1) * sizeof(bool));
            goUp(u1, v1);
            if (goUp(u2, v2)) {
                return 3;
            } else {
                return 2;
            }
        }
    }
    assert(false);
    return 0;
}

int getRandom(int n) {
    cur = (1LL * mul * cur + add) % MOD;
    return 1 + cur % n;
}
int gspvhcute(void) {
    int res = 0;
    for (int i = 1; i <= q; i++) {
        int e1 = getRandom(numNode - 1);
        int u1 = getRandom(numNode); int v1 = getRandom(numNode);
        int e2 = getRandom(numNode - 1);
        int u2 = getRandom(numNode); int v2 = getRandom(numNode);
        int tmp = e1 == e2 || u1 == v1 || u2 == v2 
                ? MOD - 1 : query(e1, u1, v1, e2, u2, v2);
        res = (227LL * res + tmp) % MOD;
    }
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("chutrinh.inp", "r", stdin);
    freopen("chutrinh.out", "w", stdout);

    int t; cin >> t;
    cin >> numNode;
    for (int i = 1; i < numNode; ++i) {
        cin >> edges[i].x >> edges[i].y;
        adj[edges[i].x].push_back(i);
        adj[edges[i].y].push_back(i);
    }
    cin >> q >> cur >> mul >> add;

    dfs(1, 0);
    cout << gspvhcute();
    return 0;
}

Subtask 5

Tutorial

Gọi \(l_1\) là \(\texttt{lca}(u_1,v_1)\), \(l_2\) là \(\texttt{lca}(u_2,v_2)\), ta sẽ chia đường đi từ \(u_1\) đến \(v_1\) thành đường đi từ \(l_1\) đến \(u_1\) và đường đi từ \(l_1\) đến \(v_1\), tương tự với \((u_2,v_2)\).

Xét bài toán kiểm tra tồn tại cạnh chung ở hai đường đi \((x,y)\) và \((u,v)\) với \(x\) là tổ tiên của \(y\) và \(u\) là tổ tiên của \(v\):

  • nếu \(u = v\) hoặc \(x = y\) thì hai đường đi không giao nhau.
  • Nếu \(x\) và \(u\) không có quan hệ tổ tiên, hai đường đi không giao nhau.
  • Ngược lại, giả sử \(u\) là tổ tiên của \(x\), nếu \(x\) nằm trên đường đi từ \(u\) đến đỉnh cha của \(v\) và \(\texttt{lca}(y,v) \neq u\) thì hai đường đi có giao nhau ít nhất một cạnh.

Như vậy chỉ cần kiểm tra đường đi từ \(l_1\) đến \(u_1\) và từ \(l_1\) đến \(v_1\) có giao với đường đi từ \(l_2\) đến \(u_2\) và từ \(l_2\) đến \(v_2\) (kiểm tra \(4\) cặp đường đi) hay không.

Độ phức tạp: \(O((n+q) \cdot \log(n))\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int x, y;
    Edge() {
        x = y = 0;
    }
    Edge(int _x, int _y) {
        x = _x; y = _y;
    }
};

const int MOD = (int)1e9 + 19972207;
int q, mul, add;
int cur;

const int N = 15e4+7;
const int LOG = 20;
int numNode;
Edge edges[N];
vector<int> adj[N];
int in[N], out[N], tim;
int depth[N], anc[N][LOG];

void dfs(int u, int p) {
    in[u] = ++tim;
    for (int i = 1; i < LOG; ++i) {
        anc[u][i] = anc[anc[u][i-1]][i-1];
    }
    for (int e : adj[u]) {
        int v = u ^ edges[e].x ^ edges[e].y;
        if (v!=p) {
            depth[v] = depth[u] + 1;
            anc[v][0] = u;
            dfs(v, u);
        }
    }
    out[u] = tim;
}

inline bool isAnc(int u, int v) {
    return in[u] <= in[v] && in[v] <= out[u];
}

inline bool isStrictAnc(int u, int v) {
    return u != v && isAnc(u, v);
}

void updateAnc(int &a, int x, int u, int v) {
    if (isAnc(u, x) && isAnc(a, u)) a = u;
    if (isAnc(v, x) && isAnc(a, v)) a = v;
}

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

bool isSimpleIntersect(int x, int y, int u, int v) { // x is anc y, u is anc v
    if (u == v || x == y) return false;
    if (!isAnc(x, u) && !isAnc(u, x)) {
        return false;
    }
    if (isAnc(x, u)) {
        swap(x, u);
        swap(y, v);
    }
    // u is ancestor of x
    return isStrictAnc(x, v) && lca(y, v) != x;
}

bool isIntersect(int x, int y, int u, int v) {
    int luv = lca(u, v);
    int lxy = lca(x, y);
    return isSimpleIntersect(luv, u, lxy, x) 
        || isSimpleIntersect(luv, u, lxy, y)
        || isSimpleIntersect(luv, v, lxy, x)
        || isSimpleIntersect(luv, v, lxy, y);
}

int query(int e1, int u1, int v1, int e2, int u2, int v2) {
    int x1, y1, x2, y2;
    x1 = edges[e1].x; y1 = edges[e1].y;
    x2 = edges[e2].x; y2 = edges[e2].y;
    if (isAnc(x1, y1)) swap(x1, y1);
    if (isAnc(x2, y2)) swap(x2, y2);
    int pu1, pv1, pu2, pv2;
    pu1 = pv1 = pu2 = pv2 = 1;
    updateAnc(pu1, u1, x1, x2);
    updateAnc(pv1, v1, x1, x2);
    updateAnc(pu2, u2, x1, x2);
    updateAnc(pv2, v2, x1, x2);
    if (pu1 > pv1) swap(pu1, pv1);
    if (pu2 > pv2) swap(pu2, pv2);
    if (pu2 != pv2) {
        swap(pu1, pu2);
        swap(pv1, pv2);
        swap(u1, u2);
        swap(v1, v2);
    }
    if (pu1 != pv1) {
        if (pu2 == pv2) return 1;
        else return pu1 == pu2 && pv1 == pv2;
    } else {
        if (pu1 != pu2) {
            return 2;
        } else { // pu1 == pu2
            return isIntersect(u1, v1, u2, v2) ? 3 : 2;   
        }
    }
    assert(false);
    return 0;
}

int getRandom(int n) {
    cur = (1LL * mul * cur + add) % MOD;
    return 1 + cur % n;
}
int gspvhcute(void) {
    int res = 0;
    for (int i = 1; i <= q; i++) {
        int e1 = getRandom(numNode - 1);
        int u1 = getRandom(numNode); int v1 = getRandom(numNode);
        int e2 = getRandom(numNode - 1);
        int u2 = getRandom(numNode); int v2 = getRandom(numNode);
        int tmp = e1 == e2 || u1 == v1 || u2 == v2 
                ? MOD - 1 : query(e1, u1, v1, e2, u2, v2);
        res = (227LL * res + tmp) % MOD;
    }
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("chutrinh.inp", "r", stdin);
    freopen("chutrinh.out", "w", stdout);

    int t; cin >> t;
    cin >> numNode;
    for (int i = 1; i < numNode; ++i) {
        cin >> edges[i].x >> edges[i].y;
        adj[edges[i].x].push_back(i);
        adj[edges[i].y].push_back(i);
    }
    cin >> q >> cur >> mul >> add;

    depth[0] = -1;
    dfs(1, 0);
    cout << gspvhcute();
    return 0;
}

Subtask 6

Tutorial

Sử dụng Euler tour và RMQ để tìm \(\texttt{lca}(u,v)\) trong \(O(1)\) và làm y hệt subtask 5.

Độ phức tạp: \(O(n \cdot \log(n) + q)\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int x, y;
    Edge() {
        x = y = 0;
    }
    Edge(int _x, int _y) {
        x = _x; y = _y;
    }
};

const int MOD = (int)1e9 + 19972207;
int q, mul, add;
int cur;

const int N = 15e4+7;
const int LOG = 20;
int numNode;
Edge edges[N];
vector<int> adj[N];
int in[N], out[N], tim;
int siz, idx[N];
int depth[N], rmq[LOG][N*2];

void dfs(int u, int p) {
    in[u] = ++tim;
    rmq[0][++siz] = u;
    idx[u] = siz;
    for (int e : adj[u]) {
        int v = u ^ edges[e].x ^ edges[e].y;
        if (v!=p) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
            rmq[0][++siz] = u;
        }
    }
    out[u] = tim;
}

void buildRMQ() {
    for (int j = 1; j < LOG; ++j) {
        for (int i = 1; i + (1<<j) - 1 <= siz; ++i) {
            rmq[j][i] = depth[rmq[j-1][i]] < depth[rmq[j-1][i+(1<<j-1)]] ? rmq[j-1][i] : rmq[j-1][i+(1<<j-1)];
        }
    }
}

inline bool isAnc(int u, int v) {
    return in[u] <= in[v] && in[v] <= out[u];
}

inline bool isStrictAnc(int u, int v) {
    return u != v && isAnc(u, v);
}

void updateAnc(int &a, int x, int u, int v) {
    if (isAnc(u, x) && isAnc(a, u)) a = u;
    if (isAnc(v, x) && isAnc(a, v)) a = v;
}

int lca(int u, int v) {
    if (idx[u] > idx[v]) {
        swap(u, v);
    }
    int k = 31 - __builtin_clz(idx[v] - idx[u] + 1);
    return depth[rmq[k][idx[u]]] < depth[rmq[k][idx[v]-(1<<k)+1]] ? rmq[k][idx[u]] : rmq[k][idx[v]-(1<<k)+1];
}

bool isSimpleIntersect(int x, int y, int u, int v) { // x is anc y, u is anc v
    if (u == v || x == y) return false;
    if (!isAnc(x, u) && !isAnc(u, x)) {
        return false;
    }
    if (isAnc(x, u)) {
        swap(x, u);
        swap(y, v);
    }
    // u is ancestor of x
    return isStrictAnc(x, v) && lca(y, v) != x;
}

bool isIntersect(int x, int y, int u, int v) {
    int luv = lca(u, v);
    int lxy = lca(x, y);
    return isSimpleIntersect(luv, u, lxy, x) 
        || isSimpleIntersect(luv, u, lxy, y)
        || isSimpleIntersect(luv, v, lxy, x)
        || isSimpleIntersect(luv, v, lxy, y);
}

int query(int e1, int u1, int v1, int e2, int u2, int v2) {
    int x1, y1, x2, y2;
    x1 = edges[e1].x; y1 = edges[e1].y;
    x2 = edges[e2].x; y2 = edges[e2].y;
    if (isAnc(x1, y1)) swap(x1, y1);
    if (isAnc(x2, y2)) swap(x2, y2);
    int pu1, pv1, pu2, pv2;
    pu1 = pv1 = pu2 = pv2 = 1;
    updateAnc(pu1, u1, x1, x2);
    updateAnc(pv1, v1, x1, x2);
    updateAnc(pu2, u2, x1, x2);
    updateAnc(pv2, v2, x1, x2);
    if (pu1 > pv1) swap(pu1, pv1);
    if (pu2 > pv2) swap(pu2, pv2);
    if (pu2 != pv2) {
        swap(pu1, pu2);
        swap(pv1, pv2);
        swap(u1, u2);
        swap(v1, v2);
    }
    if (pu1 != pv1) {
        if (pu2 == pv2) return 1;
        else return pu1 == pu2 && pv1 == pv2;
    } else {
        if (pu1 != pu2) {
            return 2;
        } else { // pu1 == pu2
            return isIntersect(u1, v1, u2, v2) ? 3 : 2;   
        }
    }
    assert(false);
    return 0;
}

int getRandom(int n) {
    cur = (1LL * mul * cur + add) % MOD;
    return 1 + cur % n;
}
int gspvhcute(void) {
    int res = 0;
    for (int i = 1; i <= q; i++) {
        int e1 = getRandom(numNode - 1);
        int u1 = getRandom(numNode); int v1 = getRandom(numNode);
        int e2 = getRandom(numNode - 1);
        int u2 = getRandom(numNode); int v2 = getRandom(numNode);
        int tmp = e1 == e2 || u1 == v1 || u2 == v2 
                ? MOD - 1 : query(e1, u1, v1, e2, u2, v2);
        res = (227LL * res + tmp) % MOD;
    }
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("chutrinh.inp", "r", stdin);
    freopen("chutrinh.out", "w", stdout);

    int t; cin >> t;
    cin >> numNode;
    for (int i = 1; i < numNode; ++i) {
        cin >> edges[i].x >> edges[i].y;
        adj[edges[i].x].push_back(i);
        adj[edges[i].y].push_back(i);
    }
    cin >> q >> cur >> mul >> add;

    depth[0] = -1;
    siz = 0;
    tim = 0;
    dfs(1, 0);
    buildRMQ();
    cout << gspvhcute();
    return 0;
}

Bình luận

Không có bình luận nào.