题目大意：给定一n边形的三角剖分，q次询问求两点最短路，最短指经过的边最短。

大体思路：分治，每次重新编号找最均匀的对角线切成两半，经过这条对角线的端点的利用该对角线计算，其他的分治下去。

Code

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 1e5 + 5;

int n;

int findrt(vector<pair<int, int>> Edge, int n) {
    int mx = 0, ans;
    for (int i = 0; i < Edge.size(); i++) {
        int u = Edge[i].first;
        int v = Edge[i].second;
        int now = abs(u - v);
        if (now > n / 2)
            now = n - now;
        if (now > mx) {
            mx = now;
            ans = i;
        }
    }
    return ans;
}

int num[MAXN][50], from[MAXN][50];
int temp[MAXN * 2];

struct Query {
    int x, y, ans;
    bool operator<(const Query& oth) const {
        return make_pair(make_pair(x, y), ans) < make_pair(make_pair(oth.x, oth.y), oth.ans);
    }
};

int renumber(vector<pair<int, int>>& Edge, vector<Query>& Ask, int dep) {
    int tot = 0;
    for (auto [u, v] : Edge) {
        temp[++tot] = u;
        temp[++tot] = v;
    }
    sort(temp + 1, temp + tot + 1);
    tot = unique(temp + 1, temp + tot + 1) - temp - 1;

    for (auto& [u, v] : Edge) {
        u = num[u][dep] = lower_bound(temp + 1, temp + tot + 1, u) - temp;
        v = num[v][dep] = lower_bound(temp + 1, temp + tot + 1, v) - temp;
        from[num[u][dep]][dep] = u;
        from[num[v][dep]][dep] = v;
    }
    for (auto& [u, v, ans] : Ask) {
        u = num[u][dep];
        v = num[v][dep];
    }
    return tot;
}

vector<vector<int>> build(vector<pair<int, int>> Edge, int n) {
    vector<vector<int>> G(n + 1);
    for (auto [u, v] : Edge) {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    return G;
}

vector<int> bfs(int x, vector<vector<int>> G) {
    vector<int> dis(n + 1, -1);
    dis[x] = 0;
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : G[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return dis;
}

bool chk(int l, int r, int x) {
    return l <= x && x <= r;
}

int chk2(int l, int r, int x) {
    if (x == l || x == r)
        return 0;
    if (chk(l, r, x))
        return 1;
    return -1;
}

void solve(vector<pair<int, int>> Edge, vector<Query>& Ask, int dep) {
    // for (int i = 0; i < dep; i++)
    //     cerr << "  ";
    // cerr << "> {";
    // for (auto [u, v] : Edge) {
    //     cerr << "{" << u << " " << v << "} ";
    // }
    // cerr << "} {";
    // for (auto [u, v, ans] : Ask) {
    //     cerr << "{" << u << " " << v << " " << ans << "} ";
    // }
    // cerr << "}" << endl;
    int n = renumber(Edge, Ask, dep);
    if (n == 3) {
        for (auto& [u, v, ans] : Ask) {
            if (u == v)
                ans = 0;
            else
                ans = 1;
        }
        return;
    }
    int rt = findrt(Edge, n);
    int x = Edge[rt].first;
    int y = Edge[rt].second;
    if (x > y)
        swap(x, y);
    vector<pair<int, int>> leftE, rightE;
    vector<Query> leftQ, rightQ;

    vector<vector<int>> G = build(Edge, n);

    vector<int> dis1 = bfs(x, G);
    vector<int> dis2 = bfs(y, G);

    map<pair<int, int>, int> mp;

    for (auto& [u, v, ans] : Ask) {
        if (u == x)
            ans = dis1[v];
        else if (u == y)
            ans = dis2[v];
        else if (v == x)
            ans = dis1[u];
        else if (v == y)
            ans = dis2[u];
        else if (chk(x, y, u) ^ chk(x, y, v)) {
            ans = min(dis1[u] + dis1[v], dis2[u] + dis2[v]);
        } else if (chk(x, y, u)) {
            leftQ.push_back({ u, v, ans });
        } else {
            rightQ.push_back({ u, v, ans });
        }
    }

    for (auto [u, v] : Edge) {
        if (chk2(x, y, u) + chk2(x, y, v) >= 0) {
            leftE.push_back(make_pair(u, v));
        }
        if (chk2(x, y, u) + chk2(x, y, v) <= 0) {
            rightE.push_back(make_pair(u, v));
        }
    }
    solve(leftE, leftQ, dep + 1);
    solve(rightE, rightQ, dep + 1);
    for (auto [u, v, ans] : leftQ)
        mp[make_pair(u, v)] = ans;
    for (auto [u, v, ans] : rightQ)
        mp[make_pair(u, v)] = ans;
    for (auto& [u, v, ans] : Ask)
        if (!ans && u != v)
            ans = mp[make_pair(u, v)];

    for (auto& [u, v, ans] : Ask) {
        u = from[u][dep];
        v = from[v][dep];
    }

    // for (int i = 0; i < dep; i++)
    //     cerr << "  ";
    // cerr << "< {";
    // for (auto [u, v] : Edge) {
    //     cerr << "{" << u << " " << v << "} ";
    // }
    // cerr << "} {";
    // for (auto [u, v, ans] : Ask) {
    //     cerr << "{" << u << " " << v << " " << ans << "} ";
    // }
    // cerr << "}" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    vector<pair<int, int>> Edge;
    for (int i = 1; i <= n - 3; i++) {
        int x, y;
        cin >> x >> y;
        Edge.push_back(make_pair(x, y));
    }
    for (int i = 1; i < n; i++) {
        Edge.push_back(make_pair(i, i + 1));
    }
    Edge.push_back(make_pair(1, n));
    int q;
    cin >> q;
    vector<Query> Ask;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        Ask.push_back({ x, y, 0 });
    }
    solve(Edge, Ask, 0);

    for (auto [u, v, ans] : Ask) {
        cout << ans << endl;
    }

    return 0;
}