史山

Tomwsc · 2026-06-10 20:49:47 · 题解

喵喵题。

考虑离线做树分治。观察发现，如果使用点分治，会使得原树被分成多个部分，而我们并不知道这些部分两两间的最短路径，部分内部的最短路径也是难以处理的。考察到最短路与边强相关，所以我们换一种思路，使用边分治。

先对原树进行三度化操作，然后进行边分治。注意到，边分治过程中，原树只会被分成两个部分，而这两个部分之间最多有 3 条边相连。所以我们可以对这些边上的点均跑一边最短路，然后再合并答案即可。其实在三度化之后直接做点分治也是可以被接受的。

递归 \log n 层，最短路单老哥，每个询问最多被递归 \log n 次。

故总时间复杂度为 O(n\log^2 n+q\log n)。

代码写成史了。

::::success[Code]

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

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using i128 = __int128;

using PII = pair<int, int>;
using PLL = pair<ll, ll>;

#define fi first
#define se second

constexpr ll inf = (1ll << 62);
constexpr int N = 4e5 + 10;

template <typename T> void chkmax(T& a, T b) { a = max(a, b); }
template <typename T> void chkmin(T& a, T b) { a = min(a, b); }

int n, sz[N], dfn[N];
ll dis[2][N], val[N];
bool flag[2][N];
vector<vector<PLL>> adj(N), G(N), nG(N);

struct Query {
    int u, v;
    ll id;
};

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int p; ll c;
        cin >> p >> c;
        adj[p].emplace_back(i + 1, c);
        adj[i + 1].emplace_back(p, c);
    }
    int tot = n;
    vector<int> leaf;
    map<PII, bool> vis;
    map<PII, ll> edge;

    auto rebuild = [&](auto self, int u, int fa) -> void {
        if (adj[u].size() == 1) {
            leaf.emplace_back(u);
            return;
        }
        int lst = u;
        for (auto [v, w] : adj[u]) {
            if (v == fa) continue;
            self(self, v, u);
            G[lst].emplace_back(v, w);
            G[v].emplace_back(lst, w);
            edge[{lst, v}] = edge[{v, lst}] = w;
            G[lst].emplace_back(++tot, 0);
            G[tot].emplace_back(lst, 0);
            edge[{lst, tot}] = edge[{tot, lst}] = 0;
            lst = tot;
        }
    };

    rebuild(rebuild, 1, 0);
    for (int i = 1; i <= tot; i++) {
        nG[i] = G[i];
        dis[0][i] = dis[1][i] = inf;
    }
    sort(leaf.begin(), leaf.end());
    vector<int> nxt(tot + 1), prev(tot + 1);
    for (int i = 1; i < leaf.size(); i++) {
        ll w;
        cin >> w;
        nxt[leaf[i - 1]] = leaf[i];
        prev[leaf[i]] = leaf[i - 1];
        val[leaf[i - 1]] = w;
        nG[leaf[i - 1]].emplace_back(leaf[i], w);
        nG[leaf[i]].emplace_back(leaf[i - 1], w);
        edge[{leaf[i], leaf[i - 1]}] = edge[{leaf[i - 1], leaf[i]}] = w;
    }

    {
        ll w;
        cin >> w;
        nxt[leaf.back()] = leaf.front();
        prev[leaf.front()] = leaf.back();
        val[leaf.back()] = w;
        nG[leaf.back()].emplace_back(leaf.front(), w);
        nG[leaf.front()].emplace_back(leaf.back(), w);
        edge[{leaf.back(), leaf.front()}] = edge[{leaf.front(), leaf.back()}] = w;
    }

    vector<int> vertex;
    vector<int> col(tot + 1, -1);

    auto dijkstra = [&](int s, int id) -> void {
        priority_queue<PLL, vector<PLL>, greater<PLL>> q;
        q.push({0, s});
        dis[id][s] = 0;
        while (!q.empty()) {
            auto [w, u] = q.top(); q.pop();
            if (flag[id][u]) continue;
            flag[id][u] = true;
            vertex.emplace_back(u);
            for (auto [v, w] : nG[u]) {
                if (col[v] == col[s] && dis[id][u] + w < dis[id][v]) {
                    dis[id][v] = dis[id][u] + w;
                    q.push({dis[id][v], v});
                }
            }
        }
    };

    int q;
    cin >> q;
    vector<Query> qry(tot + 1);
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        qry.emplace_back(u, v, i);
    }
    vector<ll> ans(q, inf);

    auto color = [&](auto self, int u, int fa, int c) -> void {
        col[u] = c;
        sz[u] = 1;
        for (auto [v, w] : G[u]) {
            if (v == fa || vis[{u, v}]) continue;
            self(self, v, u, c);
            sz[u] += sz[v];
        }
    };

    auto calc = [&](auto self, int u, int v, vector<Query> cur) -> void {
        vector<Query> Q, curr[2];
        color(color, u, v, 1), color(color, v, u, 0);
        for (auto [x, y, id] : cur) {
            if ((col[x] ^ col[y]) == 1) {
                if (!col[x]) swap(x, y);
                Q.emplace_back(x, y, id);
            }
            if (col[x] == 1 && col[y] == 1) curr[0].emplace_back(x, y, id);
            if (!col[x] && !col[y]) curr[1].emplace_back(x, y, id);
        }
        // cerr << u << " " << v << ":\n";
        // for (int i = 1; i <= tot; i++) {
        //  cout << col[i] << " \n"[i == tot];
        // }
        int maxn[2] = {0, 0}, minn[2] = {tot, tot}, siz[2] = {sz[u], sz[v]}, res[2];
        PII rt[2] = {{-1, -1}, {-1, -1}};

        auto dfs = [&](auto self, int x, int fa, int id) -> void {
            if (x > 1 && G[x].size() == 1) chkmin(minn[id], x);
            if (x <= n && G[x].size() == 1) chkmax(maxn[id], x);

            auto get = [&](PII node) -> int {
                return abs(sz[node.se] * 2 - siz[id]);
            };

            for (auto [y, w] : G[x]) {
                if (y == fa || vis[{x, y}] || col[y] != col[x]) continue;
                self(self, y, x, id);
                if (rt[id].fi == -1 || res[id] > get({x, y})) {
                    rt[id] = {x, y};
                    res[id] = get({x, y});
                }
            }
        };

        dfs(dfs, u, v, 0), dfs(dfs, v, u, 1);
        vector<Query> dot;
        dot.emplace_back(u, v, edge[{u, v}]);
        if (minn[0] < minn[1]) {
            swap(minn[0], minn[1]);
            swap(maxn[0], maxn[1]);
        }
        if ((col[minn[0]] ^ col[prev[minn[0]]]) == 1) {
            dot.emplace_back(minn[0], prev[minn[0]], val[prev[minn[0]]]);
        }
        if ((col[maxn[0]] ^ col[nxt[maxn[0]]]) == 1) {
            dot.emplace_back(maxn[0], nxt[maxn[0]], val[maxn[0]]);
        }
        // for (auto [x, y, id] : Q) {
        //  cerr << x << " " << y << " " << id << "\n";
        // }
        // cout << minn[0] << " " << maxn[0] << "\n";
        // cout << minn[1] << " " << maxn[1] << "\n";
        for (auto &[x, y, w] : dot) if (col[x] != col[u]) swap(x, y);
        color(color, v, u, 1);
        for (auto &[x, y, w] : dot) {
            // cerr << x << " " << y << " " << w << "\n";
            dijkstra(x, 0), dijkstra(y, 1);
            // for (int i = 1; i <= tot; i++) {
            //  if (dis[0][i] == inf) cout << "w ";
            //  else cout << dis[0][i] << " ";
            // }cout << "\n";
            // for (int i = 1; i <= tot; i++) {
            //  if (dis[1][i] == inf) cout << "w ";
            //  else cout << dis[1][i] << " ";
            // }cout << "\n";
            for (auto [u, v, id] : Q) {
                if (dis[0][u] == inf || dis[1][v] == inf) continue; 
                chkmin(ans[id], dis[0][u] + dis[1][v] + w);
            }
            for (auto [u, v, id] : curr[0]) {
                if (dis[0][u] == inf || dis[0][v] == inf) continue;
                chkmin(ans[id], dis[0][u] + dis[0][v]);
            }
            for (auto [u, v, id] : curr[1]) {
                if (dis[1][u] == inf || dis[1][v] == inf) continue;
                chkmin(ans[id], dis[1][u] + dis[1][v]);
            }
            for (auto i : vertex) {
                dis[0][i] = dis[1][i] = inf;
                flag[0][i] = flag[1][i] = false;
            }
            vertex.clear();
        }

        auto check = [&](PII &it) -> void {
            if (it.fi > it.se) swap(it.fi, it.se);
        };

        check(rt[0]), check(rt[1]);
        vis[{u, v}] = vis[{v, u}] = true;
        color(color, u, v, -1), color(color, v, u, -1);
        if (~rt[0].fi) self(self, rt[0].fi, rt[0].se, curr[0]);
        if (~rt[1].fi) self(self, rt[1].fi, rt[1].se, curr[1]);
    };

    int iu = -1, iv, res;

    auto init = [&](auto self, int u, int fa) -> void {
        sz[u] = 1;
        for (auto [v, w] : G[u]) {
            if (v == fa) continue;
            self(self, v, u);
            sz[u] += sz[v];
            if (iu == -1 || res > abs(sz[v] * 2 - tot)) {
                iu = u, iv = v;
                res = abs(sz[v] * 2 - tot);
            }
        }
    };

    init(init, 1, 0);
    if (iu > iv) swap(iu, iv);
    // for (int i = 1; i <= tot; i++) {
    //  for (auto [v, w] : G[i]) {
    //      cout << i << " " << v << " " << w << "\n";
    //  }
    // }
    calc(calc, iu, iv, qry);
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
}

int main() {
    // freopen("roka5.in", "r", stdin);
    // freopen("sb.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

::::