题解 P12703 [KOI 2022 Round 2] 外环路

odt03 · 2026-07-22 08:31:18 · 题解

一道练习点分治的题。

对于每一个点进行一遍 Dijkstra 是不可接受的，考虑点分治处理。

我们按照点分治的方式递归处理一个询问，假设当前递归到的分治中心是 c，询问的两点是 u,v，那么我们就要为最短路径分类。所有的最短路径可以分为三类：

但是时间瓶颈是由子树个数 s 决定的，因为我们对每一个分治重心都要跑 s+1 遍 Dijkstra。根据题目条件，容易想到对整棵树进行三度化。此时对每一个分治重心只需最多跑 4 遍 Dijkstra，而三度化最多只会新增 n 个节点，所以总结点数仍是 O(n) 的。

实际上分治时可以将所有询问离散化，在每次分治时一并处理，可以省很多空间。在递归时如果某个子树没有询问了，就不要向下递归，这样剪枝可以节省很多时间。

时间复杂度 O(n\log^2n)。

::::info[Code]

const int inf = 0x3f3f3f3f3f3f3f3fll;
int n, k, Q, m;
vector<pair<int, int>> G[200010];
vector<int> T[200010], outp;
int w[100010];
struct Q {
    int u, v;
} q[250010];
void trans() {
    m = n;
    queue<int> q; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        while (T[u].size() > 2) {
            int x = T[u].back(); T[u].pop_back();
            int y = T[u].back(); T[u].pop_back();
            int dx = G[u].back().second; G[u].pop_back();
            int dy = G[u].back().second; G[u].pop_back();
            m++;
            T[m].push_back(x), T[m].push_back(y);
            G[m].push_back({x, dx}), G[m].push_back({y, dy});
            T[u].push_back(m); G[u].push_back({m, 0});
        }
        for (int v : T[u]) q.push(v);
    }
    vector<tuple<int, int, int>> t;
    for (int u = 1; u <= m; u++)
        for (auto &[v, d] : G[u]) t.push_back({u, v, d});
    for (auto &[u, v, d] : t) T[v].push_back(u), G[v].push_back({u, d}); 
}
vector<int> all, todo;
bool vis[200010];
int siz[200010], bid[200010];
int dis[200010];
int ans[250010];
void getsz(int u, int fa) {
    siz[u] = 1; all.push_back(u);
    for (int v : T[u]) {
        if (v == fa || vis[v]) continue;
        getsz(v, u);
        siz[u] += siz[v];
    }
}
int getrt(int u, int fa, int sz) {
    for (int v : T[u]) {
        if (v == fa || vis[v]) continue;
        if (siz[v] > sz / 2) return getrt(v, u, sz);
    }
    return u;
}
void fill(int u, int fa, int id) {
    bid[u] = id;
    for (int v : T[u]) {
        if (v == fa || vis[v]) continue;
        fill(v, u, id);
    }
}
void dij(int s, vector<int> &em) {
    for (int u : em) dis[u] = inf;
    priority_queue<pair<int, int>> pq;
    dis[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        d = -d;
        for (auto [v, ds] : G[u]) {
            if (!bid[v] || d + ds >= dis[v]) continue;
            dis[v] = d + ds;
            pq.push({-dis[v], v});   
        }
    }
}
void find(int u, int fa) {
    for (auto [v, ds] : G[u])
        if (bid[u] > 0 && bid[v] > 0 && bid[u] < bid[v]) todo.push_back(u);
    for (int v : T[u]) {
        if (v == fa || vis[v]) continue;
        find(v, u);
    }
}
void work(int u, vector<int> &que) {
    getsz(u, 0);
    int rt = getrt(u, 0, siz[u]);
    vis[rt] = 1;
    int tid = 0;
    int pson[4] = {0, 0, 0, 0};
    bid[rt] = -1;
    for (int son : T[rt]) {
        if (vis[son]) continue;
        fill(son, rt, ++tid);
        pson[tid] = son;
    }
    for (int son : T[rt]) {
        if (vis[son]) continue;
        find(son, rt);
    }
    todo.push_back(rt);
    for (int now : todo) {
        dij(now, all);
        for (int id : que) {
            int qu = q[id].u, qv = q[id].v;
            ans[id] = min(ans[id], dis[qu] + dis[qv]);
        }
    }
    vector<int> subq[4];
    for (int id : que) {
        int qu = q[id].u, qv = q[id].v;
        if (bid[qu] == bid[qv]) subq[bid[qu]].push_back(id);
    }
    for (int u : all) bid[u] = 0;
    all.clear(); todo.clear();
    for (int i = 1; i <= tid; i++) 
        if (!subq[i].empty()) work(pson[i], subq[i]);
}
void solve() {
    n = read();
    for (int i = 2; i <= n; i++) {
        int p = read(), d = read();
        G[p].push_back({i, d});
        T[p].push_back(i);
    }
    for (int i = 1; i <= n; i++) if (T[i].empty()) k++, outp.push_back(i);
    for (int i = 1; i <= k; i++) w[i] = read();
    Q = read();
    for (int i = 1; i <= Q; i++) q[i].u = read(), q[i].v = read();
    trans();
    for (int i = 0; i < k; i++) {
        int u = outp[i], v = outp[(i + 1) % k];
        G[u].push_back({v, w[i + 1]});
        G[v].push_back({u, w[i + 1]});
    }
    for (int i = 1; i <= Q; i++) ans[i] = inf;
    vector<int> que;
    for (int i = 1; i <= Q; i++) que.push_back(i);
    work(1, que);
    for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
}

::::